03.pdf

1.KLASYCZNALOGIKAZDAŃ

1.0. ZAŁOŻENIA KLASYCZNEGO RACHUNKU

ZDAŃ

Rozważymy teraz problem rachunku dla logiki zdań 20 . Logika

zdań jest logiką języka, którego najprostsze, wewnętrznie nieanali-

zowalne elementy to zdania i w którym z tych zdań – określanych

jako proste lub atomowe – i ze specjalnych wyrażeń zwanych spój-

nikamiorazznaków interpunkcyjnych,którymisąnawiasy,konstru-

owane sąwszystkiepozostałewyrażeniapoprawniezbudowanetego

języka – zdania złożone. W języku zdaniowym wszystkie elementy

znaczeniowewiążącetezdaniazesobąsąwięcwyrażalneprzezspój-

nikizdaniowe.Takimjęzykiemniejestanijęzyknaturalny,aniżaden

zjęzykówróżnychsystemówwiedzy.Wtakimsensiejęzyklogikizdań

jestﬁkcyjny.Zasadylogikizdaństosująsięjednakdowszystkichję-

zykówotyle,oileabstrahujemyodwewnętrznejzłożonościichzdań

prostych.Rozważanielogikizdańjestużytecznezarównoteoretycznie

jak i dydaktycznie. Rachunek dla logiki zdań jest bowiem fragmen-

tem bogatszego rachunku dla logiki języka, w którym wyróżnia się

elementyskładowezdań–będzietorachunekpredykatów. Klasyczna

20 Rachunekzdańjestpowszechnieuważanyzapolskąspecjalność.J.Woleński

[1985]podajenastępującąanegdotę.GdyA.Tarskispotkałsięporazpierwszyz

E.Postem(byłotozapewnewroku1939lub1940)sugerowałmu,żejestjedynym

logikiem, któryuzyskałważnewynikiwrachunkuzdań,anie manic wspólnego

z Polską. Na to Post miał rzec: „O nie, urodziłem się w Białymstoku, a to jest

miasto we wschodniej Polsce.” (zob. s. 84) W życiorysie E. Posta podaje się, że

urodziłsięwAugustowie.

1. KLASYCZNALOGIKAZDAŃ

logika zdań to logika języka, którego wszystkie spójnikisą prawdzi-

wościowe i ponadto przyjmujesię dwiewartości logiczne: prawdęi

fałsz.

1.1. TAUTOLOGIE I ZDANIA LOGICZNIE PRAW-

DZIWE

Określimyterazczystoformalniejęzykrachunkuzdań.Podamy

więcalfabettegojęzykairegułykonstrukcjiwyrażeńpoprawniezbu-

dowanych:zdań.

Zdaniabudujemy,abymówić opewnejrzeczywistości, ojakimś

świecie.Wlogicematematycznejtakim«światem»jestabstrakcyjny

konstrukt: model. Będzie on tak zbudowany, aby ujmował interesu-

jącenasaspektyodnoszeniazdańdoświata.Ściśleokreślony«świat»,

model, umożliwi deﬁnicję prawdziwości zdania (w modelu). Pojęcie

prawdziwościzdaniajestpojęciemsemantycznym.Naszymcelemjest

wskazanieczystosyntaktycznych własnościowychzdań,awięctych

własnościichkształtu,budowy,któresącharakterystycznedlazdań

prawdziwychwewszystkichmodelach.Wyróżnimypewnąklasęzdań,

które będziemy określali jako tautologie. Pojęcie tautologii będzie

więc pojęciem syntaktycznym. Ustalimy związek pomiędzy byciem

tautologiąabyciemzdaniemprawdziwymwewszystkichmodelach.

1.1.1. Pojęcie spójnika

Wkażdymjęzykuistniejąróżnesposobytworzeniazdańzezdań.

Służyć temu celowi mogą różne wyrażenia (w gramatyce nazywane

spójnikami i partykułami), zestawienie zdań (połączenie zdań skła-

dowychwrazzużyciem–wjęzykumówionym–stosownejintonacji

–awjęzykupisanym–odpowiedniejinterpunkcji).

Spójnik tokażdeitylkotakiewyrażenie,którełączniezezdaniem

bądźzdaniamitworzyzdanie.

PRZYKŁADY

Spójnikami są np.: „nieprawda, że ... ”, „konieczne jest, że ... ”

oraz„ ... lub ... ”i„ ... oraz ... ”.Spójnikiemniejest:„ ... jest”.

1.1. TAUTOLOGIE I ZDANIA LOGICZNIE PRAWDZIWE

Zdania,zktórychdanyspójniktworzyzdanieto argumenty tego

spójnika.Spójnikidzielisięzewzględunailośćichargumentów.Wy-

różniamywięcspójniki jednoargumentowe, dwuargumentowe itd.

Zdania,któreotrzymujemywwynikudopisaniazdanialubzdań

dospójnikato zdania złożone . Zdania proste tozdania,któreniesą

złożone,czyliwktórychniewystępująspójniki.

PRZYKŁADY

Zdaniamiprostymisą:

2+2=4 .

Trójkąt ma trzy boki.

Zdaniamizłożonymisą:

Nieprawda,że 2+2=4 .

Jeżeliczworokątmaczterybokirówne,tomadwakątyrówne.

1.1.2. Alfabet języka klasycznej logiki zdań

Alfabet A języka klasycznej logiki zdań jest zbiorem następują-

cychprzedmiotów(symboli):

(I) p 0 ,p 1 ,... ,

(II) ¬ ,

(III) ⇒ , ∨ , ∧ , ⇔ ,

