Logika i teoria mnogości/Wykład 2: Rachunek zdań

Wprowadzenie

Logika zdaniowa jest językiem, który pozwala opisywać zależności pomiędzy zdaniami. Przykładem może być zdanie:

Jeśli Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{n}} jest liczbą pierwszą to Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{n}} jest liczbą nieparzystą lub Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{n}} jest równe 2.

W powyższym zdaniu spójniki jeśli [..] to, lub mówią o związkach które zachodzą pomiędzy zdaniami:

1. Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{n}} jest liczbą pierwszą,
2. Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{n}} jest liczbą nieparzystą,
3. Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{n}} jest równe 2.

Oznaczmy powyższe zdania przez $p,q,r$ (w takiej właśnie kolejności). Używając symboli, które zwyczajowo odpowiadają potocznemu rozumieniu spójników jeśli [..] to, lub oraz powyższych oznaczeń, otrzymamy formułę

$p\Rightarrow (q\vee r).$

Jeśli powyższą formułę uznamy za prawdziwą, to może nam ona posłużyć do otrzymania nowych wniosków. Na przykład, jeśli o jakiejś liczbie Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{n}} będziemy wiedzieć, że jest liczbą pierwszą oraz że nie jest nieparzysta, to klasyczny rachunek zdań pozwoli nam formalnie wywnioskować fakt, że liczba Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{n}} jest równa 2. Podsumowując, jeśli uznamy za prawdziwe następujące zdania:

1. $p\Rightarrow (q\vee r)$,
2. $p$,
3. $\mathrm{\neg }q$ (przez $\mathrm{\neg }$ oznaczamy negację)

to zgodnie z klasycznym rachunkiem zdań powinniśmy uznać za prawdziwe zdanie Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{r}} , czyli Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{n}} jest równe 2. Powyższy schemat wnioskowania można również opisać formułą

$((p\Rightarrow (q\vee r))\wedge p\wedge (\mathrm{\neg }q))\Rightarrow q.$

W powyższej formule symbol $\wedge$ odpowiada spójnikowi Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{i}} (oraz).

Dzięki rachunkowi zdań możemy precyzyjnie opisywać schematy wnioskowania i zdania złożone oraz oceniać ich prawdziwość.

Język logiki zdaniowej

Zaczniemy od definicji języka logiki zdaniowej. Składa się on z formuł zdefiniowanych następująco:

Definicja 2.1 [Formuła logiki zdaniowej]

1. zmienna zdaniowa jest formułą (zmienne zdaniowe oznaczamy zwykle literami alfabetu rzymskiego np. $p,q,r$),
2. jeśli $\varphi$ oraz $\psi$ są formułami to $(\varphi \Rightarrow \psi )$ jest formułą (spójnik $\Rightarrow$ nazywamy implikacją),
3. jeśli $\varphi$ jest formułą to $\mathrm{\neg }\varphi$ jest formułą (spójnik $\mathrm{\neg }$ nazywamy negacją),
4. nic innego nie jest formułą.

Powyższa definicja mówi, że formułami nazywamy te napisy, które dają się skonstruować ze zmiennych zdaniowych przy pomocy spójników $\Rightarrow$ oraz $\mathrm{\neg }$.

Uwaga 2.2.

Zgodnie z powyższą definicją nie jest formułą napis $p\Rightarrow q$, gdyż brakuje w nim nawiasów. Pomimo, iż poprawnie powinniśmy napisać $(p\Rightarrow q)$ możemy przyjąć że nie będzie konieczne pisanie nawiasów, jeśli nawiasy można jednoznacznie uzupełnić. Często przyjmuje się również prawostronne nawiasowanie dla implikacji, czyli formuła $p\Rightarrow q\Rightarrow r$ jest domyślnie nawiasowana w następujący sposób $(p\Rightarrow (q\Rightarrow r))$.

Przykład 2.3 Poniższe napisy nie są formułami

• $p\Rightarrow \Rightarrow q$,

• $\mathrm{\neg }\mathrm{\neg }\mathrm{\neg }$,

• ten napis na pewno nie jest formułą,

• $(p\Rightarrow \mathrm{\neg }q))$.

Poniższe napisy są formułami

• $(p\Rightarrow (r\Rightarrow q))$,

• $\mathrm{\neg }\mathrm{\neg }\mathrm{\neg }q$,

• $(p\Rightarrow \mathrm{\neg }q)$.

Ćwiczenie 2.1

{{{3}}}

Uwaga 2.4.

Język logiki zdaniowej można równoważnie zdefiniować nie używając nawiasów za pomocą tzw. Odwrotnej Notacji Polskiej.

Aksjomatyka Klasycznego Rachunku Zdań

Podobnie jak nie wszystkie zdania języka naturalnego mają sens, nie wszystkie formuły opisują prawdziwe schematy wnioskowania lub zdania, które bylibyśmy skłonni uznać za prawdziwe. W tym rozdziale skupimy się na tym, które spośród wszystkich formuł zdaniowych wyróżnić jako prawdziwe.

Aksjomaty

Wielu matematyków zgadza się dzisiaj co do tego, że zdania pasujące do poniższych schematów powinny być uznane za prawdziwe:

Definicja 3.1 Aksjomaty klasycznego rachunku zdań

