Rachunek zdań
Rozwa\
my zdanie:
(Z)
Ala je i As wyje.
Jest to zdanie oznajmujące zło\
one z dwóch zdań prostych: ``Ala je'' i ``As wyje'', połączonych spójnikiem
``i''. Oznaczmy symbolem zdanie ``Ala je'', zaś symbolem zdanie ``As wyje''. Wówczas wiedząc, czy
zdania i są prawdziwe, potrafimy rozstrzygnąć, czy zdanie (Z) jest prawdziwe. Na przykład, jeśli
prawdą jest, \
e Ala je (tzn. zdanie jest prawdziwe), oraz nieprawda, \
e As wyje, to wówczas wiemy, \
e
zdanie (Z) jest fałszywe. Zale\
ność między prawdziwością zdań i , a prawdziwością zdania `` i ''
wyznaczona jest jednoznacznie przez własności spójnika ``i''. W rachunku zdań zajmujemy się właśnie
badaniem, jak prawdziwość zdań zło\
onych przy pomocy ró\
nych spójników zale\
y od prawdziwości zdań
prostych.
W logice wartość logiczną zdania definiujemy jako , gdy zdanie to jest fałszywe, zaś jako , gdy zdanie
to jest prawdziwe. Symbolu u\
ywamy równie\
do oznaczenia dowolnego zdania fałszywego, zaś
symbolu do oznaczenia dowolnego zdania prawdziwego.
Zdania oznaczamy głównie symbolami . Zapis oznacza, \
e zdanie jest fałszywe (ma
wartość logiczną ), zaś zapis oznacza, \
e zdanie jest prawdziwe (ma wartość logiczną ). W
rachunku zdań spójniki logiczne równie\
oznaczamy specjalnymi symbolami, na przykład spójnik
koniunkcji ``i'' oznaczamy symbolem . Zdanie nazywamy koniunkcją zdań i .
Wartości logiczne koniunkcji dla wszystkich mo\
liwych układów wartości logicznych zdań i
mo\
emy zapisać w formie tabelki.
Spójnik koniunkcji jest spójnikiem dwuargumentowym (gdy\
tworzymy przy jego pomocy nowe zdania
z dwóch zdań wyjściowych). Spójnik mo\
emy te\
traktować jak działanie na symbolach i .
Wówczas tabelkę wartości logicznych koniunkcji mo\
emy streścić w ciagu równości:
A zatem
Wprowadzimy teraz niektóre inne spójniki logiczne.
oznacza jednoargumentowy spójnik negacji: oznacza zdanie: ``nie '', czy te\
``nieprawda, \
e ''.
Tabelka wartości logicznych negacji :
Mo\
emy więc napisać i .
oznacza dwuargumentowy spójnik alternatywy. oznacza zdanie `` lub ''. Podobnie jak w
przypadku implikacji, w języku potocznym sens spójnika alternatywy nie jest precyzyjny. W rachunku
zdań przyjmujemy, \
e alternatywa jest prawdziwa dokładnie wtedy, gdy przynajmniej jedno ze zdań
jest prawdziwe. Widać to w poni\
szej tabelce.
oznacza dwuargumentowy spójnik równowa\
ności. oznacza ka\
de z następujących
równowa\
nych zdań:
1. `` wtedy i tylko wtedy, gdy ''
2. `` dokładnie wtedy, gdy ''
3. `` jest warunkiem koniecznym i dostatecznym do tego, \
e ''
4. `` jest równowa\
ne temu, \
e ''
Najczęściej jednak odczytuje się je na pierwszy z powy\
szych sposobów. Przyjmujemy, \
e równowa\
ność
jest prawdziwa dokładnie wtedy, gdy i mają te same wartości logiczne.
 oznacza dwuargumentowy spójnik implikacji. Implikacja oznacza zdanie ``jeśli , to ''. W
