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 $p$ zdanie ``Ala je'', zaś symbolem $q$ zdanie ``As wyje''. Wówczas wiedząc, czy zdania $p$ i $q$ są prawdziwe, potrafimy rozstrzygnąć, czy zdanie (Z) jest prawdziwe. Na przykład, jeśli prawdą jest, że Ala je (tzn. zdanie $p$ jest prawdziwe), oraz nieprawda, że As wyje, to wówczas wiemy, że zdanie (Z) jest fałszywe. Zależność między prawdziwością zdań $p$ i $q$, a prawdziwością zdania ``$p$ i $q$'' 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 $0$, gdy zdanie to jest fałszywe, zaś jako $1$, gdy zdanie to jest prawdziwe. Symbolu $0$ używamy również do oznaczenia dowolnego zdania fałszywego, zaś symbolu $1$ do oznaczenia dowolnego zdania prawdziwego.

Zdania oznaczamy głównie symbolami $p,q,r,s$. Zapis $p=0$ oznacza, że zdanie $p$ jest fałszywe (ma wartość logiczną $0$), zaś zapis $p=1$ oznacza, że zdanie $p$ jest prawdziwe (ma wartość logiczną $1$). W rachunku zdań spójniki logiczne również oznaczamy specjalnymi symbolami, na przykład spójnik koniunkcji ``i'' oznaczamy symbolem $\land$. Zdanie $p\land q$ nazywamy koniunkcją zdań $p$ i $q$.

Wartości logiczne koniunkcji $p\land q$ dla wszystkich możliwych układów wartości logicznych zdań $p$ i $q$ możemy zapisać w formie tabelki.

$$\begin{array}{c\vert c\vert c}p&q&p\land q\\ \hline 1&1&1\\ 1&0&0\\ 0&1&0\\ 0&0&0\end{array}$$

Spójnik koniunkcji $\land$ jest spójnikiem dwuargumentowym (gdyż tworzymy przy jego pomocy nowe zdania z dwóch zdań wyjściowych). Spójnik $\land$ możemy też traktować jak działanie na symbolach $0$ i $1$. Wówczas tabelkę wartości logicznych koniunkcji możemy streścić w ciagu równości:

$$0\land 0=0 \mbox{, \ \ \ \ tzn. \lq\lq fałsz i fałsz'' to \lq\lq fałsz'',}$$

$$0\land 1=0,\ 1\land 0=0,\ 1\land 1=1.$$

A zatem

$$p\land q=1\mbox { dokładnie wtedy, gdy }p=1\mbox { i } q=1.$$

Wprowadzimy teraz niektóre inne spójniki logiczne.

$\neg$ oznacza jednoargumentowy spójnik negacji: $\neg p$ oznacza zdanie: ``nie $p$'', czy też ``nieprawda, że $p$''. Tabelka wartości logicznych negacji $\neg p$:

$$\begin{array}{c\vert c}p&\neg p\\ \hline 0&1\\ 1&0\end{array}$$

Możemy więc napisać $\neg 0=1$ i $\neg 1=0$.

$\lor$ oznacza dwuargumentowy spójnik alternatywy. $p\lor q$ oznacza zdanie ``$p$ lub $q$''. Podobnie jak w przypadku implikacji, w języku potocznym sens spójnika alternatywy nie jest precyzyjny. W rachunku zdań przyjmujemy, że alternatywa $p\lor q$ jest prawdziwa dokładnie wtedy, gdy przynajmniej jedno ze zdań $p,q$ jest prawdziwe. Widać to w poniższej tabelce.

$$\begin{array}{c\vert c\vert c}p&q&p\lor q\\ \hline 1&1&1\\ 1&0&1\\ 0&1&1\\ 0&0&0\end{array}$$

$\Leftrightarrow$ oznacza dwuargumentowy spójnik równoważności. $p\Leftrightarrow q$ oznacza każde z następujących równoważnych zdań:

1. ``$p$ wtedy i tylko wtedy, gdy $q$''
2. ``$p$ dokładnie wtedy, gdy $q$''
3. ``$p$ jest warunkiem koniecznym i dostatecznym do tego, że $q$''
4. ``$p$ jest równoważne temu, że $q$''

Najczęściej jednak odczytuje się je na pierwszy z powyższych sposobów. Przyjmujemy, że równoważność $p\Leftrightarrow q$ jest prawdziwa dokładnie wtedy, gdy $p$ i $q$ mają te same wartości logiczne.

$$\begin{array}{c\vert c\vert c}p&q&p\Leftrightarrow q\\ \hline 1&1&1\\ 1&0&0\\ 0&1&0\\ 0&0&1\end{array}$$

$\Rightarrow$ oznacza dwuargumentowy spójnik implikacji. Implikacja $p\Rightarrow q$ oznacza zdanie ``jeśli $p$, to $q$''. W implikacji $p\Rightarrow q$ zdanie $p$ nazywamy poprzednikiem, zaś $q$ następnikiem implikacji. Implikację $q\Rightarrow p$ nazywamy implikacją odwrotną do $p\Rightarrow q$. By znaleźć tabelkę wartości logicznych implikacji rozważmy następujący przykład.

Ojciec obiecuje Jasiowi:

Jeśli $\overbrace{\mbox{jutro będzie ładna pogoda}}^{\mbox{$p$}}$, to $\overbrace{\mbox{pójdziemy na grzyby}}^{\mbox{$q$}}$.

Obietnica ta jest więc implikacją $p\Rightarrow q$. Ojciec nie dotrzyma słowa tylko w jednym przypadku: jeżeli mianowicie jutro będzie ładna pogoda (tzn. $p=1$), a nie pójdą z Jasiem na grzyby (tzn. $q=0$). Dlatego przyjmujemy, że implikacja $p\Rightarrow q$ jest fałszywa tylko wtedy, gdy $p=1$ i $q=0$. W pozostałych przypadkach $p\Rightarrow q$ ma wartość logiczną $1$. Zatem tabelka wartości logicznych implikacji wygląda następująco:

$$\begin{array}{c\vert c\vert c}p&q&p\Rightarrow q\\ \hline 1&1&1\\ 0&1&1\\ 0&0&1\\ 1&0&0\end{array}$$

Dlatego na przykład $(0\Rightarrow 0)=1$. 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ę $p\Rightarrow q$ możemy odczytywać na wiele równoważnych sposobów:

1. ``$q$ pod warunkiem, że $p$''
2. ``$q$ wtedy, gdy $p$''
3. ``$p$ tylko wtedy, gdy $q$''
4. ``$p$ jest warunkiem dostatecznym do tego, że $q$''
5. ``$q$ jest warunkiem koniecznym do tego, że $p$''

Przykład. Niech $n$ oznacza pewną liczbę naturalną. Rozważmy zdanie:

(A) Jeśli $\overbrace{\mbox{$n$\ jest podzielne przez $4$}}^{\mbox{warunek $p$}}$, to $\overbrace{\mbox{$n$\ jest podzielne przez $2$}}^{\mbox{warunek $q$}}$.

Zdanie to jest implikacją $p\Rightarrow q$. Jest ono prawdziwe niezależnie od tego, jaką konkretnie liczbą naturalną jest $n$. Innymi słowy, w każdej sytuacji jeśli zachodzi warunek $p$, to zachodzi warunek $q$. Nie ma więc takiej sytuacji, że zachodzi warunek $p$, zaś nie zachodzi warunek $q$. Dlatego do tego, by zachodził warunek $p$ konieczne jest, by zachodził warunek $q$.

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

$\Rightarrow$

Przykładem twierdzenia jest (A). Założeniem jest tu stwierdzenie, że $n$ jest liczbą naturalną podzielną przez $4$, tezą zaś stwierdzenie, że $n$ jest podzielne przez $2$.

Niektóre twierdzenia matematyczne sa oczywiste, nazywamy je wtedy aksjomatami lub pewnikami. Zazwyczaj jednak twierdzenia wymagają uzasadnienia czyli dowodu.

Mówimy, że dany warunek $q$ wynika z założeń (przesłanek) $p$, gdy w każdej sytuacji, w której $p$ jest prawdziwe, również $q$ 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 $n$ jest podzielna przez liczbę całkowitą $m$ (symbolicznie: $m\mid n$), gdy $n=m\cdot k$ dla pewnej liczby całkowitej $k$.^1.1