1. $(\varphi \Rightarrow (\psi \Rightarrow \varphi ))$ (formuła ta jest nazywana aksjomatem K),
2. $(\varphi \Rightarrow (\nu \Rightarrow \psi )\Rightarrow ((\varphi \Rightarrow \nu )\Rightarrow (\varphi \Rightarrow \nu ))$ (formuła ta jest nazywana aksjomatem S),
3. $(\mathrm{\neg }\varphi \Rightarrow \psi )\Rightarrow (\mathrm{\neg }\varphi \Rightarrow \mathrm{\neg }\psi )\Rightarrow \varphi$ (tzw. schemat dowodu niewprost)

Zdania pasujące do powyższych schematów to wszystkie zdania, które można otrzymać, podstawiając w miejsce $\varphi ,\nu ,\psi$ dowolne formuły.

Reguła dowodzenia

Przyglądnijmy się teraz jak posługujemy się implikacją we wnioskowaniu. W przykładzie z początku wykładu implikacja odpowiadała konstrukcji językowej:

jeśli $\varphi$ to $\psi$.

W takim przypadku, jeśli akceptujemy powyższą implikacjię jako zdanie prawdziwe oraz jeśli zdanie $\varphi$ jako prawdziwe, to powinniśmy także zaakceptować $\psi$. Przedstawiony sposób wnioskowania nosi nazwę reguły Modus Ponens (nazywana też regułą odrywania, często będziemy używać skrótu MP) i jest skrótowo notowany w poniższy sposób

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \frac{\phi \Rightarrow \psi, \phi} \psi}. }

Reguła modus ponens posłuży nam do uzupełniania zbioru aksjomatów o ich konsekwencje logiczne, które również uznamy za prawdziwe. Aby precyzyjnie zdefiniować zbiór wszystkich konsekwencji logicznych aksjomatów, definiujemy poniżej pojęcie dowodu.

Definicja 3.2

Ciąg formuł ${\varphi }_0,\dots ,{\varphi }_n$ jest dowodem formuły $\psi$ wtedy i tylko wtedy, gdy:

1. ${\varphi }_n$ jest formułą $\psi$,
2. dla każdego $i\le n$ formuła ${\varphi }_i$ jest aksjomatem lub istnieją $j,k<i$ takie, że formuła ${\varphi }_i$ jest wynikiem zastosowania reguły modus ponens do formuł ${\varphi }_j,{\varphi }_k$.

W drugim punkcie powyższej definicji, jeśli formuła ${\varphi }_i$ nie jest aksjomatem (a więc powstaje przez zastosowanie MP), to formuły ${\varphi }_j,{\varphi }_k$ muszą pasować do przesłanek reguły MP, a więc ${\varphi }_j$ musi być postaci ${\varphi }_k\Rightarrow {\varphi }_i$ lub ${\varphi }_k$ postaci ${\varphi }_j\Rightarrow {\varphi }_i$.

Definicja 3.3

Formułę nazywamy twierdzeniem klasycznego rachunku zdań jeśli istnieje jej dowód z aksjomatów klasycznego rachunku zdań 3.1

Przykład

Zastanówmy się na formułą postaci $\varphi \Rightarrow \varphi$. Intuicja podpowiada, że taką formułę powinniśmy uznać za prawdziwą. Nie pasuje ona jednak do żadnego ze schematów aksjomatów 3.1. Formuła ta jest jednak twierdzeniem klasycznego rachunku zdań. Poniżej przedstawiamy jej dowód. Aby łatwiej dopasować formuły do schematów aksjomatów, użyliśmy nawiasów kwadratowych dla nawiasów, które pochodzą ze schematów.

1. $[\varphi \Rightarrow [(q\Rightarrow \varphi )\Rightarrow \varphi )]\Rightarrow [[\varphi \Rightarrow (q\Rightarrow \varphi )]\Rightarrow [\varphi \Rightarrow \varphi ]]$ formuła ta jest aksjomatem zgodnym ze schematem S,
2. $\varphi \Rightarrow [(q\Rightarrow \varphi )\Rightarrow \varphi ]$ aksjomat zgodny ze schematem K,
3. $(\varphi \Rightarrow (q\Rightarrow \varphi ))\Rightarrow (\varphi \Rightarrow \varphi )$ z modus ponens z formuł 1 i 2,
4. $\varphi \Rightarrow [q\Rightarrow \varphi ]$ aksjomat zgodny ze schematem K,
5. $(\varphi \Rightarrow \varphi )$ z modus ponens z formuł 3 i 4.

Podsumowanie

Klasyczny rachunek zdań, czyli zbiór formuł które uznajemy za prawdziwe, zdefiniowaliśmy, wyróżniając pewne formuły jako aksjomaty 3.1 i dorzucając do nich wszystkie formuły, które dają się z nich wywnioskować przy pomocy reguły Modus Ponens. Warto zwrócić uwagę, że pomimo tego, iż w doborze aksjomatów i reguł wnioskowania kierowaliśmy się intuicyjnym pojęciem implikacji i konsekwencji, klasyczny rachunek zdań jest teorią syntaktyczną, zbiorem pewnych napisów o których znaczeniu nie musimy nic mówić.

Uwaga 3.4

Warto przyglądnąć się przyjętym aksjomatom i zastanowić się jakim zdaniom odpowiadają i czy rzeczywiście bylibyśmy skłonni uznać je za prawdziwe. Pomocne może być interpretowanie formuł postaci $\varphi \Rightarrow (\nu \Rightarrow \psi )$ jako „jeśli prawdziwe jest $\varphi$ i prawdziwe jest $\nu$ to prawdziwe jest $\psi$”. W kolejnych rozdziałach przekonamy się, że taka interpretacja jest uzasadniona.

Matryca boolowska

W poprzednim rozdziale zdefiniowaliśmy klasyczny rachunek zdań jako teorię aksjomatyczną. Jeśli pozwolimy sobie na używanie skończonych zbiorów i funkcji, możemy równoważnie zdefiniować klasyczny rachunek zdań za pomocą tzw. matrycy boolowskiej.