implikacji zdanie nazywamy poprzednikiem, zaś następnikiem implikacji. Implikację
nazywamy implikacją odwrotną do . By znalez
ć tabelkę wartości logicznych implikacji rozwa\
my
następujący przykład.
Ojciec obiecuje Jasiowi:
Jeśli , to .
Obietnica ta jest więc implikacją . Ojciec nie dotrzyma słowa tylko w jednym przypadku: je\
eli
mianowicie jutro będzie ładna pogoda (tzn. ), a nie pójdą z Jasiem na grzyby (tzn. ). Dlatego
przyjmujemy, \
e implikacja jest fałszywa tylko wtedy, gdy i . W pozostałych
przypadkach ma wartość logiczną . Zatem tabelka wartości logicznych implikacji wygląda
następująco:
Dlatego na przykład . Trzeba tu przyznać, \
e logiczny spójnik implikacji niezbyt dokładnie
oddaje sens potoczny konstrukcji ``jeśli... to'' (który trudno jednak sprecyzować). Przykładowo zgodnie z
formalnym znaczeniem tego spójnika inną obietnicę ojca Jasia: ``jeśli jutro będzie padał deszcz, to
polecimy na Księ\
yc'' wypadnie uznać za zdanie prawdziwe, jeśli tylko jutro nie będzie deszczu. Jednak w
matematyce dą\
ymy do sprecyzowania znaczenia wypowiadanych zdań i dlatego decydujemy się na
powy\
szą definicję.
Implikację mo\
emy odczytywać na wiele równowa\
nych sposobów:
1. `` pod warunkiem, \
e ''
2. `` wtedy, gdy ''
3. `` tylko wtedy, gdy ''
4. `` jest warunkiem dostatecznym do tego, \
e ''
5. `` jest warunkiem koniecznym do tego, \
e ''
Przykład. Niech oznacza pewną liczbę naturalną. Rozwa\
my zdanie:
(A) Jeśli , to .
Zdanie to jest implikacją . Jest ono prawdziwe niezale\
nie od tego, jaką konkretnie liczbą naturalną
jest . Innymi słowy, w ka\
dej sytuacji jeśli zachodzi warunek , to zachodzi warunek . Nie ma więc
takiej sytuacji, \
e zachodzi warunek , zaś nie zachodzi warunek . Dlatego do tego, by zachodził
warunek konieczne jest, by zachodził warunek .
Uwagi o twierdzeniach i dowodach.
Prawa, zwłaszcza prawa matematyki, formułujemy w postaci twierdzeń. Najogólniej rzecz biorąc,
twierdzenie orzeka, \
e ka\
dej sytuacji, w której spełnione sa określone zało\
enia, prawdziwa jest
określona teza. Schemat twierdzenia jest więc następujący:
Jeśli , to .
W inny sposób mo\
emy to wyrazić pisząc:
Załó\
my, \
e . Wtedy .
Twierdzenie ma więc formę implikacji
Przykładem twierdzenia jest (A). Zało\
eniem jest tu stwierdzenie, \
e jest liczbą naturalną podzielną
przez , tezą zaś stwierdzenie, \
e jest podzielne przez .
Niektóre twierdzenia matematyczne sa oczywiste, nazywamy je wtedy aksjomatami lub pewnikami.
Zazwyczaj jednak twierdzenia wymagają uzasadnienia czyli dowodu.
Mówimy, \
e dany warunek wynika z zało\
eń (przesłanek) , gdy w ka\
dej sytuacji, w której jest
prawdziwe, równie\
jest prawdziwe. Najogólniej rzecz biorąc, dowód twierdzenia polega na
uzasadnieniu, \
e z zało\
eń wynika teza twierdzenia. Rozró\
niamy dowody wprost i nie wprost.
Dowód wprost to ciąg zdań rozpoczynający się od zało\
eń twierdzenia, kończący się tezą twierdzenia, w
którym kolejne zdania są oczywiste lub wynikają z poprzednich zdań dowodu w sposób oczywisty. W
dowodzie mo\
emy odwoływać się do definicji, faktów oczywistych lub udowodnionych wcześniej.
W matematyce często uzywa się pojęć zło\
onych, wprowadzanych przy pomocy definicji odwołujących
się do pojęć prostszych, podstawowych. Przykładowo, w twierdzeniu (A) występuje pojęcie podzielności.
Przypomnijmy jego definicję.
Definicja Liczba całkowita jest podzielna przez liczbę całkowitą (symbolicznie: ), gdy
dla pewnej liczby całkowitej .
Odwołując się do definicji mo\
emy sprawdzić, \
e np. liczba jest podzielna przez
(świadczy o tym liczba ). Podobnie, jest podzielna przez ka\
dą liczbę całkowitą
(świadczy o tym liczba ). W szczególności, liczba jest podzielna przez (nie znaczy to jednak, \
e
istnieje wynik tego dzielenia).
W dowodzie wprost wyobra\
amy sobie sytuację, w której spełnione są zało\
enia twierdzenia, a następnie
w kolejnych krokach rozumowania wyciągamy wnioski na temat tej sytuacji. W rozumowaniu mo\
emy
odwoływać się do definicji, faktów znanych wczesniej i wcześniejszych kroków rozumowania. Ostatnim
krokiem rozumowania jest teza.
Przykładowo podamy szczegółowy dowód wprost twierdzenia (A). Opatrzymy go komentarzami w
nawiasach kwadratowych.
Dowód twierdzenia A.
1. Załó\
my, \
e liczba naturalna jest podzielna przez . [ zało\
enie]
2. Znaczy to, \
e dla pewnej liczby całkowitej . [odwołanie do definicji]
3. [odwołanie do znanego faktu]
4. Dlatego . [wniosek z 2. i 3.]
5. Niech . Wtedy . [wniosek z 4.]
6. Na mocy definicji, jest podzielna przez . [teza, odwołanie do definicji].
W dowodzie twierdzenia (A) wyobraziliśmy sobie dowolną sytuację, w której spełnione są zało\
enia
twierdzenia, tzn. rozwa\
yliśmy dowolną liczbę naturalną podzielną przez (punkt 1. dowodu). Od tego
momentu symbol oznaczał w dowodzie cały czas tę ustaloną liczbę naturalną. W punkcie 2. dowodu
wprowadziliśmy liczbę całkowitą , a następnie w punkcie 5. liczbę całkowitą . Dowód polegał na
operowaniu tymi obiektami wg określonych reguł. Mo\
na tu dostrzec analogię z operowaniem figurami w
partii gry w szachy.
Drugim rodzajem dowodu jest dowód nie wprost. W dowodzie nie wprost rozwa\
amy (hipotetyczną)
sytuację, w której spełnione są zało\
enia twierdzenia, zaś teza nie. Na początku takiego dowodu oprócz
zało\
eń twierdzenia zakładamy dodatkowo, \
e teza nie zachodzi. Następnie dą\
ymy do pokazania, \
e z
tych zało\
eń wynika sprzeczność, tzn. zdanie fałszywe. Uzyskana sprzeczność przekonuje nas, \
e nasza
hipotetyczna sytuacja nie mo\
e istnieć. Znaczy to, \
e teza wynika z zało\
eń, dowodząc tym samym
twierdzenia.
Przykładowo, udowodnimy metodą nie wprost następujące twierdzenie.
Twierdzenie B Je\
eli jest liczbą rzeczywistą dodatnią taką, \
e , to nie jest wymierna.
Dowód Nie wprost. Załó\
my, \
e jest dodatnią liczbą rzeczywistą taką, \
e . Przypuśćmy (nie
wprost), \
e jest wymierna. Mo\
emy więc przedstawić w postaci nieskracalnego ułamka dla
pewnych dodatnich liczb naturalnych i . Skoro , to , czyli
Liczba jest więc parzysta (czyli podzielna przez ). Dlatego (na mocy definicji) jest postaci
dla pewnej liczby całkowitej . Stąd dostajemy, \
e , czyli
Liczba jest więc równie\
parzysta. Zatem ułamek jest skracalny, sprzeczność.
W wyra\
eniach i zdania nazywamy równie\
członami odpowiednio
koniunkcji, alternatywy, implikacji i równowa\
ności.
W algebrze u\
ywając symboli działań algebraicznych, zmiennych liczbowych i nawiasów mo\
emy
tworzyć zło\
one wyra\
enia algebraiczne. Na przykład rozwa\
my wyra\
enie
Gdy za zmienne podstawimy konkretne wartości liczbowe, wyra\
enie to staje się liczbą, ma wartość
liczbową obliczoną poprzez wykonanie wskazanych działań. Nawiasy wskazują na kolejność
wykonywania operacji. Mo\
emy te\
odczytać strukturę wyra\
enia . Mianowicie jest iloczynem
zmiennej i wyra\
enia . Z kolei wyra\
enie jest ró\
nicą
wyra\
enia i wyra\
enia .
Podobnie w rachunku zdań mo\
emy traktować spójniki logiczne jako operacje na zdaniach słu\
ące do
tworzenia nowych zdań. U\
ywając zmiennych zdaniowych , spójników logicznych
i nawiasów mo\
emy tworzyć zło\
one formuły zdaniowe (zwane równie\
wyra\
eniami lub
schematami zdaniowymi). Na przykład rozwa\
my formułę
Gdy za zmienne zdaniowe podstawiamy konkretne zdania, formuła ta staje się zdaniem utworzonym
poprzez działanie odpowiednich spójników. Nawiasy wskazują na kolejność wykonywanych operacji.
Mo\
emy te\
odczytać strukturę formuły . Jest to mianowicie implikacja, której poprzednik to formuła
, zaś następnik to formuła . Przyjmujemy, \
e zmienne zdaniowe to równie\
(najprostsze)
formuły.
W algebrze ustalona jest hierarchia działań algebraicznych: najpierw wykonujemy mno\
enie, potem
dodawanie i odejmowanie. Dlatego w wyra\
eniach algebraicznych mo\
emy opuszczać niektóre nawiasy.
Na przykład wyra\
enie mo\
emy zapisać jako
Podobnie ustala się hierarchię spójników logicznych: najpierw działa spójnik negacji , potem działają
(równorzędnie) spójniki koniunkcji i alternatywy , na końcu zaś działają (równorzędnie) spójniki
implikacji i równowa\
ności . Dzięki temu mo\
emy opuszczać niektóre nawiasy. Dlatego formułę
mo\
emy zapisać w formie
Niech oznacza pewną formułę, w której jedyne zmienne zdaniowe to i (mówimy
wówczas, \
e jest to formuła o zmiennych ). Gdy oznaczają konkretne zdania, to równie\

