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 znaleźć 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 są 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 używa 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 .^1.1

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 wcześniej 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 fałszywy. 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ść.