Definicja 4.1

Dwuelementową matrycą boolowską nazywamy zbiór dwuelementowy $\mathbb{𝔹}=\{0,1\}$ w którym 1 jest wyróżnioną wartością prawdy, wraz z dwoma funkcjami odpowiadającymi za interpretacje spójników $\Rightarrow$ oraz $\mathrm{\neg }$ zdefiniowanymi następująco

$\Rightarrow$ 0 1 0 1 1 1 0 1

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{p}} $\mathrm{\neg }p$ 0 1 1 0

$\text{(4.1)}$

Definicja 4.2

Wartościowaniem nazywamy funkcję, która przypisuje zmiennym zdaniowym elementy zbioru $\mathbb{𝔹}$. Wartościowanie zmiennych można rozszerzyć na wartościowanie formuł interpretując spójniki $\Rightarrow$ oraz $\mathrm{\neg }$ jako funkcje zgodnie z tabelami 4.1.

Przykład 4.3

Niech $v$ będzie wartościowaniem zmiennych takim, że $v(p)=0,v(q)=1,v(r)=0$. Wtedy

• formuła $q\Rightarrow p$ jest wartościowana na 0 (będziemy to zapisywać jako $v(q\Rightarrow p)=0$),

• formuła $r\Rightarrow (q\Rightarrow p)$ jest wartościowana na 1 (czyli $v(r\Rightarrow (q\Rightarrow p))=1$),

• formuła $\mathrm{\neg }p\Rightarrow r$ jest wartościowana na 0 (czyli $v(\mathrm{\neg }p\Rightarrow r)=0$).

Ćwiczenie 4.1

{{{3}}}

Ćwiczenie 4.2

{{{3}}}

Twierdzenie o pełności

Zauważmy, że istnieją formuły, które dla każdego wartościowania zmiennych zdaniowych, zawsze przyjmują wartość 1 (np. $p\Rightarrow p$). Takie formuły będziemy nazywać tautologiami.

Ćwiczenie 4.3

-

Nie przez przypadek pierwsze trzy formuły z poprzedniego zadania odpowiadają aksjomatom klasycznego rachunku zdań 3.1. Okazuje się że istnieje ścisły związek pomiędzy tautologiami a twierdzeniami klasycznego rachunku zdań. Mówi o tym ważny wynik Emila Posta

Emil Leon Post (1897-1954)
Zobacz biografię

Twierdzenie 4.4

Post 1921 Formuła jest twierdzeniem klasycznego rachunku zdań wtedy i tylko wtedy kiedy jest tautologią.

Dowód powyższego twierdzenia jest przedstawiony na wykładzie Logika dla informatyków Dzięki powyższemu twierdzeniu możemy w miarę łatwo stwierdzać, czy dana formuła jest twierdzeniem klasycznego rachunku zdań, sprawdzając, czy jest tautologią, co wymaga rozważenia jedynie skończonej (chociaż często niemałej) liczby wartościowań. Co więcej, mamy też możliwość dowodzenia, że jakaś formuła nie jest twierdzeniem klasycznego rachunku zdań. Uzasadnienie, że nie da się jakiejś formuły udowonić z aksjomatów poprzez stosowanie reguły MP wydaje się zadaniem trudnym, znacznie łatwiej jest poszukać wartościowania, które wartościuje formułę na 0 (znowu wystarczy sprawdzić jedynie skończenie wiele wartościowań).

Ćwiczenie 4.4

{{{3}}}

Inne spójniki

Do tej pory jedynymi rozważanymi spójnikami była implikacja i negacja. W analogiczny sposób do 4.1 możemy wprowadzać kolejne spójniki. Często używane spójniki to koniunkcja (spójnik i) oznaczana przez $\wedge$ oraz alternatywa (spójnik lub) oznaczana przez $\vee$, które będziemy interpretować w następujący sposób:

$\wedge$ 0 1  0   0   0   1   0   1

$\vee$ 0 1  0   0   1   1   1   1

$\text{(4.2)}$

Zgodnie z intuicją koniunkcja $\varphi \wedge \psi$ jest wartościowana na 1 wtedy i tylko wtedy, gdy zarówno $\varphi$ jak i $\psi$ są wartościowane na 1. Alternatywa $\varphi \vee \psi$ jest wartościowana na 1, jeśli przynajmniej jedna z formuł $\varphi ,\psi$ jest wartościowana na 1.

Definicja 4.5

Formuły $\varphi$ oraz $\psi$ są równoważne (oznaczamy ten fakt przez $\varphi \equiv \psi$ wtedy i tylko wtedy, gdy dla każdego wartościowania formuła $\varphi$ przyjmuje tą samą wartość co formuła $\psi$.

Ćwiczenie 4.5

Udowodnij, że następujące formuły są równoważne

1. $\varphi \vee \psi \equiv \mathrm{\neg }\varphi \Rightarrow \psi$
2. $\varphi \wedge \psi \equiv \mathrm{\neg }(\varphi \Rightarrow \mathrm{\neg }\psi )$

Rozwiązanie

1. Lewa strona jest fałszywa jedynie, gdy $\varphi$ oraz $\psi$ są wartościowane na 0. Prawa strona jest fałszywa wtedy i tylko wtedy, kiedy $\mathrm{\neg }\varphi$ jest wartościowane na 1 oraz $\psi$ jest wartościowane na 0 (to jedyna możliwość aby implikacja była fałszywa). Wobec tego prawa strona jest fałszywa wtedy i tylko wtedy, kiedy $\varphi$ oraz $\psi$ są wartościowane na 0, a więc jest równoważna lewej.

2. Lewa strona jest prawdziwa jedynie, gdy $\varphi$ oraz $\psi$ są wartościowane na 1. Prawa strona jest prawdziwa wtedy i tylko wtedy, kiedy $\mathrm{\neg }(\varphi \Rightarrow \mathrm{\neg }\psi )$ jest wartościowane na 1, więc wtedy gdy $(\varphi \Rightarrow \mathrm{\neg }\psi )$ jest wartościowane na 0. To z kolei zdarzyć się może jedynie, gdy $\varphi$ jest wartościowane na 1 i $\mathrm{\neg }\psi$ na 0, a więc wtedy, gdy zarówno $\varphi$ jak i $\psi$ są wartościowane na 1. Wobec tego obie formuły są równoważne.

Równie dobrym rozwiązaniem jest sprawdzenie wszystkich możliwości wartościowań i porównanie wyników.

Z powyższego zadania wynika, że każdą formułę w której występują spójniki $\wedge$ lub $\vee$ można zastąpić równoważną formułą, w której jedynymi spójnikami są $\Rightarrow$ oraz $\mathrm{\neg }$. Tak naprawdę więc nowe spójniki nie wprowadzają nic nowego poza użytecznymi skrótami w zapisywaniu formuł. Aby się oswoić z własnościami spójników, prześledzimy szereg ich praw.

Ćwiczenie 4.6

Udowodnij następujące równoważności

1. $\mathrm{\neg }\mathrm{\neg }p\equiv p$,
2. $p\Rightarrow q\equiv \mathrm{\neg }p\vee q$,
3. $p\Rightarrow (q\Rightarrow r)\equiv (p\wedge q)\Rightarrow r$,
4. $\mathrm{\neg }(p\wedge q)\equiv \mathrm{\neg }p\vee \mathrm{\neg }q$,
5. $\mathrm{\neg }(p\vee q)\equiv \mathrm{\neg }p\wedge \mathrm{\neg }q$,
6. $p\wedge (q\vee r)\equiv (p\wedge q)\vee (p\wedge r)$,
7. $p\vee (q\wedge r)\equiv (p\vee q)\wedge (p\vee r)$,
8. $(p\Rightarrow q)\Rightarrow (\mathrm{\neg }p\Rightarrow \mathrm{\neg }q)$.

Rozwiązanie

Przedstawiamy przykładowe dowody kilku pierwszych równoważności.

1. Jeśli Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{p}} jest wartościowane na 1, to zgodnie z tabelą dla negacji 4.1 $\mathrm{\neg }p$ jest wartościowane na 0 i $\mathrm{\neg }\mathrm{\neg }p$ jest wartościowane na 1. Jeśli Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{p}} jest wartościowane na 0 to, $\mathrm{\neg }p$ jest wartościowane na 1 i $\mathrm{\neg }\mathrm{\neg }p$ jest wartościowane na 0. Formuły przyjmują te same wartości dla każdego wartościowania, więc są równoważne.

2. Jedyną możliwością, aby lewa strona była fałszywa jest, aby Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{p}} było wartościowane na 1, a Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{q}} na 0. Prawa stona jest fałszywa jedynie, gdy $\mathrm{\neg }p$ oraz Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{q}} są wartościowane na 0. Czyli prawa strona jest fałszywa, jedynie gdy Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{p}} jest wartościowane na 1 i Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{q}} na 0. Formuły są więc równoważne.

3. Analogicznie do poprzedniego punktu łatwo się przekonać, że jedynym wartościowaniem, które falsyfikuje lewą stronę, jest takie, które wartościuje Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{p}} i Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{q}} na 1 oraz Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{r}} na 0. Tą samą własność ma formuła po prawej stronie, więc formuły są równoważne.

4. Przykład rozwiązania przez rozważenie wszystkich możliwości

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{p}}	Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{q}}	Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{p} \wedge \textnormal{q}}	$\mathrm{\neg }(p\wedge q)$	$\mathrm{\neg }p$	$\mathrm{\neg }q$	$\mathrm{\neg }p\vee \mathrm{\neg }q$
0	0	0	1	1	1	1
0	1	0	1	1	0	1
1	0	0	1	0	1	1
1	1	1	0	0	0	0

W pierwszych dwóch kolumnach są zapisane wartościowania zmiennych Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{p}} i Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{q}} , a w pozostałych odpowiadające im wartościowania formuł zbudowanych z tych zmiennych. Ponieważ kolumna 4 i 7 są identyczne to formuły z zadania są równoważne.

5. W równoważności z poprzedniego punktu, podstawiąjąc za Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{p}} formułę $\mathrm{\neg }p$ oraz za Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{q}} formułę $\mathrm{\neg }q$ otrzymamy równoważność

$\mathrm{\neg }(\mathrm{\neg }p\wedge \mathrm{\neg }q)\equiv \mathrm{\neg }\mathrm{\neg }p\vee \mathrm{\neg }\mathrm{\neg }q.$

Stosując dwukrotnie równoważność z pierwszego punktu do prawej strony otrzymujemy

$\mathrm{\neg }(\mathrm{\neg }p\wedge \mathrm{\neg }q)\equiv p\vee q.$

Negując tą równoważność obustronnie otrzymamy

$\mathrm{\neg }\mathrm{\neg }(\mathrm{\neg }p\wedge \mathrm{\neg }q)\equiv \mathrm{\neg }(p\vee q).$

Stosując równoważność z pierwszego punktu do lewej strony otrzymamy szukaną równoważność.

Ćwiczenie 4.7

Sprawdź które z następujących formuł są tautologiami

1. $((p\vee r)\wedge (q\vee \mathrm{\neg }r))\Rightarrow (p\vee q)$,
2. $(p\vee q)\Rightarrow ((p\vee r)\wedge (q\vee \mathrm{\neg }r))$,
3. $((p\wedge r)\vee (q\wedge \mathrm{\neg }r))\Rightarrow (p\wedge q)$,
4. $(p\wedge q)\Rightarrow ((p\wedge r)\vee (q\wedge \mathrm{\neg }r))$.

Rozwiązanie

1. Spróbujmy znaleźć wartościowanie, które falsyfikuje tą formułę. Skoro implikacja ma być fałszywa, to formuła $(p\vee q)$ (czyli następnik) musi być fałszywa. Tak jest tylko wtedy, kiedy zarówno Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{p}} jak i Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{q}} są fałszywe. Zobaczmy co się wtedy dzieje z poprzednikim implikacji, czyli formułą

$(p\vee r)\wedge (q\vee \mathrm{\neg }r).$

Jeśli teraz ustalimy Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{r}} na fałsz, to $(p\vee q)$ będzie fałszywe, a jeśli ustalimy $r$ na prawdę to $(q\vee \mathrm{\neg }r)$ będzie fałszywe. W obu tych przypadkach cały poprzednik jest fałszywy. Wynika stąd, że nie da się dobrać takiego wartościowania, że poprzednik jest prawdziwy, a następnik fałszywy więc, rozważana formuła jest tautologą.

2 Formuła nie jest tautologią. Wystarczy wartościować Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{p}} i Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{r}} na prawdę i Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{q}} na fałsz.

3. Formuła nie jest tautologią. Wystarczy wartościować Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{p}} i Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{r}} na prawdę i Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{q}} na fałsz.

4. Przykład rozwiązania przez rozważenie wszystkich możliwości

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{p}}	Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{q}}	Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{r}}	Parser nie mógł rozpoznać (błąd składni): {\displaystyle (\textnormal{p} \wedge \textnormal{q})}	$(p\wedge r)$	$(q\wedge \mathrm{\neg }r)$	$(p\wedge r)\vee (q\wedge \mathrm{\neg }r)$	$(p\wedge q)\Rightarrow ((p\wedge r)\vee (q\wedge \mathrm{\neg }r))$
0	0	0	0	0	0	0	1
0	0	1	0	0	0	0	1
0	1	0	0	0	1	1	1
0	1	1	0	0	0	0	1
1	0	0	0	0	0	0	1
1	0	1	0	1	0	1	1
1	1	0	1	0	1	1	1
1	1	1	1	1	0	1	1

W kolumnie odpowiadającej badanej formule, są same 1, więc jest ona tautologią.

Binarne spójniki logiczne interpretowaliśmy jako funkcje z $\mathbb{𝔹}\times \mathbb{𝔹}\to \mathbb{𝔹}$. Nie trudno przekonać się, że takich funkcji jest dokładnie 16. Dla każdej takiej funkcji możemy dodać spójnik, który będzie interpretowany dokładnie jako ta funkcja. W poniższej tabeli zamieszczamy wszystkie takie funkcje wraz ze zwyczajowymi oznaczeniami odpowiadających im spójników.

Definicja 4.6

W poniższej tabeli przedstawiamy wszystkie spójniki binarne.

Numer funkcji	$p=0$ $q=0$	$p=0$ $q=1$	$p=1$ $q=0$	$p=1$ $q=1$
0	0	0	0	0		$F$
1	0	0	0	1		$\wedge$
2	0	0	1	0		$\mathrm{\neg }(p\Rightarrow q)$
3	0	0	1	1		Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{p}}
4	0	1	0	0		$\mathrm{\neg }(q\Rightarrow p)$
5	0	1	0	1		Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{q}}
6	0	1	1	0		$XOR$
7	0	1	1	1		$\vee$
8	1	0	0	0		$NOR$
9	1	0	0	1		$\iff$
10	1	0	1	0		$\mathrm{\neg }q$
11	1	0	1	1		$q\Rightarrow p$
12	1	1	0	0		$\mathrm{\neg }p$
13	1	1	0	1		$p\Rightarrow q$
14	1	1	1	0		$NAND$
15	1	1	1	1		$T$

Spójnik binarny $\circ$ będziemy nazywać przemiennym, jeśli zachodzi następująca równoważność

$p\circ q\equiv q\circ p\text{(4.3)}$

Ćwiczenie 4.8

Sprawdź następujące równoważności

1. $xNANDy\equiv \mathrm{\neg }(x\wedge y)$
2. $xNORy\equiv \mathrm{\neg }(x\vee y)$
3. $xXORy\equiv \mathrm{\neg }(x\iff y)$

Rozwiązanie

Powyższe równoważności wynikają natychmiast z porównania odpowiednich wierszy w tabeli definicji spójników.

Ćwiczenie 4.9

-

Spójnik binarny $\circ$ będziemy nazywać łącznym jeśli zachodzi

następująca równoważność

$p\circ (q\circ r)\equiv (p\circ q)\circ r.\text{(4.4)}$

Jeśli spójnik $\circ$ jest łączny to dowolne dwie formuły, które są zbudowane jedynie ze spójników $\circ$ są równoważne, jeśli występuje w nich tyle samo spójników. Dlatego dla łącznych spójników binarnych pomija się często nawiasy.

Ćwiczenie 4.10

-

Możemy również rozważać spójniki 3 i więcej argumentowe. Spójnik $k$-argumetowy powinien odpowiadać funkcji ${\mathbb{𝔹}}^k\to \mathbb{𝔹}$.

Przykład 4.7