(IV) ) , ( .

Zbiór wszystkich skończonych ciągów elementów A to A ∗ .Ele-

menty A ∗ to słowanadalfabetem A .

p 0 ,p 1 ,... to litery zdaniowe . Intuicyjnie reprezentują one zdania

proste,czylizdania,wktórychniewystępująspójniki.Stądteżnazy-

wanesą atomami .Dopuszczamybyzdańtychbyłotyle,ilejestliczb

naturalnych,czyliprzeliczalnienieskończeniewiele.Wteoretycznych

rozważaniach przyjmujemy, że litery zdaniowe są niezłożonymi zna-

kami.Zwyklejakoliterzdaniowychużywaćbędziemyliter: p,q,r,... .

¬ jestspójnikiemjednoargumentowym.Nazywamygo negacją 21 .

21 Łacińskie nego znaczy:przeczę.

1. KLASYCZNALOGIKAZDAŃ

Spójniki: ⇒ , ∨ , ∧ , ⇔ sądwuargumentowe.Nazywamyje,odpo-

wiednio: implikacją 22 , alternatywą , koniunkcją i równoważnością .W

wypadkuimplikacjijejpierwszyargumentnazywamy poprzednikiem

adrugi następnikiem .

Nawiasy : ) –nawiasprawy, ( –nawiaslewy,pełniąfunkcję znaków

interpunkcyjnych .Znakitewnaszymjęzykulogikizdańsąniezbędne

dlajednoznacznegozapisuwyrażeńtegojęzyka.Zwykledlawygody–

wtymcelu,abynapisbyłbardziejczytelny–stosujesięteżnawiasy

innychkształtów: ] , [ ; } , { .

1.1.3. Deﬁnicja zdania (wyrażenia poprawnie zbudowa-

nego logiki zdań)

1.1.3.1. Zdanie w notacji standardowej

Z elementów powyżej opisanego słownika (alfabetu) budujemy

zdania. Zdania są jedynymi poprawnie zbudowanymi wyrażeniami

językalogikizdań.

DEFINICJAZDANIA

Niech α i β będądowolnymi skończonymiciągami symbolialfa-

betujęzykalogikizdań,czyli α i β sąelementami A ∗ ( α , β ∈A ∗ ).

(I) literyzdaniowesązdaniami;

(II) jeżeli α jestzdaniem,to ¬ α jestzdaniem;

(III) jeżeli α , β sązdaniami,to( α ⇒ β ),( α ∨ β ),( α ∧ β ),( α ⇔ β )są

zdaniami;

(IV) niemainnychzdańopróczliterzdaniowychoraztychwyrażeń,

któresąskończonymiciągamisymboli 23 spełniającymiwarunki

(II)i(III).

22 Spójnik ten określany jest również jako implikacja materialna dla odróż-

nienia od implikacji formalnej . Termin „implikacja formalna” używany jest na

oznaczenie implikacji, której warunkiem koniecznym poprawności i sensowności

jestzachodzeniezwiązkuformalnegomiędzy poprzednikiemanastępnikiem.

23 Pojęciaużytewdeﬁnicjizdania:ciągu,skończonegociągu,najmniejszego

zbiorunależądoteoriimnogości,tamteżpodanesąichdeﬁnicje.

1.1. TAUTOLOGIE I ZDANIA LOGICZNIE PRAWDZIWE

Warunek(IV)możnazastąpićwarunkiemrównoważnym:

(IV)’ zbiór zdań jest najmniejszym zbiorem skończonych ciągów

symbolispełniającychwarunki(I)–(III).

Zbiór wyrażeń poprawnie zbudowanych, w tym wypadku zdań,

jestpodzbiorem A ∗ .

PRZYKŁADY

Zdaniamisą: p 0 , p 4 , p 5 , ¬ p 0 , ( p 5 ∨ p 0 ) , ( ¬ ( p 0 ∧ p 5 ) ∨ p 0 ) .

Zdaniaminiesą: ( p 0 ) , ¬ ( p 0 ) ¬ ( p 5 ) ∨ ( p 0 ) , ¬ ( p 0 p 5 ) ∨ ( p 0 ) , ( p 0 ∨ p 1 ) ∧

p 0 ∨ p 1 )

∧

(

p 0 ∨ p 1 )

∧ ... .

Skończonyciąg α elementówsłownikajestzdaniemwtedyitylko

wtedy,gdyłączniespełnionesąnastępującewarunki:

1. Pierwszym wyrazem ciągu α jest litera zdaniowa, albo spójnik

negacjialbonawiaslewy.

2. Po literze zdaniowej albo nie następuje nawias prawy, albo na-

stępujenawiasprawyalbonastępujespójnikdwuargumentowy.

3. Ponawiasielewymnastępujeliterazdaniowa,albospójniknega-

cjialbonawiaslewy.

4. W α występujetylesamospójnikówdwuargumentowych,cona-

wiasówlewychiconawiasówprawych.

5. Wkażdymmiejscuw α ,wktórymznajdujesięnawiaslewyza-

czynasięodcinekciągutaki,żeliczbawystąpieńnawiasówlewych

jestrównaliczbiewystąpieńnawiasówprawych,awnajkrótszym

tego rodzajuodcinkuliczby te sąrówneliczbie wystąpieńspój-

nikówdwuargumentowych.

Podanacharakterystykadajepodstawędlaautomatyzacjispraw-

dzania,czydanyciąg α jestzdaniem.

PRZYKŁADY

Ciąg

((

p 0 ⇒ p 1 )

∧ p 2 )

⇔

((

p 3 ∨

(

p 1 ⇒¬ p 2 )))

(

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: