1. 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$.

$\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:

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

Zdanie to jest implikacją $p\Rightarrow q$. $q$ jest tu warunkiem koniecznym do $p$, gdyż jeśli $q$ jest fałszem (tzn. liczba $n$ nie dzieli się przez $2$), to również warunek $p$ nie zachodzi (tzn. liczba $n$ nie jest podzielna przez $4$). Zdanie to możemy równoważnie przeformułować na każdy z podanych wyżej 5 sposobów.

$\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}$$

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$^1.1

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ść. Uzyskana sprzeczność dowodzi, że nasze przypuszczenie, że $A$ jest fałszywe, nie jest prawdą. Datego $A$ jest prawdziwe.

W rozumowaniu powyższym skorzystaliśmy z tautologii $(\neg A\Rightarrow 0)\Rightarrow A$. Przypomnijmy, że $0$ może oznaczać dowolne zdanie fałszywe, w naszym przypadku zdanie ``$p=1$ i $p=0$''.

Rozumowanie przeprowadzone drugim sposobem jest przykładem dowodu nie wprost (inaczej: dowodu przez sprowadzenie do sprzecznosci). W dowodzie takim zakładamy, ze dowodzona teza $A$ nie zachodzi i staramy się wywnioskować sprzeczność (tzn. dowodzimy $\neg A\Rightarrow 0$). Gdy to się nam uda, na mocy tautologii $(\neg A\Rightarrow 0)\Rightarrow A$ możemy wywnioskować, że nasza teza $A$ jest prawdziwa. Oczywiście w praktyce nie przeprowadzamy dowodu tak szczegółowo.