W poniższej tabeli przedstawiamy przykład spójnika trójargumentowego

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{p}}	Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{q}}	Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{r}}	$\circ (p,q,r)$
0	0	0	0
0	0	1	1
0	1	0	1
0	1	1	0
1	0	0	1
1	0	1	0
1	1	0	0
1	1	1	1

Uwaga 4.1

Różnych spójników $k$-argumentowych jest dokładnie $2^{2^k}$.

Systemy funkcjonalnie pełne

Każda formuła odpowiada pewnej funkcji przekształcającej wartościowania zmiennych w niej występujących w element zbioru $\mathbb{𝔹}$. Na przykład formuła $p\Rightarrow (q\Rightarrow r)$ wyznacza funkcję $f_{p\Rightarrow (q\Rightarrow r)}$ opisaną poniższą tabelą

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{p}}	Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{q}}	Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{r}}	$f_{p{\to }_{(}q\to r)}$
0	0	0	1
0	0	1	1
0	1	0	1
0	1	1	1
1	0	0	1
1	0	1	1
1	1	0	0
1	1	1	1

Mówimy, wtedy że formuła $\varphi$ definuje funkcję $f_{\varphi }$.

Definicja 5.1

Skończony zbiór funkcji boolowskich $\mathrm{\Gamma }$ nazywamy funkcjonalnie pełnym, jeśli każdą funkcję boolowską da się zdefiniować przy pomocy formuły zbudowanej wyłącznie ze spójników odpowiadających funkcjom ze zbioru $\mathrm{\Gamma }$.

Twierdzenie 5.2

Zbiór $\{\wedge ,\vee ,\mathrm{\neg }\}$ jest funkcjonalnie pełny.

Dowód

Dla dowolnej funkcji boolowskiej skonstruujemy formułę która ją definiuje. Niech Parser nie mógł rozpoznać (nieznana funkcja „\nNat”): {\displaystyle \displaystyle k\in \nNat} oraz $f:{\mathbb{𝔹}}^k\to \mathbb{𝔹}$. W definiowanej formule będziemy używać zmiennych $p_1,\dots ,p_k$, a każdy element $(w_1,\dots ,w_k)\in {\mathbb{𝔹}}^k$ będzie odpowiadał wartościowaniu $v_w$ takiemu, że $v(p_i)=w_i$.

Niech $F$ będzie zbiorem tych argumentów, dla których funkcja $f$ przyjmuje wartość 1. Dla dowolnego elementu $x_i\in F$ skonstruujemy formułę ${\varphi }_i$ w taki sposób, aby była spełniona tylko dla wartościowania odpowiadającego elementowi $x_i$. Niech $x_i=(w_1,\dots ,w_k)$, wtedy formułę ${\varphi }_i$ definiujemy jako $l_1^i\wedge l_2^i\wedge \dots \wedge l_k^i$ gdzie