Odwołując się do definicji możemy sprawdzić, że np. liczba $n=72$ jest podzielna przez $m=9$ (świadczy o tym liczba $k=8$). Podobnie, $n=0$ jest podzielna przez każdą liczbę całkowitą $m$ (świadczy o tym liczba $k=0$). W szczególności, liczba $0$ jest podzielna przez $0$ (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 $n$ jest podzielna przez $4$. [ założenie]
2. Znaczy to, że $n=4\cdot k$ dla pewnej liczby całkowitej $k$. [odwołanie do definicji]
3. $4=2\cdot 2$ [odwołanie do znanego faktu]
4. Dlatego $n=2\cdot 2\cdot k$. [wniosek z 2. i 3.]
5. Niech $k'=2\cdot k$. Wtedy $n=2\cdot k'$. [wniosek z 4.]
6. Na mocy definicji, $n$ jest podzielna przez $2$. [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ą $n$ podzielną przez $4$ (punkt 1. dowodu). Od tego momentu symbol $n$ oznaczał w dowodzie cały czas tę ustaloną liczbę naturalną. W punkcie 2. dowodu wprowadziliśmy liczbę całkowitą $k$, a następnie w punkcie 5. liczbę całkowitą $k'$. 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 $x$ jest liczbą rzeczywistą dodatnią taką, że $x^2=2$, to $x$ nie jest wymierna.

Dowód Nie wprost. Załóżmy, że $x$ jest dodatnią liczbą rzeczywistą taką, że $x^2=2$. Przypuśćmy (nie wprost), że $x$ jest wymierna. Możemy więc przedstawić $x$ w postaci nieskracalnego ułamka $x={m\over n}$ dla pewnych dodatnich liczb naturalnych $m$ i $n$. Skoro $x^2=2$, to $2={m^2\over n^2}$, czyli

$$(*)\ \ 2n^2=m^2.$$

Liczba $m$ jest więc parzysta (czyli podzielna przez $2$). Dlatego (na mocy definicji) jest postaci $m=2\cdot k$ dla pewnej liczby całkowitej $k$. Stąd dostajemy, że $2n^2=m^2=2\cdot 2\cdot k^2$, czyli

$$(**)\ \ n^2=2k^2.$$

Liczba $n$ jest więc również parzysta. Zatem ułamek ${m\over n}$ jest skracalny, sprzeczność.

W wyrażeniach $p\land q,p\lor q,p\Rightarrow q$ i $p\Leftrightarrow q$ zdania $p,q$ 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

$$(*)\ \ \ (((x\cdot x)+(y\cdot y))-y)\cdot x.$$

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 $x$ i wyrażenia $((x\cdot x)+(y\cdot y))-y$. Z kolei wyrażenie $((x\cdot x)+(y\cdot y))-y$ jest różnicą wyrażenia $(x\cdot x)+(y\cdot y)$ i wyrażenia $y$.

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 $p,q,r,s,\dots$, spójników logicznych $\lor,\land\Rightarrow,\Leftrightarrow,\neg$ 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łę

$$(**)\ \ ((p\land q)\lor p)\Rightarrow(\neg p).$$

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 $(p\land q)\lor p$, zaś następnik to formuła $\neg p$. 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

$$((x\cdot x + y\cdot y) -y)\cdot x.$$

Podobnie ustala się hierarchię spójników logicznych: najpierw działa spójnik negacji $\neg$, potem działają (równorzędnie) spójniki koniunkcji $\land$ i alternatywy $\lor$, na końcu zaś działają (równorzędnie) spójniki implikacji $\Rightarrow$ i równoważności $\Leftrightarrow$. Dzięki temu możemy opuszczać niektóre nawiasy. Dlatego formułę $(**)$ możemy zapisać w formie

$$(p\land q)\lor p\Rightarrow \neg p.$$

Niech $\alpha(p,q,r)$ oznacza pewną formułę, w której jedyne zmienne zdaniowe to $p,q$ i $r$ (mówimy wówczas, że jest to formuła o zmiennych $p,q,r$). Gdy $p,q,r$ oznaczają konkretne zdania, to również $\alpha(p,q,r)$ oznacza zdanie, którego wartość logiczna zależy tylko od wartości logicznych zdań $p,q,r$ i struktury formuły. Możemy ją obliczyć zgodnie z tabelkami wartości logicznych spójników.

Przykład. Niech $\alpha(p,q)$ oznacza formułę $(p\land q)\lor p\Rightarrow \neg p$. Dla $p=1,q=0$ wartość logiczna zdania $\alpha(p,q)$ równa się:

$$\alpha(1,0)=((1\land 0)\lor 1\Rightarrow\neg 1)=(0\lor 1\Rightarrow 0)=(1\Rightarrow 0)=0.$$

W rachunku tym traktujemy spójniki jak działania na liczbach $0,1$. Wyniki naszych obliczeń możemy umieścić w tabelce wartości logicznych formuły $\alpha(p,q)$.

$$\begin{array}{c\vert c\vert c}p&q&\alpha(p,q)\\ \hline 1&1&\dots\\ 1&0&0\\ 0&1&\dots\\ 0&0&\dots\end{array}$$

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 $x$ jest jakąś liczbą rzeczywistą. Równość algebraicznych wyrażeń:

$$(x+1)\cdot(x-1)=x^2$$

jest po prostu skróconym sposobem napisania zdania:

Iloczyn liczby $x$ powiększonej o jeden i liczby $x$ pomniejszonej o jeden równa się kwadratowi liczby $x$.

Podobnie zdanie:

Liczba $x$ minus trzy jest równa liczbie uzyskanej przez pomnożenie liczby $x$ przez pierwiastek kwadratowy z liczby ($x$ plus jeden).

możemy zapisać skrótowo jako:

$$x-3=x\cdot\sqrt{x+1}.$$

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 $x$. Nazywamy je wtedy tożsamościami. Przykłady tożsamości to

$$(x-y)(x+y)=x^2-y^2,$$

$$(x+y)^2=x^2+2xy+y^2.$$

Tożsamościom w algebrze w rachunku zdań odpowiadają tautologie.

Definicja 1..1   Mówimy, że formuła $\alpha(p,q,r,\dots)$ jest tautologią rachunku zdań (lub krótko: tautologią), gdy jest zdaniem prawdziwym dla dowolnych zdań $p,q,r,\dots$

Uwaga 1..2   Formuła $\alpha(p,q,r,\dots)$ jest tautologią wtedy i tylko wtedy, gdy ma wartość logiczną $1$ dla wszystkich układów wartości logicznych zmiennych $p,q,r,\dots$

Poniżej podajemy przykłady tautologii. Niektóre z nich mają w logice tradycyjne nazwy.
$p\lor\neg p$ (prawo wyłączonego środka)
$p\Leftrightarrow p$
$\neg(p\land\neg p)$ (prawo sprzeczności, w klasycznej logice wyrażano je mówiąc: ``nie może być tak, że prawdą jest równocześnie zdanie $p$ i jego negacja'')
$p\Leftrightarrow\neg(\neg p)$ (prawo podwójnej negacji)
$[(p\Rightarrow q)\land(q\Rightarrow r)]\Rightarrow(p\Rightarrow r)$ (prawo przechodniości implikacji)
$(p\Rightarrow q)\Leftrightarrow(\neg q\Rightarrow\neg p)$ (prawo transpozycji, zwane też prawem kontrapozycji)
$\neg(p\land q)\Leftrightarrow\neg p\lor \neg q$ i $\neg(p\lor q)\Leftrightarrow\neg p\land \neg q$ (prawa de Morgana)
$\neg(p\Rightarrow q)\Leftrightarrow p\land\neg q$
$(p\Leftrightarrow q)\Leftrightarrow(p\Rightarrow q)\land(q\Rightarrow p)$

Przykład Niech $\alpha(p,q)=(p\Rightarrow p\lor q)$. Udowodnimy, że $\alpha(p,q)$ jest tautologią.

Sposób 1. Wprost. Sporządzamy tabelkę wartości logicznych formuły $\alpha$.

$$\begin{array}{c\vert c\vert c\vert c}p&q&p\lor q&p\Rightarrow p\lor q\\ \hline 1&1&1&1\\ 1&0&1&1\\ 0&1&1&1\\ 0&0&0&1\end{array}$$

Z tabelki wartości logicznych formuły $\alpha$ widzimy, że dla wszystkich wartości logicznych zmiennych $p,q$ wartość $\alpha(p,q)$ równa się $1$. Na mocy uwagi 1.2 $\alpha(p,q)$ jest więc tautologią.

Sposób 2. Nie wprost. Oznaczmy przez $A$ zdanie:

$p\Rightarrow p\lor q$ jest tautologią.

Przypuśćmy nie wprost, że zdanie to jest fałszywe, tzn. prawdziwe jest następujące zdanie $\neg A$:

$p\Rightarrow p\lor q$ nie jest tautologią.

Na mocy definicji tautologii znaczy to, że dla pewnych zdań $p$ i $q$ mamy

$$(p\Rightarrow p\lor q)=0.$$

Implikacja jest fałszywa tylko w przypadku, gdy poprzednik jest prawdziwy, zaś następnik falszywy. Dlatego dla konkretnych już w tym momencie zdań $p,q$ dostajemy $p=1$ i $p\lor q=0$. Alternatywa $p\lor q$ jest fałszywa tylko wtedy, gdy oba jej człony są fałszywe. Stąd dostajemy w szczególności, że $p=0$. Wnioskujemy więc, że zarówno $p=1$, jak i $p=0$, sprzeczność.