oznacza zdanie, którego wartość logiczna zale\
y tylko od wartości logicznych zdań i
struktury formuły. Mo\
emy ją obliczyć zgodnie z tabelkami wartości logicznych spójników.
Przykład. Niech oznacza formułę . Dla wartość logiczna zdania
równa się:
W rachunku tym traktujemy spójniki jak działania na liczbach . Wyniki naszych obliczeń mo\
emy
umieścić w tabelce wartości logicznych formuły .
Wypełnienie pustych miejsc pozostawiamy jako ćwiczenie.
W matematyce obecna jest tendencja do algebraizacji. W szczególności wiele zdań matematycznych
zapisujemy w formie skrótowej, u\
ywając symboli na oznaczenie słów lub zwrotów.
Przykład. Załó\
my, \
e jest jakąś liczbą rzeczywistą. Równość algebraicznych wyra\
eń:
jest po prostu skróconym sposobem napisania zdania:
Iloczyn liczby powiększonej o jeden i liczby pomniejszonej o jeden równa się
kwadratowi liczby .
Podobnie zdanie:
Liczba minus trzy jest równa liczbie uzyskanej przez pomno\
enie liczby przez
pierwiastek kwadratowy z liczby ( plus jeden).
mo\
emy zapisać skrótowo jako:
Zauwa\
my, \
e dla uniknięcia niejednoznaczności w zdaniu potocznym zmuszeni byliśmy u\
yć nawiasów.
W algebrze niektóre tego typu zdania są prawdziwe dla wszystkich liczb rzeczywistych . Nazywamy je
wtedy to\
samościami. Przykłady to\
samości to
To\
samościom w algebrze w rachunku zdań odpowiadają tautologie.
Definicja 1..1 Mówimy, \
e formuła jest tautologią rachunku zdań (lub krótko:
tautologią), gdy jest zdaniem prawdziwym dla dowolnych zdań
Uwaga 1..2 Formuła jest tautologią wtedy i tylko wtedy, gdy ma wartość logiczną dla
wszystkich układów wartości logicznych zmiennych
Poni\
ej podajemy przykłady tautologii. Niektóre z nich mają w logice tradycyjne nazwy.
(prawo wyłączonego środka)
(prawo sprzeczności, w klasycznej logice wyra\
ano je mówiąc: ``nie mo\
e być tak, \
e prawdą
jest równocześnie zdanie i jego negacja'')
(prawo podwójnej negacji)
(prawo przechodniości implikacji)
(prawo transpozycji, zwane te\
prawem kontrapozycji)
i (prawa de Morgana)
Przykład Niech . Udowodnimy, \
e jest tautologią.
Sposób 1. Wprost. Sporządzamy tabelkę wartości logicznych formuły .
Z tabelki wartości logicznych formuły widzimy, \
e dla wszystkich wartości logicznych zmiennych
wartość równa się . Na mocy uwagi 1.2 jest więc tautologią.
Sposób 2. Nie wprost. Oznaczmy przez zdanie:
jest tautologią.
Przypuśćmy nie wprost, \
e zdanie to jest fałszywe, tzn. prawdziwe jest następujące zdanie :
nie jest tautologią.
Na mocy definicji tautologii znaczy to, \
e dla pewnych zdań i mamy
Implikacja jest fałszywa tylko w przypadku, gdy poprzednik jest prawdziwy, zaś następnik falszywy.
Dlatego dla konkretnych ju\
w tym momencie zdań dostajemy i . Alternatywa
jest fałszywa tylko wtedy, gdy oba jej człony są fałszywe. Stąd dostajemy w szczególności, \
e .
Wnioskujemy więc, \
e zarówno , jak i , sprzeczność.
9 z 9