$l_j^i\{\begin{array}{ll}{p}_j,& \text{gdy }{w}_j=1;\\ \mathrm{\neg }{p}_j,& \text{gdy }{w}_j=0.\end{array}$

Łatwo sprawdzić, że formuła ${\varphi }_i$ jest spełniona tylko dla wartościowania odpowiadającego elementowi $x_i$.

Postępując w ten sposób dla każdego elementu zbioru $F$ otrzymamy formuły ${\varphi }_1,\dots {\varphi }_m$. Biorąc

${\varphi }_1\vee \dots \vee {\varphi }_m$

otrzymamy formułę która definiuje funkcję $f$, oznaczmy ją przez $\mathrm{\Phi }$. Jeśli dla wartościowania $v$ formuła $\mathrm{\Phi }$ jest spełniona to znaczy, że któraś z formuł ${\varphi }_i$ jest spełniona. Oznacza to że wartościowanie $v$ odpowiada pewnemu elementowi $x_i$ zbioru $F$, wobec tego funkcja $f(x_i)=1$ co jest zgodne z tym, że spełniona jest $\mathrm{\Phi }$. W drugą stronę załóżmy że dla pewnego elementu $a\in {\mathbb{𝔹}}^k$ mamy $f(a)=1$. Wobec tego $a\in F$. Wtedy $a$ odpowiada pewnej formule ${\varphi }_i$, która jest spełniona dla wartościowania odpowiadającego $a$. Wobec tego również cała formuła $\mathrm{\Phi }$ jest spełniona dla tego wartościowania (bo jeden z elementów alternatywy jest spełniony). Wynika stąd, że formuła $\mathrm{\Phi }$ definiuje funkcję $f$. Na koniec zauważmy jeszcze że jedynymi spójnikami występującymi w formule $\mathrm{\Phi }$ są $\mathrm{\neg },\vee ,\wedge$.

Twierdzenie 5.3

Zbiory $\{\wedge ,\mathrm{\neg }\}$, $\{\vee ,\mathrm{\neg }\}$ są funkcjonalnie pełne.

Dowód

Aby pokazać, że $\{\wedge ,\mathrm{\neg }\}$ jest funkcjonalnie pełny wystarczy pokazać, że przy pomocy spójników $\{\wedge ,\mathrm{\neg }\}$ da się zdefiniować $\vee$. Wtedy funkcjonalną pełność otrzymamy z twierdzenia 5.2. W ćwiczeniu 4.2 pokazaliśmy, że

$\mathrm{\neg }(x\vee y)=\mathrm{\neg }x\wedge \mathrm{\neg }y.$

Wobec tego

$x\vee y=\mathrm{\neg }(\mathrm{\neg }x\wedge \mathrm{\neg }y)$

a więc zdefiniowaliśmy $\vee$ przy pomocy $\mathrm{\neg },\wedge$.

Analogicznie aby pokazać funkcjonalną pełność zbioru $\{\vee ,\mathrm{\neg }\}$ zdefiniujemy $\wedge$ przy pomocy spójników $\vee ,\mathrm{\neg }$. Z ćwiczenia 4.2 mamy

$\mathrm{\neg }(x\wedge y)=\mathrm{\neg }x\vee \mathrm{\neg }y$

a więc

$x\wedge y=\mathrm{\neg }(\mathrm{\neg }x\vee \mathrm{\neg }y).$

Ćwiczenie 5.1

{{{3}}}

Twierdzenie 5.4

Zbiór $\{NOR\}$ jest funkcjonalnie pełny.

Dowód

Pokażemy, że przy pomocy $NOR$ można zdefiniować $\mathrm{\neg }$ oraz $\vee$. Wtedy z twierdzenia twierdzenia 5.3 otrzymamy tezę twierdzenia.

Łatwo sprawdzić, że

$pNORp\equiv \mathrm{\neg }.$

Wiemy, że

$pNORq\equiv \mathrm{\neg }(p\vee q).$

Wobec tego mamy również

$\mathrm{\neg }(pNORq)\equiv p\vee q.$

Możemy teraz wyrazić negację za pomocą $NOR$, otrzymamy wtedy

$(pNORq)NOR(pNORq)\equiv p\vee q.$

Ćwiczenie 5.2

{{{3}}}

Ćwiczenie 5.3

{{{3}}}

Ćwiczenie 5.4

{{{3}}}

Ćwiczenie 5.5

{{{3}}}

Ćwiczenie 5.6

{{{3}}}

Ćwiczenie 5.7

-

Postacie normalne

Definicja 6.1

Literałem nazywamy formułę która jest zmienną zdaniową lub negacją zmiennej zdaniowej.

Zauważmy, że formuła konstruowana w dowodzie twierdzenia 5.2 jest w pewnej standartowej postaci - formuła jest alternatywą formuł które są koniunkcjami literałów. Przypomnijmy, że dla $p\Rightarrow q$ zbudujemy formułę

$(p\wedge q)\vee (\mathrm{\neg }p\wedge q)\vee (\mathrm{\neg }p\wedge \mathrm{\neg }q).$

Definicja 6.2

Formuła jest w dyzjunktywnej postaci normalnej (DNF) jeśli jest alternatywą formuł które są koniunkcjami literałów. Czyli wtedy gdy jest postaci

${\varphi }_1\vee \dots \vee {\varphi }_n$

oraz każda z formuł ${\varphi }_i$ jest koniunkcją literałów, czyli jest postaci

$l_l^i\wedge \dots \wedge l_k^i$

dla pewnych literałów $l_l^i,\dots ,l_k^i$

Twierdzenie 6.3

Dla każedej formuły istnieje równoważna formuła w DNF.

Dowód

Wynika bezpośrednio z konstrukcji w dowodzie twierdzenia 5.2.

Definicja 6.4

Formuła jest w koniunktywnej postaci normalnej (CNF) jeśli jest koniunkcją formuł które są alternatywami literałów.

Twierdzenie 6.5

Dla każdej formuły istnieje równoważna formuła w CNF.

Dowód

Niech $\mathrm{\Phi }$ będzie dowolną formułą. Z twierdzenia ??Uzupelnic dnf| wynika że dla formuły $\mathrm{\neg }\mathrm{\Phi }$ istnieje dyzjunktywna postać normalna. Niech $\mathrm{\Psi }$ będzie taką formułą. Wtedy mamy

$\mathrm{\Phi }\equiv \mathrm{\neg }\mathrm{\Psi }.$

Stosując wielokrotnie prawa de'Morgana dla formuły $\mathrm{\neg }\mathrm{\Psi }$ otrzymamy formułę w koniunktywnej postaci normalnej. Indukcyjny dowód tego faktu pomijamy.

Ćwiczenie 6.1

{{{3}}}

Ćwiczenie 6.2

{{{3}}}

Spełnialność

Spośród wszystkich formuł wyróżnimy też zbiór formuł spełnialnych.

Definicja 6.6

Formuła jest spełnialna jeśli istenieje takie wartościowanie które wartościuje tą formułę na 1.

Formuły spełnialne są w ścisłym związku z tautologiami.

Twierdzenie 6.7

Formuła $\varphi$ jest tautologią wtedy i tylko wtedy kiedy formuła $\mathrm{\neg }\varphi$ nie jest spełnialna.

Dowód

Przypuśćmy, że formuła $\varphi$ jest tautologią. Wtedy dla każdego wartościowania Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{v}} mamy $v(\varphi )=1$. Stąd otrzymujemy że dla każdego wartościowania Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{v}} mamy $v(\mathrm{\neg }\varphi )=0$, a więc nie istnieje wartościwanie, które spełnia $\mathrm{\neg }\varphi$, czyli formuła ta nie jest spełnialna.

Przypuśćmy, że formuła $\mathrm{\neg }\varphi$ nie jest spełnialna, czyli nie istnieje wartościowanie Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{v}} takie, że $v(\mathrm{\neg }\varphi )=0$. Wynika stąd, że dla każdego wartościowania mamy $v(\varphi )=1$, a więc $\varphi$ jest tautologią.

Ćwiczenie 6.3

{{{3}}}

Formuły z powyższego zadania, poza tym że są w koniunktywnej postaci normalnej, to jeszcze występujące w nich klauzule mają dokładnie dwa literały. Problem spełnialności takich formuł jest nazywany w literaturze problemem 2SAT. Dla takich formuł istnieją szybkie algorytmy pozwalające ocenić ich spełnialność. Dopuszczanie klauzul o długości 3, bardzo komplikuje problem. Do dziś nie wiadomo czy dla takich formuł istnieją szybkie algorytmy oceniające spełnialność. Więcej na ten temat można się dowiedzieć z wykładu Teoria złożoności.

Logika intuicjonistyczna

Niektórzy logicy mają wątpliwości co do tego czy powinniśmy przyjmować schemat dowodu nie wprost jako aksjomat. Poddanie w wątpliwość tego aksjomatu doprowadziło do powstnia tzw. logiki intuicjonistycznej. Ważnym powodem zajmowania się logiką intuicjonistyczną są jej zadziwiające związki z teorią obliczeń (izomorfizm Curry-Howard).

Implikacyjny fragment logiki intuicjonistycznej, który będziemy oznaczać przez $I_{\Rightarrow }$ to zbiór tych formuł które da się dowodnić przy pomocy reguły MP z aksjomatów S i K.

Definicja 7.1

Aksjomaty $I_{\Rightarrow }$

1. $(\varphi \Rightarrow (\psi \Rightarrow \varphi ))$ (formuła ta jest nazywana aksjomatem K)
2. $(\varphi \Rightarrow (\nu \Rightarrow \psi )\Rightarrow ((\varphi \Rightarrow \nu )\Rightarrow (\varphi \Rightarrow \nu ))$ (formuła ta jest nazywana aksjomatem S)

W pełnej wersji logiki intucjonistycznej pojawiają się również aksjomaty dla spójników $\wedge ,\vee$ oraz $\mathrm{\neg }$. Dla uproszczenia zajmiemy się jedynie formułami w których jedynym spójnikiem jest implikacja. Dodatkowym argumentem uzasadniającym takie podejście jest fakt, że każde twierdzenie logiki intuicjonistycznej w którym jedynymi spójnikami są $\Rightarrow$ da się udowodnić przy pomocy aksjomatów 7.1. Zobaczymy, że analogiczne twierdzenie nie jest prawdą dla logiki klasycznej. Logika intuicjonistyczna jest bardziej skomplikowana od logiki klasycznej. W szczególności nie istnieje skończona matryca za pomocą której moglibyśmy rozstrzygać czy dana formuła jest twierdzeniem logiki intuicjonistycznej.

Twierdzenie 7.2

Każde twierdzenie logiki intuicjonistycznej jest twierdzeniem klasycznego rachunku zdań.

Dowód

Każdy dowód twierdzenia logiki inuicjonistycznej jest równocześnie dowodem twierdzenia klasycznego rachunku zdań.

Implikacja w drugą stronę nie zachodzi. Istnieją formuły zbudowane jedynie przy pomocy $\Rightarrow$, które nie należą do $I_{\Rightarrow }$ pomimo że są twierdzeniami klasycznego rachunku zdań. Przykładem takiej formuły jest prawo Pierce'a:

$((p\Rightarrow q)\Rightarrow p)\Rightarrow p$

W zadaniu 4.1 pokazaliśmy, że formuła ta jest w istocie tautologią więc w myśl twierdzenia Posta 4.4 również twierdeniem klasycznego rachunku zdań.
W poniższych zadaniach wykażemy poniższe twierdzenie

Twierdzenie 7.3

Prawo Pierce'a nie jest twierdzeniem intuicjonizmu.

Zauważmy, że oznacza to również że każdy dowód prawa Pierce'a w logice klasycznej korzysta z aksjomatu 3 3.1, a więc wymaga używania spójnika $\mathrm{\neg }$.
Aby udowodnić twierdzenie 7.3 zdefiniujemy jeszcze jedną logikę którą nazwiemy $I_3$. Podobnie do 4.1 zdefiniujemy matrycę tym razem 3-elementową.

Definicja 7.4

Matrycą ${\mathbb{𝕄}}_3$ będziemy nazywać zbiór trójelementowy $M_3=\{0,1,2\}$ w którym 2 jest wyróżnioną wartością prawdy, wraz z funkcją odpowiadają za interpretacje $\Rightarrow$ zdefiniowaną następująco

$\Rightarrow$	0	1	2
0	2	2	2
1	0	2	2
2	0	1	2

W przypadku rozważanej matrycy ${\mathbb{𝕄}}_3$ wartościowanie będzie funkcją przypisującą zmiennym zdaniowym elementy zbioru $M_3$. Podobnie jak dla logiki klasycznej wartościowanie zmiennych rozszzerzamy na wartościowanie formuł zgodnie z tabelą 7.4.

Przykład 7.5

Dla wartościowania $v$ takiego, że $v(p)=2,v(q)=1,v(r)=0$ formuła

$(p\Rightarrow q)\Rightarrow r$

przyjmuje wartość 0.

Definicja 7.6

Tautologią logiki $I_3$ będziemy nazywać każdą formułę implikacyjną, która przy każdym wartościowaniu zmiennych w $M_3$ przyjmuje wartość 2.

Ćwiczenie 7.1

{{{3}}}

Ćwiczenie 7.2

{{{3}}}

Ćwiczenie 7.3

{{{3}}}

Ćwiczenie 7.4

{{{3}}}

Podsumujmy wyniki powyższych zadań. Wskazaliśmy logikę $I_3$ taką, że każda twierdzenie intuicjonizmu jest tautologią $I_3$. Skoro prawo Pierce'a nie jest tautologią $I_3$ to nie jest też twierdzeniem $I_{\Rightarrow }$.

UWAGA! W dalszej części będziemy się posługiwać wyłącznie logiką klasyczną.