Konwersja Arka 2: Różnice pomiędzy wersjami

← poprzednia edycja następna edycja →

WizualnieWikikod

Wersja z 09:54, 2 sie 2006

{tw}{Twierdzenie}[section]

{fa}[tw]{Fakt}

{AZbioruPustego}{Aksjomat Zbioru Pustego}

{APary}{Aksjomat Pary}

{ASumy}{Aksjomat Sumy}

{}{0pt}

{}{0in}

{}{-0.5in}

{}{6.3in}

{}{9in}

{cwicz}[section]

{obra}[section]

{hint}

{thm}{Twierdzenie}[section]

{defn}[thm]{Definicja}

{Zadanie}[thm]{Zadanie}

{Uwaga}[thm]{Uwaga}

{Przykład}[thm]{Przykład}

{Rozwiązanie}[thm]{Rozwiązanie}

{Hint}[thm]{Hint}

{equation}{section}

{kuba_preamble1}

{kuba_preamble2}

Wprowadzenie

Logika zdaniowa jest językiem, który pozwala opisywać zależności

pomiędzy zdaniami. Przykładem może być zdanie:

Jeśli n jest liczbą pierwszą to n jest liczbą nieparzystą lub 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:

"n jest liczbą pierwszą,"

"n jest liczbą nieparzystą,"

"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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textbf{jeśli} [..] \textbf{to}, \textbf{lub}} oraz powyższych oznaczeń otrzymamy formułę

p \Rightarrow (q \lor 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 n

będziemy wiedzieć, że jest liczbą pierwszą oraz, że nie jest

nieparzysta to klasyczny rachunek zdań pozwoli nam formalnie

wywnioskować fakt że liczba n jest równa 2. Podsumowując, jeśli

uznamy za prawdziwe następujące zdania:

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

$p$ ,

$\neg q$ (przez $\neg$ oznaczamy negację)

to zgodnie z klasycznym rachunkiem (może lepiej z intuicją?) zdań

powinniśmy uznać za prawdziwe zdanie $r$ , czyli "n jest równe

2". Powyższy schemat wnioskowania można również opisać formułą

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

W powyższej formule spójnik symbol $\land$ odpowiada spójnikowi

"'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:

{formuła logiki zdaniowej}

zmienna zdaniowa jest formułą (zmienne zdaniowy oznaczamy

zwykle literami alfabetu rzymskiego np. $p, q, r$ )

jeśli $ϕ$ oraz $ψ$ są formułami to $(ϕ \Rightarrow ψ)$ jest formułą (spójnik $\Rightarrow$ nazywamy implikacją)

jeśli $ϕ$ jest formułą to $\neg ϕ$ jest formułą

(spójnik $\neg$ nazywamy negacją)

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 $\neg$ .

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ć.

ład

Poniższe napisy nie są formułami

$p \Rightarrow \Rightarrow q$

$\neg \neg \neg$

"ten napis na pewno nie jest formułą"

$(p \Rightarrow \neg q))$

Poniższe napisy są formułami

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

$\neg \neg \neg q$

$(p \Rightarrow \neg q)$

ład

Ćwiczenie [Uzupelnij]

Rozmiarem formuły nazwiemy ilość występujących w niej spójników.

Na przykład formuła $\neg \neg q$ ma rozmiar 2, a formuła

$(p \Rightarrow q)$ ma rozmiar 1. Przypuśćmy, że jedyną zmienną zdaniową

jaką wolno nam użyć jest $p$ . Ile można skonstruować rożnych

formuł o rozmiarze 3?

Solution.

Oznaczmy przez

f_{n}

liczbę formuł o rozmiarze

n

(czyli liczbę

formuł w których jest $n$ spójników). Interesuje nas $f_{3}$ . Każda

formuła o rozmiarze 3 powstaje albo z dwóch formuł o rozmiarach 1

poprzez połączenie ich spójnikiem $\Rightarrow$ albo z jednej formuły o

rozmiarze 2 poprzez dodanie do niej spójnika $\neg$ . Co

więcej każda taka formuła powstaje tylko w jeden sposób. Wynika

stąd następująca zależność:

f_{3} = f_{2} + (f_{1})^{2}

Wiemy, że są tylko dwie formuły o rozmiarze 1, są to $\neg p$ oraz

$p \Rightarrow p$ . Stąd mamy $f_{1} = 2$ . Dla formuł o rozmiarze 2 możemy

zauważyć podobną zależność. Każda taka formuła jest albo zbudowana z

dwóch formuł z których jedna (niekoniecznie pierwsza) ma rozmiar 1 a

druga 0 za pomocą $\Rightarrow$ , albo jest zbudowana z formuły o rozmiarze

1 za pomocą negacji. Zauważmy też, że istnieje formuła o rozmiarze

0, jest to $p$ . Mamy więc następujący wzór dla $f_{2}$

f_{2} = 1 \cdot f_{1} + f_{1} \cdot 1 + f_{1} = 3 \cdot f_{1}

Z dwóch ostatnich wzorów otrzymujemy

f_{3} = 3 \cdot f_{1} + (f_{1})^{2} = 6 + 4 = 10

Skoro jest ich niewiele to możemy wszystkie wypisać

$\neg \neg \neg p$

$\neg \neg (p \Rightarrow p)$

$\neg (p \Rightarrow \neg p)$

$\neg (p \Rightarrow (p \Rightarrow p))$

$\neg (\neg p \Rightarrow p)$

$\neg ((p \Rightarrow p) \Rightarrow p)$

$(\neg p) \Rightarrow (\neg p)$

$(\neg p) \Rightarrow (p \Rightarrow p)$

$(p \Rightarrow p) \Rightarrow (\neg p)$

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

Język logiki zdaniowej można równoważnie zdefiniować nie

używając nawiasów za pomocą Odwrotnej Notacji Polskiej

Odwrotna Notacja Polska.

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:

Aksjomaty klasycznego rachunku zdań.

$(ϕ \Rightarrow (ψ \Rightarrow ϕ))$ (formuła ta jest nazywana

aksjomatem K)

$(ϕ \Rightarrow (ν \Rightarrow ψ) \Rightarrow ((ϕ \Rightarrow ν) \Rightarrow (ϕ \Rightarrow ν))$ (formuła ta jest nazywana

aksjomatem S)

$(\neg ϕ \Rightarrow ψ) \Rightarrow (\neg ϕ \Rightarrow \neg ψ) \Rightarrow ϕ$

Zdania pasujące do powyższych schematów to wszystkie zdania które

można otrzymać podstawiając w miejsce $ϕ, ν, ψ$ dowolne

formuły.

Reguła dowodzenia

Przyglądnijmy się teraz jak posługujemy się implikacją we

wniskowaniu. W przykładzie z początku wykładu implikacja odpowiadała

konstrukcji językowej:

"'jeśli"' $ϕ$ "'to"' $ψ$ .

W takim przypadku jeśli akceptujemy powyższą implikacjię jako zdanie

prawdziwe oraz jeśli zdanie $ϕ$ jako prawdziwe to powinniśmy

także zaakceptować $ψ$ . 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

\frac{ϕ \Rightarrow ψ, ϕ}{ψ} .

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.

Ciąg formuł $ϕ_{0}, \dots, ϕ_{n}$ jest dowodem formuły $ψ$

wtedy i tylko wtedy, gdy:

$ϕ_{n}$ jest formułą $ψ$

dla każdego $i \leq n$ formuła $ϕ_{i}$ jest aksjomatem

lub istnieją $j, k < i$ takie, że formuła $ϕ_{i}$

jest wynikiem zastosowania reguły modus ponens do

formuł $ϕ_{j}, ϕ_{k}$ .

W drugim punkcie powyższej definicji jeśli formuła $ϕ_{i}$ nie jest

aksjomatem (a więc powstaje przez zastosowanie MP) to formuły

$ϕ_{j}, ϕ_{k}$ muszą pasować do przesłanek reguły MP, a więc

$ϕ_{j}$ musi być postaci $ϕ_{k} \Rightarrow ϕ_{i}$ lub $ϕ_{k}$ postaci

$ϕ_{j} \Rightarrow ϕ_{i}$ .

Formułę nazywamy "twierdzeniem klasycznego rachunku zdań"

jeśli istnieje jej dowód z aksjomatów klasycznego rachunku

zdań Uzupelnic defn:AksjomatyKRZ|.

Przykład

Zastanówmy się na formułą postaci $ϕ \Rightarrow ϕ$ . Intuicja

podpowiada, że taką formułę powinniśmy uznać za prawdziwą. Nie

pasuje ona jednak do żadnego ze schematów aksjomatów

Uzupelnic defn:AksjomatyKRZ|. 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.

$[ϕ \Rightarrow [(q \Rightarrow ϕ) \Rightarrow ϕ)] \Rightarrow [[ϕ \Rightarrow (q \Rightarrow ϕ)] \Rightarrow [ϕ \Rightarrow ϕ]]$ formuła ta jest aksjomatem zgodnym ze schematem S

$ϕ \Rightarrow [(q \Rightarrow ϕ) \Rightarrow ϕ]$ aksjomat zgodny ze

schematem K

$(ϕ \Rightarrow (q \Rightarrow ϕ)) \Rightarrow (ϕ \Rightarrow ϕ)$ z modus ponens z

formuł 1 i 2.

$ϕ \Rightarrow [q \Rightarrow ϕ]$ aksjomat zgodny ze schematem

K

$(ϕ \Rightarrow ϕ)$ 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

Uzupelnic defn:AksjomatyKRZ| 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ć.

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 $ϕ \Rightarrow (ν \Rightarrow ψ)$ jako ",,jeśli prawdziwe jest

$ϕ$ i prawdziwe jest $ν$ to prawdziwe jest $ψ$ "". 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.

Dwuelementową matrycą boolowską nazywamy zbiór dwuelementowy

$𝔹 = {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 $\neg$ zdefiniowanymi następująco

Parser nie mógł rozpoznać (nieznana funkcja „\begintabular”): {\displaystyle \begintabular {|c|c c|}\hline & 0 & 1 \\\hline 0 & 1 & 1 \\ 1 & 0 & 1 \\\hline \endtabular \hspace{1cm} \begintabular {|c|c|}\hline } pParser nie mógł rozpoznać (błąd składni): {\displaystyle & } pParser nie mógł rozpoznać (błąd składni): {\displaystyle \\\hline 0 & 1 \\ 1 & 0 \\\hline \endtabular }

Wartościowaniem nazywamy funkcję która przypisuje zmiennym

zdaniowym elementy zbioru $𝔹$ . Wartościowanie zmiennych

można rozszerzyć na wartościowanie formuł interpretując spójniki

$\Rightarrow$ oraz $\neg$ jako funkcje zgodnie z tabelami

Uzupelnic eq:tabeleInterpretacjiKRZ|.

ład

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 $\neg p \Rightarrow r$ jest wartościowana na 0 (czyli $v (\neg p \Rightarrow r) = 0$ )

ład

Ćwiczenie [Uzupelnij]

Przy wartościowaniu $v$ z przykładu Uzupelnic eg:wartosciowania| jakie

wartości przyjmują następujące formuły

$p \Rightarrow (q \Rightarrow r)$

$p \Rightarrow (p \Rightarrow q)$

$\neg \neg q \Rightarrow p$

$(\neg q \Rightarrow q) \Rightarrow (q \Rightarrow \neg q)$

Solution.

$v (p \Rightarrow (q \Rightarrow r)) = 1$

$v (p \Rightarrow (p \Rightarrow q)) = 1$

$v (\neg \neg q \Rightarrow p) = 0$

$v ((\neg q \Rightarrow q) \Rightarrow (q \Rightarrow \neg q)) = 0$

Ćwiczenie [Uzupelnij]

Podaj przykład wartościowania zmiennych tak aby poniższe formuły

były wartościowane na 0

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

1. $(\neg p \Rightarrow q)$

1. $(p \Rightarrow q) \Rightarrow q$

Podaj przykład wartościowania zmiennych tak aby poniższe formuły

były wartościowane na 1

1. $\neg (p \Rightarrow q)$

1. $\neg (\neg p \Rightarrow \neg q)$

1. $(\neg q \Rightarrow q) \Rightarrow (q \Rightarrow \neg q)$

Solution.

Wartościowania będziemy oznaczać przez

v

1. $v (p) = 1, v (q) = 1, v (r) = 0$

1. $v (p) = 0, v (q) = 0$

1. $v (p) = 0, v (q) = 0$

1. $v (p) = 1, v (q) = 0$

1. $v (p) = 0, v (q) = 1)$

1. $v (q) = 1$

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 [Uzupelnij]

Sprawdź czy poniższe formuły są tautologiami

$(ϕ \Rightarrow (ψ \Rightarrow ϕ))$

$(ϕ \Rightarrow (ν \Rightarrow ψ) \Rightarrow ((ϕ \Rightarrow ν) \Rightarrow (ϕ \Rightarrow ν))$

$(\neg ϕ \Rightarrow ψ) \Rightarrow (\neg ϕ \Rightarrow \neg ψ) \Rightarrow ϕ$

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

{hint}{1}

Hint .

Spróbuj poszukać wartościowań dla których formuła przyjmuje

wartość 0

{hint}{1}

Hint .

Można też sprawdzić wszystkie możliwości wartościowań.

Solution.

Nie przez przypadek pierwsze trzy formuły z poprzedniego zadania

odpowiadają aksjomatom klasycznego rachunku zdań

Uzupelnic defn:AksjomatyKRZ|. Okazuje się że istnieje ścisły związek

pomiędzy tautologiami a twierdzeniami klasycznego rachunku zdań. Mówi o tym ważny wynik Emil Post.

Twierdzenie [Uzupelnij]

{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 [Uzupelnij]

Udowodnij że każde twierdzenie klasycznego rachunku zdań jest tautologią.

{hint}{1}

Hint .

Pokazaliśmy już w zadaniu

Uzupelnic zad:aksjomatyTatuologie|, że aksjomaty są tautologiami.

Zacznij od pokazania, że zastosowanie reguły MP do tautologii daje

tautologię.

{hint}{1}

Hint .

Udowodnij, twierdznie przez indukcję ze względu na długość

dowodu.

Solution.

Inne spójniki

Do tej pory jedynymi rozważanymi spójnikami była implikacja i

negacja. W analogiczny sposób do Uzupelnic eq:tabeleInterpretacjiKRZ|

możemy wprowadzać kolejne spójniki. Często używane spójniki to

koniunkcja (spójnik "'i"') oznaczana przez $\land$ oraz

alternatywa (spójnik "'lub"') oznaczana przez $\lor$ , które

będziemy interpretować w następujący sposób:

Parser nie mógł rozpoznać (nieznana funkcja „\begintabular”): {\displaystyle \begintabular {|c|c c|}\hline & 0 & 1 \\\hline 0 & 0 & 0 \\ 1 & 0 & 1 \\\hline \endtabular \hspace{1cm} \begintabular {|c|c c|}\hline & 0 & 1 \\\hline 0 & 0 & 1 \\ 1 & 1 & 1 \\\hline \endtabular }

Zgodnie z intuicją koniunkcja $ϕ \land ψ$ jest wartościowana

na 1 wtedy i tylko wtedy gdy zarówno $ϕ$ jak i $ψ$ są

wartościowane na 1. Alternatywa $ϕ \lor ψ$ jest wartościowana

na 1 jeśli przynajmniej jedna z formuł $ϕ, ψ$ jest

wartościowana na 1.

Formuły $ϕ$ oraz $ψ$ są "równoważne" (oznaczamy ten fakt

przez $ϕ \equiv ψ$ wtedy i tylko wtedy gdy dla każdego

wartościowania formuła $ϕ$ przyjmuje tą samą wartość co

formuła $ψ$ .

Ćwiczenie [Uzupelnij]

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

$ϕ \lor ψ \equiv \neg ϕ \Rightarrow ψ$

$ϕ \land ψ \equiv \neg (ϕ \Rightarrow \neg ψ)$

Solution.

Lewa strona jest fałszywa jedynie gdy $ϕ$ oraz

$ψ$ są wartościowane na 0. Prawa strona jest fałszywa

wtedy i tylko wtedy kiedy $\neg ϕ$ jest wartościowane na

1 oraz $ψ$ 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 $ϕ$ oraz

$ψ$ są wartościowane na 0, a więc jest równoważna lewej.

Lewa strona jest prawdziwa jedynie gdy $ϕ$ oraz

$ψ$ są wartościowane na 1. Prawa strona jest prawdziwa

wtedy i tylko wtedy kiedy $\neg (ϕ \Rightarrow \neg ψ)$ jest wartościowane na

1, więc wtedy gdy $(ϕ \Rightarrow \neg ψ)$ jest wartościowane na 0. To z kolei

zdarzyć się może jedynie gdy $ϕ$ jest wartościowane na 1

i $\neg ψ$ na 0, a więc wtedy gdy zarówno $ϕ$ jak i

$ψ$ 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 $\land$ lub $\lor$ można zastąpić równoważną formułą w

której jedynymi spójnikami są $\Rightarrow$ oraz $\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 [Uzupelnij]

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

$\neg \neg p \equiv p$

$p \Rightarrow q \equiv \neg p \lor q$

$p \Rightarrow (q \Rightarrow r) \equiv (p \land q) \Rightarrow r$

$\neg (p \land q) \equiv \neg p \lor \neg q$

$\neg (p \lor q) \equiv \neg p \land \neg q$

$p \land (q \lor r) \equiv (p \land q) \lor (p \land r)$

$p \lor (q \land r) \equiv (p \lor q) \land (p \lor r)$

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

Solution.

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

Jeśli $p$ jest wartościowane na 1, to zgodnie z tabelą dla negacji Uzupelnic eq:tabeleInterpretacjiKRZ|

$\neg p$ jest wartościowane na 0 i $\neg \neg p$ jest wartościowane na 1. Jeśli $p$ jest wartościowane

na 0 to $\neg p$ jest wartościowane na 1 i $\neg \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.

Jedyną możliwością aby lewa strona była fałszywa jest

aby $p$ było wartościowane na 1, a $q$ na 0. Prawa

stona jest fałszywa jedynie gdy $\neg p$ oraz $q$ są wartościowane

na 0. Czyli prawa strona jest fałszywa jedynie

gdy $p$ jest wartościowane na 1 i $q$ na 0. Formuły są więc

równoważne.

Analogicznie do poprzedniego punktu łatwo się

przekonać, że jedynym wartościowaniem które falsyfikuje lewą

stronę jest takie które wartościuje $p$ i $q$ na 1 oraz $r$

na 0. Tą samą własność ma formuła po prawej stronie, więc

formuły są równoważne.

Przykład rozwiązania przez rozważenie wszystkich

możliwości

Parser nie mógł rozpoznać (nieznana funkcja „\begintabular”): {\displaystyle \begintabular {|c|c|c|c|c|c|c|}\hline } pParser nie mógł rozpoznać (błąd składni): {\displaystyle & } qParser nie mógł rozpoznać (błąd składni): {\displaystyle & } p qParser nie mógł rozpoznać (błąd składni): {\displaystyle & } (p q)Parser nie mógł rozpoznać (błąd składni): {\displaystyle & } pParser nie mógł rozpoznać (błąd składni): {\displaystyle & } qParser nie mógł rozpoznać (błąd składni): {\displaystyle & } p qParser nie mógł rozpoznać (błąd składni): {\displaystyle \\\hline 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\\\hline \endtabular \hspace{1cm} }

W pierwszych dwóch kolumnach są zapisane wartościowania

zmiennych $p$ i $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.

W równoważności z poprzedniego punktu, podstawiąjąc za $p$

formułę $\neg p$ oraz za $q$ formułę $\neg q$ otrzymamy

równoważność

\neg (\neg p \land \neg q) \equiv \neg \neg p \lor \neg \neg q .

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

otrzymujemy

\neg (\neg p \land \neg q) \equiv p \lor q .

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

\neg \neg (\neg p \land \neg q) \equiv \neg (p \lor q) .

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

otrzymamy szukaną równoważność.

Ćwiczenie [Uzupelnij]

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

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

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

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

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

Solution.

Spróbujmy znaleźć wartościowanie które falsyfikuje tą

formułę. Skoro implikacja ma być fałszywa to formuła $(p \lor q)$ (czyli następnik) musi być

fałszywa. Tak jest tylko wtedy kiedy zarówno $p$ jak i $q$ są

fałszywe. Zobaczmy co się wtedy dzieje z poprzednikim implikacji,

czyli formułą

(p \lor r) \land (q \lor \neg r) .

Jeśli teraz ustalimy $r$ na fałsz to $(p \lor q)$ będzie

fałszywe a jeśli ustalimy $r$ na

prawdę to $(q \lor \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ą.

Formuła nie jest tautologią. Wystarczy wartościować $p$ i

$r$ na prawdę i $q$ na fałsz.

Formuła nie jest tautologią. Wystarczy wartościować $p$ i

$r$ na prawdę i $q$ na fałsz.

Przykład rozwiązania przez rozważenie wszystkich

możliwości

Parser nie mógł rozpoznać (nieznana funkcja „\begintabular”): {\displaystyle \begintabular {|c|c|c|c|c|c|c|c|}\hline } pParser nie mógł rozpoznać (błąd składni): {\displaystyle & } qParser nie mógł rozpoznać (błąd składni): {\displaystyle & } rParser nie mógł rozpoznać (błąd składni): {\displaystyle &} (p q)Parser nie mógł rozpoznać (błąd składni): {\displaystyle &} (p r)Parser nie mógł rozpoznać (błąd składni): {\displaystyle &} ( q r)Parser nie mógł rozpoznać (błąd składni): {\displaystyle &} (p r)( q r)Parser nie mógł rozpoznać (błąd składni): {\displaystyle & } (p q) ( (p r)( q r))Parser nie mógł rozpoznać (błąd składni): {\displaystyle \\\hline 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 \\\hline \endtabular \hspace{1cm} }

W kolumnie odpowiadającej badanej formule są same 1, więc

jest ona tautologią.

Binarne spójniki logiczne interpretowaliśmy jako funkcje z $𝔹 \times 𝔹 \to 𝔹$ . 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.

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

Parser nie mógł rozpoznać (nieznana funkcja „\begintabular”): {\displaystyle \begintabular {|c|c|c|c|c|c||c|}\hline Numer & } p=0Parser nie mógł rozpoznać (błąd składni): {\displaystyle &} p=0Parser nie mógł rozpoznać (błąd składni): {\displaystyle &} p=1Parser nie mógł rozpoznać (błąd składni): {\displaystyle &} p=1Parser nie mógł rozpoznać (błąd składni): {\displaystyle && \\ funkcji& } q=0Parser nie mógł rozpoznać (błąd składni): {\displaystyle & } q=1Parser nie mógł rozpoznać (błąd składni): {\displaystyle & } q=0Parser nie mógł rozpoznać (błąd składni): {\displaystyle & } q=1Parser nie mógł rozpoznać (błąd składni): {\displaystyle && \\ \hline 0 & 0 & 0 & 0 & 0 && } FParser nie mógł rozpoznać (błąd składni): {\displaystyle \\ 1 & 0 & 0 & 0 & 1 && \\ 2 & 0 & 0 & 1 & 0 && } (p q)Parser nie mógł rozpoznać (błąd składni): {\displaystyle \\ 3 & 0 & 0 & 1 & 1 && } pParser nie mógł rozpoznać (błąd składni): {\displaystyle \\ 4 & 0 & 1 & 0 & 0 && } (q p)Parser nie mógł rozpoznać (błąd składni): {\displaystyle \\ 5 & 0 & 1 & 0 & 1 && } qParser nie mógł rozpoznać (błąd składni): {\displaystyle \\ 6 & 0 & 1 & 1 & 0 && } XORParser nie mógł rozpoznać (błąd składni): {\displaystyle \\ 7 & 0 & 1 & 1 & 1 && \\ 8 & 1 & 0 & 0 & 0 && } NORParser nie mógł rozpoznać (błąd składni): {\displaystyle \\ 9 & 1 & 0 & 0 & 1 && \\ 10& 1 & 0 & 1 & 0 && } qParser nie mógł rozpoznać (błąd składni): {\displaystyle \\ 11& 1 & 0 & 1 & 1 && } q pParser nie mógł rozpoznać (błąd składni): {\displaystyle \\ 12& 1 & 1 & 0 & 0 && } p Parser nie mógł rozpoznać (błąd składni): {\displaystyle \\ 13& 1 & 1 & 0 & 1 && } p q Parser nie mógł rozpoznać (błąd składni): {\displaystyle \\ 14& 1 & 1 & 1 & 0 && } NANDParser nie mógł rozpoznać (błąd składni): {\displaystyle \\ 15& 1 & 1 & 1 & 1 && } T Parser nie mógł rozpoznać (błąd składni): {\displaystyle \\\hline \endtabular \hspace{1cm} }

Spójnik binarny $\circ$ będziemy nazywać "przemiennym" jeśli zachodzi

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

p \circ q \equiv q \circ p

Ćwiczenie [Uzupelnij]

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

$x N A N D y \equiv \neg (x \land y)$

$x N O R y \equiv \neg (x \lor y)$

$x X O R y \equiv \neg (x \Leftrightarrow y)$

Solution.

Ćwiczenie [Uzupelnij]

Ile spójników binarnych jest przemiennych? Wypisz je wszystkie.

{hint}{1}

Hint .

Wygodnie jest reprezentować spójniki binarne w tabeli

kwadratowej. Na przykład alternatywę

zdefiniowaliśmy jako

Parser nie mógł rozpoznać (nieznana funkcja „\begintabular”): {\displaystyle \begintabular {|c|c c|}\hline & 0 & 1 \\\hline 0 & 0 & 1 \\ 1 & 1 & 1 \\\hline \endtabular . }

Jaką własność musi posiadać tabela aby spójnik definiowany przez nią był

przemienny?

Solution.

Dla przemienności spójnika

\circ

istotne jest aby

1 \circ 0 = 0 \circ 1

. Dla pozostałych

przypadków wartościowań równoważnośc Uzupelnic eq:przemienność|

jest zawsze spełniona. Każdy spójnik binarny możemy

zdefiniować za pomocą tabelki kwadratowej, np. alternatywę

zdefiniowaliśmy jako

Parser nie mógł rozpoznać (nieznana funkcja „\begintabular”): {\displaystyle \begintabular {|c|c c|}\hline & 0 & 1 \\\hline 0 & 0 & 1 \\ 1 & 1 & 1 \\\hline \endtabular . }

Warunek przemienności oznacza, że wartość w polu o

współrzędnych $(0, 1)$ jest równa wartości w polu o

współrzędnych $(1, 0)$ . Takich tabel jest 8, więc mamy 8

spójników przemiennych. Nietrudno je teraz odnaleźć w tabeli

Uzupelnic defn:spójniki|. Są to

$F$

$\land$

$X O R$

$\lor$

$N O R$

$\Leftrightarrow$

$N A N D$

$T$

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 .

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 [Uzupelnij]

Udowodnij, że następujące spójniki są łączne

$\lor$

$\land$

$\Leftrightarrow$

$X O R$

Solution.

Formuła $(p \lor q) \lor r$ jest fałszywa jedynie

wtedy gdy $p$ , $q$ i $r$ są wartościowane na fałsz. Tak

samo jest dla formuły $p \lor (q \lor r)$ więc są one

równoważne.

Formuła $(p \land q) \land r$ jest prawdziwa jedynie

wtedy gdy $p$ , $q$ i $r$ są wartościowane na prawdę. Tak

samo jest dla formuły $p \land (q \land r)$ więc są one

równoważne.

Zbadamy równoważność formuł $(p \Leftrightarrow q) \Leftrightarrow r$

i $p \Leftrightarrow (q \Leftrightarrow r)$ za pomocą tabeli

Parser nie mógł rozpoznać (nieznana funkcja „\begintabular”): {\displaystyle \begintabular {|c|c|c|c|c|c|c|}\hline } pParser nie mógł rozpoznać (błąd składni): {\displaystyle &} qParser nie mógł rozpoznać (błąd składni): {\displaystyle &} r Parser nie mógł rozpoznać (błąd składni): {\displaystyle &} (p q)Parser nie mógł rozpoznać (błąd składni): {\displaystyle & } (p q) rParser nie mógł rozpoznać (błąd składni): {\displaystyle & } (q r )Parser nie mógł rozpoznać (błąd składni): {\displaystyle &} p (q r)Parser nie mógł rozpoznać (błąd składni): {\displaystyle \\\hline 0 & 0 & 0 & 1 & 0 & 1 & 0 \\ 0 & 0 & 1 & 1 & 1 & 0 & 1 \\ 0 & 1 & 0 & 0 & 1 & 0 & 1 \\ 0 & 1 & 1 & 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 0 & 1 & 1 & 1 \\ 1 & 0 & 1 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 1 & 0 & 0 & 0 \\ 1 & 1 & 1 & 1 & 1 & 1 & 1 \\\hline \endtabular \hspace{1cm} }

Kolumna 4 i 6 są identyczne więc odpowiadające im

formuły są równoważne. Spójnik $\Leftrightarrow$ jest więc łączny.

...

Możemy również rozważać spójniki 3 i więcej argumentowe. Spójnik

$k$ -argumetowy powinien odpowiadać funkcji $𝔹^{k} \to 𝔹$ .

ład

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

Parser nie mógł rozpoznać (nieznana funkcja „\begintabular”): {\displaystyle \begintabular {|c c c|c||}\hline } pParser nie mógł rozpoznać (błąd składni): {\displaystyle & } qParser nie mógł rozpoznać (błąd składni): {\displaystyle & } rParser nie mógł rozpoznać (błąd składni): {\displaystyle &} (p, q,r)Parser nie mógł rozpoznać (błąd składni): {\displaystyle \\\hline 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 \\\hline \endtabular \hspace{1cm} }

ład

Ćwiczenie [Uzupelnij]

Udowodnij, że różnych spójników $k$ -argumentowych jest dokładnie

$2^{2^{k}}$ .

Solution.

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

$𝔹$ . 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ć (nieznana funkcja „\begintabular”): {\displaystyle \begintabular {|c|c|c|c|}\hline p & q & r & } f_{p (q r)}Parser nie mógł rozpoznać (błąd składni): {\displaystyle \\\hline 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 \\\hline \endtabular }

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

Skończony zbiór funkcji boolowskich $Γ$ 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 $Γ$ .

Twierdzenie [Uzupelnij]

Zbiór ${\land, \lor, \neg}$ jest funkcjonalnie pełny.

Dowód [Uzupelnij]

Twierdzenie [Uzupelnij]

Zbiory ${\land, \neg}$ , ${\lor, \neg}$ są funkcjonalnie pełne.

Dowód [Uzupelnij]

Udowodnij, że zbiór ${\Rightarrow, \neg}$ jest funkcjonalnie

pełny.

Twierdzenie [Uzupelnij]

Zbiór ${N O R}$ jest funkcjonalnie pełny.

Udowodnij, że zbiór ${N A N D}$ jest funkcjonalnie pełny.

Ćwiczenie [Uzupelnij]

Zdefiniuj alternatywę przy pomocy samej implikacji.

Solution.

Łatwo sprawdzić że formuła

p \Rightarrow (p \Rightarrow q)

jest równoważna

formule $p \lor q$ .

Jakie funkcje binarne da się zdefiniować przy pomocy samej

implikacji?

Ćwiczenie [Uzupelnij]

Udowodnij, że poniższe zbiory nie są funkcjonalnie pełne

${\land}$

${\lor}$

${\Leftrightarrow}$

${X O R}$

Solution.

Oznaczmy zbiór formuł w których jedynym spójnikiem jest $\land$ przez

$F_{\land}$ . Udowodnimy, że każda formuła z $F_{\land}$ przyjmuje zawsze wartość 1, jeśli jej zmienne są

wartościowane na 1. Rozmiarem formuły będziemy nazywać liczbę wystąpień spójnika $\land$ w formule.

Dowód będzie indukcyjny ze względu na

rozmiar formuły.

Baza indukcji: Każda formuła z $F_{\land}$ o rozmiarze 0 jest postaci $x$ , gdzie

$x$ jest zmienną. Wobec tego przy wartościowaniu zmiennych na 1 formuła $x$ też jest

wartościowana na 1. A więc każda formuła o rozmiarze 0 ma postulowaną własność.

Krok indukcyjny: Ustalmy dowolne $n > 0$ i przyjmijmy, że

wszystkie formuły o mniejszym rozmiarze mają postulowaną

własność. Niech $ν$ będzie dowolną formułą z $F_{\land}$ o rozmiarze

$n$ . Skoro $n > 1$ to $ν$ musi być postaci $ϕ \land ψ$ . Rozważmy wartościowanie które wszyskim zmiennym

przypisuje wartość 1. Ponieważ rozmiary $ϕ$ oraz $ψ$

są silnie mniejsze od $n$ to z założenia indukcyjnego

otrzymujemy, że dla naszego wartościowania obie przyjmują

wartość 1. Wobec tego zgodnie z tabelą

Uzupelnic eq:tabeleInterpretacjiKRZANDOR| cała formuła $ϕ \land ψ$ też przyjmuje wartość 1. Dowiedliśmy więc, że każda

formuła o rozmiarze $n$ ma postulowaną własność.

Wiemy już że każda $F_{\land}$ przyjmuje zawsze wartość 1, jeśli jej zmienne są

wartościowane na 1. Wobec tego niemożliwe jest zdefiniowanie

np. spójnika $F$ gdyż definująca go formuła musiałby

przyjąć wartość 0 na takim wartościowaniu.

Dowód analogiczny do poprzedniego.

Ćwiczenie [Uzupelnij]

Czy funkcje binarne zdefiniowane za pomocą formuł zawierającyh jedynie przemienne spójniki muszą być przemienne?

{hint}{1}

Hint .

Przyjrzyj się formułom zbudowanym z

\Leftrightarrow

Ćwiczenie [Uzupelnij]

(z wykładu prof. P.M.Idziaka)

Niech $F_{n}$ oznacza ilość boolowskich funkcji $n$ argumetnowych,

a $P_{n}$ ilość boolowskich funkcji $n$ argumentowych, takich że

przy pomocy każdej z nich da się zdefiniować dowolną funkcję

boolowską (czyli jeśli $\circ$ jest takim spójnikiem to zbiór

${\circ}$ jest funkcjonalnie pełny). Udowdnij istenienie

poniższej granicy i wyznacz jej wartość

\lim_{n \to \infty} \frac{P_{n}}{F_{n}}

Solution.

Postacie normalne

"Literałem" nazywamy formułę która jest zmienną zdaniową lub

negacją zmiennej zdaniowej.

Zauważmy, że formuła konstruowana w dowodzie twierdzenia

Uzupelnic thm:AndOrNegFP| 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 \land q) \lor (\neg p \land q) \lor (\neg p \land \neg q) .

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

literałów. Czyli wtedy gdy jest postaci

ϕ_{1} \lor \dots \lor ϕ_{n}

oraz każda z formuł $ϕ_{i}$ jest koniunkcją literałów, czyli jest postaci

l_{1}^{i} \land \dots \land l_{k}^{i}

dla pewnych literałów $l_{1}^{i}, \dots, l_{k}^{i}$

Twierdzenie [Uzupelnij]

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

Dowód [Uzupelnij]

Wynika bezpośrednio z konstrukcji w dowodzie twierdzenia

Uzupelnic thm:AndOrNegFP|.

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

alternatywami literałów.

Twierdzenie [Uzupelnij]

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

Dowód [Uzupelnij]

Ćwiczenie [Uzupelnij]

Jak sprawdzić, czy formuła w CNF jest tautologią?

Solution.

Niech rozważaną formułą będzie

ϕ_{1} \land \dots \land ϕ_{n}

Aby była tautologią konieczne jest aby każda z formuł $ϕ_{i}$ była tautologią.

Ponieważ każda z formuł $ϕ_{i}$ jest alternatywą literałów to jest tautologią jedynie wtedy

jeśli istnieje taki literał który występuje w $ϕ_{i}$ zarówno pozytywnie (czyli jako zmienna)

jak i negatywnie (czyli jako zanegowana zmienna).

Ćwiczenie [Uzupelnij]

Dla poniższych formuł wypisz ich najkrótsze równoważne formuły w

CNF

$p \Leftrightarrow q$

$p \Rightarrow (q \Rightarrow p)$

$(p \Rightarrow q) \Rightarrow p$

$(p \lor a \lor b) \land (\neg q \lor \neg a) \land (r \lor \neg b \lor \neg c) \land (c \lor p))$

$(p \land q) \lor (r \land s)$

Solution.

Spełnialność

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

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 [Uzupelnij]

Formuła $ϕ$ jest tautologią wtedy i tylko wtedy kiedy formuła

$\neg ϕ$ nie jest spełnialna.

Dowód [Uzupelnij]

Przypuśćmy, że formuła $ϕ$ jest tautologią. Wtedy dla każdego wartościowania $v$ mamy

$v (ϕ) = 1$ . Stąd otrzymujemy że dla każdego wartościowania $v$ mamy $v (\neg ϕ) = 0$ , a więc

nie istnieje wartościwanie, które spełnia $\neg ϕ$ , czyli formuła ta nie jest spełnialna.

Przypuśćmy, że formuła $\neg ϕ$ nie jest spełnialna, czyli nie istnieje wartościowanie $v$

takie, że $v (\neg ϕ) = 0$ . Wynika stąd, że dla każdego wartościowania mamy $v (ϕ) = 1$ , a więc $ϕ$ jest tautologią.

Ćwiczenie [Uzupelnij]

Sprawdź spełnialność następujących formuł

$(\neg p \lor q) \land (\neg q \lor \neg r) \land (\neg q \lor \neg p)$

$(\neg p \lor q) \land (\neg q \lor \neg r) \land (\neg q \lor p)$

Solution.

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.

Aksjomaty $I_{\Rightarrow}$

$(ϕ \Rightarrow (ψ \Rightarrow ϕ))$ (formuła ta jest nazywana

aksjomatem K)

$(ϕ \Rightarrow (ν \Rightarrow ψ) \Rightarrow ((ϕ \Rightarrow ν) \Rightarrow (ϕ \Rightarrow ν))$ (formuła ta jest nazywana

aksjomatem S)

W pełnej wersji logiki intucjonistycznej

pojawiają się również aksjomaty dla spójników $\land, \lor$ oraz $\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

Uzupelnic defn:AksjomatyIntImp|. 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 [Uzupelnij]

Każde twierdzenie logiki intuicjonistycznej

jest twierdzeniem klasycznego rachunku zdań.

Dowód [Uzupelnij]

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 Uzupelnic zad:aksjomatyTatuologie| pokazaliśmy, że formuła ta jest w istocie tautologią

więc w myśl twierdzenia Posta Uzupelnic thm:zupełnośćPost| również

twierdeniem klasycznego rachunku zdań.

W poniższych zadaniach wykażemy poniższe twierdzenie

Twierdzenie [Uzupelnij]

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 Uzupelnic defn:AksjomatyKRZ|, a więc wymaga

używania spójnika $\neg$ .

Aby udowodnić twierdzenie Uzupelnic thm:PrawoPiercea| zdefiniujemy

jeszcze jedną logikę którą nazwiemy $I_{3}$ . Podobnie do

Uzupelnic defn:matrycaBool| zdefiniujemy matrycę tym razem 3-elementową.

Matrycą $𝕄_{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

Parser nie mógł rozpoznać (nieznana funkcja „\begintabular”): {\displaystyle \begintabular {|c|c c c|}\hline & 0 & 1 & 2\\\hline 0 & 2 & 2 & 2\\ 1 & 0 & 2 & 2\\ 2 & 0 & 1 & 2\\\hline \endtabular \hspace{1cm} }

W przypadku rozważanej matrycy $𝕄_{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ą

Uzupelnic eq:tabeleInterpretacjiInt3|.

ład

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.

ład

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 [Uzupelnij]

Udowodnij, że aksjomaty S i K są tautologiami $I_{3}$ .

Solution.

Ćwiczenie [Uzupelnij]

Udowodnij, że jeśli formuła postaci $ϕ \Rightarrow ψ$ oraz formuła $ϕ$

są tautologiami $I_{3}$ to formuła $ψ$ jest tautologią $I_{3}$ .

Solution.

Ćwiczenie [Uzupelnij]

Udowodnij, że każde twierdzenie logiki $I_{\Rightarrow}$ jest

tautologią $I_{3}$ .

{hint}{1}

Hint .

Przeprowadź rozumowanie indukcyjne ze względu na długość dowodu.

Pomocne będą poprzednie zadania.

Solution.

Ćwiczenie [Uzupelnij]

Sprawdź, czy prawo Pierce'a jest tautologią $I_{3}$ .

{hint}{1}

Hint .

Nie jest.

Solution.

Dla wartościowania

v

takiego, że

v (p) = 1

i

v (q) = 0

kolejne

fomruły przyjmują następujace wartości

$v (p \Rightarrow q) = 0$

$v ((p \Rightarrow q) \Rightarrow p) = 2$

$v (((p \Rightarrow q) \Rightarrow p) \Rightarrow p) = 1$

Wobec tego prawo Pierce'a nie jest tautologią $I_{3}$ gdyż

wyróżnioną wartością prawdy $I_{3}$ w jest 2.

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ą"'.

{amsplain}

Konwersja Arka 2: Różnice pomiędzy wersjami

Wersja z 09:54, 2 sie 2006

Spis treści

Wprowadzenie

Język logiki zdaniowej

Aksjomatyka Klasycznego Rachunku Zdań

Aksjomaty

Reguła dowodzenia

Przykład

Podsumowanie

Matryca boolowska

Twierdzenie o pełności

Inne spójniki

Systemy funkcjonalnie pełne

Postacie normalne

Spełnialność

Logika intuicjonistyczna

Menu nawigacyjne

Działania na stronie

Opcje strony

Narzędzia osobiste

Nawigacja

Szukaj

Narzędzia

@@ Linia 1: / Linia 1: @@
-==Wprowadzenie==
+{tw}{Twierdzenie}[section]
-Logika zdaniowa jest językiem, który pozwala opisywać zależności
+{fa}[tw]{Fakt}
-pomiędzy zdaniami. Przykładem może być zdanie:
-Jeśli n jest liczbą pierwszą to n jest liczbą nieparzystą lub n jest
+{AZbioruPustego}{Aksjomat Zbioru Pustego}
-równe 2.
-W powyższym zdaniu spójniki "'jeśli"' [..] "'to"',
+{APary}{Aksjomat Pary}
-"'lub"' mówią o związkach które zachodzą pomiędzy zdaniami:
-# "n jest liczbą pierwszą,"
+{ASumy}{Aksjomat Sumy}
-# "n jest liczbą nieparzystą,"
-# "n jest równe 2."
-Oznaczmy powyższe zdania przez <math>p,q,r</math> (w takiej właśnie
+{}{0pt}
-kolejności). Używając symboli, które zwyczajowo odpowiadają
-potocznemu rozumieniu spójników <math>\textbf{jeśli} [..] \textbf{to},
-\textbf{lub}</math> oraz powyższych oznaczeń otrzymamy formułę
-<center><math>
+{}{0pt}
-p \Rightarrow (q \vee r).
+{}{0in}
-</math></center>
-Jeśli powyższą formułę uznamy za prawdziwą to może nam ona posłużyć
+{}{-0.5in}
-do otrzymania nowych wniosków. Na przykład jeśli o jakiejś liczbie n
-będziemy wiedzieć, że jest liczbą pierwszą oraz, że nie jest
-nieparzysta to klasyczny rachunek zdań pozwoli nam formalnie
-wywnioskować fakt że liczba n jest równa 2. Podsumowując, jeśli
-uznamy za prawdziwe następujące zdania:
-# <math> p \Rightarrow (q \vee r) </math>,
+{}{6.3in}
-# <math>p </math>,
+{}{9in}
-# <math> \neg q </math> (przez <math>\neg</math> oznaczamy negację)
-to zgodnie z klasycznym rachunkiem (może lepiej z intuicją?) zdań
-powinniśmy uznać za prawdziwe zdanie <math>r</math>, czyli "n jest równe
-". Powyższy schemat wnioskowania można również opisać formułą
-<center><math>
+{cwicz}[section]
-\left((p \Rightarrow (q \vee r)) \wedge p \wedge (\neg q)\right) \Rightarrow
+{obra}[section]
-q.
-</math></center>
-W powyższej formule spójnik symbol <math>\wedge</math> odpowiada spójnikowi
+{hint}
-"'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
+{thm}{Twierdzenie}[section]
-formuł zdefiniowanych następująco:
-{formuła logiki zdaniowej}
-# zmienna zdaniowa jest formułą (zmienne zdaniowy oznaczamy
+{defn}[thm]{Definicja}
-zwykle literami alfabetu rzymskiego np. <math>p,q,r</math>)
-# jeśli <math>\phi</math> oraz <math>\psi</math> są formułami to <math>(\phi
-\Rightarrow \psi)</math> jest formułą (spójnik <math>\Rightarrow</math> nazywamy implikacją)
-# jeśli <math>\phi</math> jest formułą to <math>\neg \phi</math> jest formułą
-(spójnik <math>\neg</math> nazywamy negacją)
-# nic innego nie jest formułą.
+{Zadanie}[thm]{Zadanie}
-Powyższa definicja mówi, że formułami nazywamy te napisy które dają
+{Uwaga}[thm]{Uwaga}
-się skonstruować ze zmiennych zdaniowych przy pomocy spójników
-<math>\Rightarrow</math> oraz <math>\neg</math>.
-Zgodnie z powyższą definicją nie jest formułą napis <math>p\Rightarrow q</math>,
+{Przykład}[thm]{Przykład}
-gdyż brakuje w nim nawiasów. Pomimo, iż poprawnie powinniśmy
-napisać <math>(p\Rightarrow q)</math> możemy przyjąć że nie będzie konieczne
-pisanie nawiasów, jeśli nawiasy można jednoznacznie uzupełnić.
-ład
+{Rozwiązanie}[thm]{Rozwiązanie}
-Poniższe napisy nie są formułami
-* <math>p \Rightarrow \Rightarrow q</math>
+{Hint}[thm]{Hint}
-* <math>\neg \neg \neg</math>
-* "ten napis na pewno nie jest formułą"
-* <math>(p \Rightarrow \neg q))</math>
+{equation}{section}
-Poniższe napisy są formułami
+{kuba_preamble1}
-* <math>(p \Rightarrow (r \Rightarrow q))</math>
+{kuba_preamble2}
-* <math>\neg \neg \neg q</math>
-* <math>(p \Rightarrow \neg q)</math>
-ład
+==Wprowadzenie==
-{{cwiczenie|[Uzupelnij]||
-Rozmiarem formuły nazwiemy ilość występujących w niej spójników.
-Na przykład formuła <math>\neg \neg q</math> ma rozmiar 2, a formuła
-<math>(p\Rightarrow q)</math> ma rozmiar 1. Przypuśćmy, że jedyną zmienną zdaniową
-jaką wolno nam użyć jest <math>p</math>. Ile można skonstruować rożnych
-formuł o rozmiarze 3?
-; Solution.
+Logika zdaniowa jest językiem, który pozwala opisywać zależności
-: Oznaczmy przez <math>f_n</math> liczbę formuł o rozmiarze <math>n</math> (czyli liczbę
-formuł w których jest <math>n</math> spójników). Interesuje nas <math>f_3</math>. Każda
-formuła o rozmiarze 3 powstaje albo z dwóch formuł o rozmiarach 1
-poprzez połączenie ich spójnikiem <math>\Rightarrow</math> albo z jednej formuły o
-rozmiarze 2 poprzez dodanie do niej spójnika <math>\neg</math>. Co
-więcej każda taka formuła powstaje tylko w jeden sposób. Wynika
-stąd następująca zależność:
-<center><math>
+pomiędzy zdaniami. Przykładem może być zdanie:
-f_3= f_2 + (f_1)^2
-</math></center>
-Wiemy, że są tylko dwie formuły o rozmiarze 1, są to <math>\neg p</math> oraz
-<math>p \Rightarrow p</math>. Stąd mamy <math>f_1=2</math>. Dla formuł o rozmiarze 2 możemy
-zauważyć podobną zależność. Każda taka formuła jest albo zbudowana z
-dwóch formuł z których jedna (niekoniecznie pierwsza) ma rozmiar 1 a
-druga 0  za pomocą <math>\Rightarrow</math>, albo jest zbudowana z formuły o rozmiarze
-za pomocą negacji. Zauważmy też, że istnieje formuła o rozmiarze
-, jest to <math>p</math>. Mamy więc następujący wzór dla <math>f_2</math>
-<center><math>
+Jeśli n jest liczbą pierwszą to n jest liczbą nieparzystą lub n jest
-f_2= 1 \cdot f_1 + f_1 \cdot 1 +f_1 = 3 \cdot f_1
+równe 2.
-</math></center>
-Z dwóch ostatnich wzorów otrzymujemy
-<center><math>
-f_3= 3 \cdot f_1 + (f_1)^2= 6+4 = 10
+W powyższym zdaniu spójniki "'jeśli"' [..] "'to"',
-</math></center>
-Skoro jest ich niewiele to możemy wszystkie wypisać
+"'lub"' mówią o związkach które zachodzą pomiędzy zdaniami:
-:# <math>\neg \neg \neg p</math>
-:# <math>\neg \neg (p \Rightarrow p)</math>
-:# <math>\neg (p \Rightarrow \neg p)</math>
+# "n jest liczbą pierwszą,"
-:# <math>\neg (p \Rightarrow (p\Rightarrow p))</math>
-:# <math>\neg (\neg p \Rightarrow  p)</math>
-:# <math>\neg ((p\Rightarrow p) \Rightarrow  p)</math>
+# "n jest liczbą nieparzystą,"
-:# <math> (\neg p)\Rightarrow  (\neg p)</math>
-:# <math> (\neg p)\Rightarrow  (p \Rightarrow p)</math>
-:# <math> (p \Rightarrow p) \Rightarrow  (\neg p)</math>
+# "n jest równe 2."
-:# <math> (p \Rightarrow p)\Rightarrow  (p \Rightarrow p)</math>
-}}
-Język logiki zdaniowej można równoważnie zdefiniować nie
+Oznaczmy powyższe zdania przez <math>p,q,r</math> (w takiej właśnie
-używając nawiasów za pomocą Odwrotnej Notacji Polskiej
-Odwrotna Notacja Polska.
-==Aksjomatyka Klasycznego Rachunku Zdań==
+kolejności). Używając symboli, które zwyczajowo odpowiadają
-Podobnie jak nie wszystkie zdania języka naturalnego mają sens, nie
+potocznemu rozumieniu spójników <math>\textbf{jeśli} [..] \textbf{to},
-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===
+\textbf{lub}</math> oraz powyższych oznaczeń otrzymamy formułę
-Wielu matematyków zgadza się dzisiaj co do tego że zdania pasujące
-do poniższych schematów powinny być uznane za prawdziwe:
-Aksjomaty klasycznego rachunku zdań.
-# <math>(\phi \Rightarrow (\psi \Rightarrow \phi))</math> (formuła ta jest nazywana
-aksjomatem K)
-# <math>(\phi \Rightarrow (\nu \Rightarrow \psi) \Rightarrow \left((\phi \Rightarrow \nu) \Rightarrow
+<center><math>
-(\phi \Rightarrow \nu) \right)</math> (formuła ta jest nazywana
-aksjomatem S)
-# <math>(\neg \phi \Rightarrow \psi) \Rightarrow (\neg \phi \Rightarrow \neg
-\psi) \Rightarrow \phi</math>
-Zdania pasujące do powyższych schematów to wszystkie zdania które
-można otrzymać podstawiając w miejsce <math>\phi, \nu, \psi</math> dowolne
-formuły.
-===Reguła dowodzenia===
+p \Rightarrow (q \vee r).
+</math></center>
-Przyglądnijmy się teraz jak posługujemy się implikacją we
-wniskowaniu. W przykładzie z początku wykładu implikacja odpowiadała
-konstrukcji językowej:
-"'jeśli"' <math>\phi</math> "'to"' <math>\psi</math>.
-W takim przypadku jeśli akceptujemy powyższą implikacjię jako zdanie
+Jeśli powyższą formułę uznamy za prawdziwą to może nam ona posłużyć
-prawdziwe oraz jeśli zdanie <math>\phi</math> jako prawdziwe to powinniśmy
-także zaakceptować <math>\psi</math>. 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
-<center><math>
+do otrzymania nowych wniosków. Na przykład jeśli o jakiejś liczbie n
-\frac{\phi \Rightarrow \psi, \phi}{\psi}.
+będziemy wiedzieć, że jest liczbą pierwszą oraz, że nie jest
-</math></center>
-Reguła modus ponens posłuży nam do uzupełniania zbioru aksjomatów  o
+nieparzysta to klasyczny rachunek zdań pozwoli nam formalnie
-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.
-Ciąg formuł <math>\phi_0, \dots ,\phi_n</math> jest dowodem formuły <math>\psi</math>
+wywnioskować fakt że liczba n jest równa 2. Podsumowując, jeśli
-wtedy i tylko wtedy, gdy:
-# <math>\phi_n</math> jest formułą <math>\psi</math>
+uznamy za prawdziwe następujące zdania:
-# dla każdego <math>i\leq n</math> formuła <math>\phi_i</math> jest aksjomatem
-lub istnieją <math>j,k <i</math> takie, że formuła <math>\phi_i</math>
-jest wynikiem zastosowania reguły modus ponens do
-formuł <math>\phi_j, \phi_k</math>.
-W drugim punkcie powyższej definicji jeśli formuła <math>\phi_i</math> nie jest
-aksjomatem (a więc powstaje przez zastosowanie MP) to formuły
-<math>\phi_j,\phi_k</math> muszą pasować do przesłanek reguły MP, a więc
-<math>\phi_j</math> musi być postaci <math>\phi_k \Rightarrow \phi_i</math> lub <math>\phi_k</math> postaci
-<math>\phi_j \Rightarrow \phi_i</math>.
-Formułę nazywamy "twierdzeniem klasycznego rachunku zdań"
+# <math> p \Rightarrow (q \vee r) </math>,
-jeśli istnieje jej dowód  z aksjomatów klasycznego rachunku
-zdań [[##defn:AksjomatyKRZ|Uzupelnic defn:AksjomatyKRZ|]].
-===Przykład===
-Zastanówmy się na formułą postaci <math>\phi \Rightarrow \phi</math>. Intuicja
-podpowiada, że taką formułę powinniśmy uznać za prawdziwą. Nie
-pasuje ona jednak do żadnego ze schematów aksjomatów
-[[##defn:AksjomatyKRZ|Uzupelnic defn:AksjomatyKRZ|]]. 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.
-# <math>[\phi \Rightarrow [(q \Rightarrow \phi) \Rightarrow \phi)]\Rightarrow [[\phi \Rightarrow (q \Rightarrow \phi)] \Rightarrow [\phi \Rightarrow
+# <math>p </math>,
-\phi]]</math> formuła ta jest aksjomatem zgodnym ze schematem S
-# <math>\phi \Rightarrow [(q \Rightarrow \phi) \Rightarrow \phi]</math> aksjomat zgodny ze
-schematem K
-# <math>(\phi \Rightarrow (q \Rightarrow \phi)) \Rightarrow (\phi \Rightarrow \phi)</math> z modus ponens z
-formuł 1 i 2.
-# <math>\phi \Rightarrow [q \Rightarrow \phi]</math> aksjomat zgodny ze schematem
+# <math> \neg q </math> (przez <math>\neg</math> oznaczamy negację)
-K
-# <math>(\phi \Rightarrow \phi)</math> z modus ponens z formuł 3 i 4
-===Podsumowanie===
-Klasyczny rachunek zdań, czyli zbiór formuł które uznajemy za
+to zgodnie z klasycznym rachunkiem (może lepiej z intuicją?) zdań
-prawdziwe zdefiniowaliśmy wyróżniając pewne formuły jako aksjomaty
-[[##defn:AksjomatyKRZ|Uzupelnic defn:AksjomatyKRZ|]] 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ć.
-Warto przyglądnąć się przyjętym aksjomatom i zastanowić się
+powinniśmy uznać za prawdziwe zdanie <math>r</math>, czyli "n jest równe
-jakim zdaniom odpowiadają i czy rzeczywiście bylibyśmy skłonni
-uznać je za prawdziwe. Pomocne może być interpretowanie formuł
-postaci <math>\phi \Rightarrow (\nu \Rightarrow \psi)</math> jako ",,jeśli prawdziwe jest
-<math>\phi</math> i prawdziwe jest <math>\nu</math> to prawdziwe jest <math>\psi</math>"". W
-kolejnych rozdziałach przekonamy się że taka interpretacja jest
-uzasadniona.
-==Matryca boolowska==
+". Powyższy schemat wnioskowania można również opisać formułą
-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.
-Dwuelementową matrycą boolowską nazywamy zbiór dwuelementowy
-<math>\mathbb{B}=\{0,1\}</math> w którym 1 jest wyróżnioną wartością prawdy, wraz z
-dwoma funkcjami odpowiadającymi za interpretacje spójników
-<math>\Rightarrow</math> oraz <math>\neg</math> zdefiniowanymi następująco
 <center><math>
-\begintabular {|c|c c|}\hline
-</math><math> & 0 & 1 \\\hline
-& 1 & 1 \\
-& 0 & 1 \\\hline
-\endtabular  \hspace{1cm}
-\begintabular {|c|c|}\hline
-</math>p<math> & </math> p<math> \\\hline
-& 1  \\
-& 0  \\\hline
-\endtabular
-</math></center>
-Wartościowaniem nazywamy funkcję która przypisuje zmiennym
-zdaniowym elementy zbioru <math>\mathbb{B}</math>. Wartościowanie zmiennych
-można rozszerzyć na wartościowanie formuł interpretując spójniki
-<math>\Rightarrow</math> oraz <math>\neg</math> jako funkcje zgodnie z tabelami
-[[##eq:tabeleInterpretacjiKRZ|Uzupelnic eq:tabeleInterpretacjiKRZ|]].
-ład
+\left((p \Rightarrow (q \vee r)) \wedge p \wedge (\neg q)\right) \Rightarrow
-Niech <math>v</math> będzie wartościowaniem zmiennych takim, że <math>v(p)=0,
+q.
-v(q)=1, v(r)=0</math>. Wtedy
-* formuła <math>q \Rightarrow p</math> jest wartościowana na
+</math></center>
-(będziemy to zapisywać jako <math>v(q \Rightarrow p)=0</math>),
-* formuła <math>r \Rightarrow (q \Rightarrow p)</math> jest wartościowana na 1 (czyli <math>v(r \Rightarrow (q \Rightarrow p))=1</math>)
-* formuła <math>\neg p \Rightarrow r</math> jest wartościowana na  0 (czyli <math>v(\neg p \Rightarrow r)=0</math>)
-ład
+W powyższej formule spójnik symbol <math>\wedge</math> odpowiada spójnikowi
-{{cwiczenie|[Uzupelnij]||
+"'i"' (oraz).
-Przy wartościowaniu <math>v</math> z przykładu [[##eg:wartosciowania|Uzupelnic eg:wartosciowania|]] jakie
-wartości przyjmują następujące formuły
-# <math>p \Rightarrow (q \Rightarrow r)</math>
-# <math>p \Rightarrow (p \Rightarrow q)</math>
+Dzięki rachunkowi zdań możemy precyzyjnie opisywać schematy
-# <math>\neg \neg q \Rightarrow p</math>
+wnioskowania i zdania złożone oraz oceniać ich prawdziwość.
-# <math>(\neg q\Rightarrow q) \Rightarrow (q \Rightarrow \neg q)</math>
-; Solution.
-:
-:# <math>v(p \Rightarrow (q \Rightarrow r))=1</math>
+==Język logiki zdaniowej==
-:# <math>v(p \Rightarrow (p \Rightarrow q))=1</math>
-:# <math>v(\neg \neg q \Rightarrow p)=0</math>
-:# <math>v((\neg q\Rightarrow q) \Rightarrow (q \Rightarrow \neg q))=0</math>
+Zaczniemy od definicji języka logiki zdaniowej. Składa się on z
-}}
+formuł zdefiniowanych następująco:
-{{cwiczenie|[Uzupelnij]||
+{formuła logiki zdaniowej}
-# Podaj przykład wartościowania zmiennych tak aby poniższe formuły
-były wartościowane na 0
-## <math>p \Rightarrow (q \Rightarrow r)</math>
-## <math>(\neg p \Rightarrow q)</math>
+# zmienna zdaniowa jest formułą (zmienne zdaniowy oznaczamy
-## <math>(p\Rightarrow q) \Rightarrow q</math>
+zwykle literami alfabetu rzymskiego np. <math>p,q,r</math>)
-# Podaj przykład wartościowania zmiennych tak aby poniższe formuły
-były wartościowane na 1
-## <math>\neg (p \Rightarrow q)</math>
-## <math>\neg (\neg p \Rightarrow  \neg q)</math>
+# jeśli <math>\phi</math> oraz <math>\psi</math> są formułami to <math>(\phi
-## <math>(\neg q\Rightarrow q) \Rightarrow (q \Rightarrow \neg q)</math>
+\Rightarrow \psi)</math> jest formułą (spójnik <math>\Rightarrow</math> nazywamy implikacją)
-; Solution.
-: Wartościowania będziemy oznaczać przez <math>v</math>
-:#
-:## <math>v(p)=1, v(q)=1, v(r)=0</math>
+# jeśli <math>\phi</math> jest formułą to <math>\neg \phi</math> jest formułą
-:## <math>v(p)=0,v(q)=0</math>
+(spójnik <math>\neg</math> nazywamy negacją)
-:## <math>v(p)=0,v(q)=0</math>
-:#
-:## <math>v(p)=1,v(q)=0</math>
+# nic innego nie jest formułą.
-:## <math>v(p)=0,v(q)=1)</math>
-:## <math>v(q)=1</math>
-}}
+Powyższa definicja mówi, że formułami nazywamy te napisy które dają
-===Twierdzenie o pełności===
+się skonstruować ze zmiennych zdaniowych przy pomocy spójników
-Zauważmy, że istnieją formuły, które dla każdego wartościowania
+<math>\Rightarrow</math> oraz <math>\neg</math>.
-zmiennych zdaniowych zawsze przyjmują wartość 1 (np. <math>p \Rightarrow p</math>).
-Takie formuły będziemy nazywać "'tautologiami"'.
-{{cwiczenie|[Uzupelnij]||
-Sprawdź czy poniższe formuły są tautologiami
-# <math>(\phi \Rightarrow (\psi \Rightarrow \phi))</math>
+Zgodnie z powyższą definicją nie jest formułą napis <math>p\Rightarrow q</math>,
-# <math>(\phi \Rightarrow (\nu \Rightarrow \psi) \Rightarrow \left((\phi \Rightarrow \nu) \Rightarrow
+gdyż brakuje w nim nawiasów. Pomimo, iż poprawnie powinniśmy
-(\phi \Rightarrow \nu) \right)</math>
+napisać <math>(p\Rightarrow q)</math> możemy przyjąć że nie będzie konieczne
-# <math>(\neg \phi \Rightarrow \psi) \Rightarrow (\neg \phi \Rightarrow \neg
+pisanie nawiasów, jeśli nawiasy można jednoznacznie uzupełnić.
-\psi) \Rightarrow \phi</math>
-# <math>((\phi \Rightarrow q) \Rightarrow p) \Rightarrow p</math>
-{hint}{1}
-; Hint .
-: Spróbuj poszukać wartościowań dla których formuła przyjmuje
-wartość 0
-{hint}{1}
+ład
-; Hint .
-: Można też sprawdzić wszystkie możliwości wartościowań.
-; Solution.
+Poniższe napisy nie są formułami
-:   }}
-Nie przez przypadek pierwsze trzy formuły z poprzedniego zadania
-odpowiadają aksjomatom klasycznego rachunku zdań
-[[##defn:AksjomatyKRZ|Uzupelnic defn:AksjomatyKRZ|]]. Okazuje się że istnieje ścisły związek
-pomiędzy tautologiami a twierdzeniami klasycznego rachunku zdań. Mówi o tym ważny wynik Emil Post.
-{{twierdzenie|[Uzupelnij]||
-{Post 1921}
-Formuła jest twierdzeniem klasycznego rachunku zdań wtedy i
+* <math>p \Rightarrow \Rightarrow q</math>
-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ń).
-{{cwiczenie|[Uzupelnij]||
+* <math>\neg \neg \neg</math>
-Udowodnij że każde twierdzenie klasycznego rachunku zdań jest tautologią.
-{hint}{1}
+* "ten napis na pewno nie jest formułą"
-; Hint .
-: Pokazaliśmy już w zadaniu
-[[##zad:aksjomatyTatuologie|Uzupelnic zad:aksjomatyTatuologie|]], że aksjomaty są tautologiami.
-Zacznij od pokazania, że zastosowanie reguły MP  do tautologii daje
-tautologię.
-{hint}{1}
-; Hint .
-: Udowodnij, twierdznie przez indukcję ze względu na długość
-dowodu.
-; Solution.
-:   }}
-===Inne spójniki===
-Do tej pory jedynymi rozważanymi spójnikami była implikacja i
+* <math>(p \Rightarrow \neg q))</math>
-negacja. W analogiczny sposób do [[##eq:tabeleInterpretacjiKRZ|Uzupelnic eq:tabeleInterpretacjiKRZ|]]
-możemy wprowadzać kolejne spójniki. Często używane spójniki to
-koniunkcja (spójnik "'i"') oznaczana przez <math>\wedge</math> oraz
-alternatywa (spójnik "'lub"') oznaczana przez <math>\vee</math>, które
-będziemy interpretować w następujący sposób:
-<center><math>
-\begintabular {|c|c c|}\hline
-</math><math> & 0 & 1 \\\hline
-& 0 & 0 \\
-& 0 & 1 \\\hline
-\endtabular  \hspace{1cm}
-\begintabular {|c|c c|}\hline
-</math><math> & 0 & 1 \\\hline
-& 0 & 1 \\
-& 1 & 1 \\\hline
-\endtabular
-</math></center>
-Zgodnie z intuicją koniunkcja <math>\phi \wedge \psi</math> jest wartościowana
+Poniższe napisy są formułami
-na 1 wtedy i tylko wtedy gdy zarówno <math>\phi</math> jak i <math>\psi</math> są
-wartościowane na 1. Alternatywa <math>\phi \vee \psi</math> jest wartościowana
-na 1 jeśli przynajmniej jedna z formuł <math>\phi, \psi</math> jest
-wartościowana na 1.
-Formuły <math>\phi</math> oraz <math>\psi</math> są "równoważne" (oznaczamy ten fakt
-przez <math>\phi \equiv \psi</math> wtedy i tylko wtedy gdy dla każdego
-wartościowania formuła <math>\phi</math> przyjmuje tą samą wartość co
-formuła <math>\psi</math>.
-{{cwiczenie|[Uzupelnij]||
-Udowodnij, że następujące formuły są równoważne
+* <math>(p \Rightarrow (r \Rightarrow q))</math>
-# <math>\phi \vee \psi \equiv \neg \phi \Rightarrow \psi </math>
-# <math>\phi \wedge \psi \equiv \neg (\phi \Rightarrow \neg \psi)</math>
-; Solution.
+* <math>\neg \neg \neg q</math>
-:
-:# Lewa strona jest fałszywa jedynie gdy <math>\phi</math> oraz
-<math>\psi</math> są wartościowane na 0. Prawa strona jest fałszywa
-wtedy i tylko wtedy kiedy <math>\neg \phi</math> jest wartościowane na
-oraz <math>\psi</math> 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 <math>\phi</math> oraz
-<math>\psi</math> są wartościowane na 0, a więc jest równoważna lewej.
-:# Lewa strona jest prawdziwa jedynie gdy <math>\phi</math> oraz
-<math>\psi</math> są wartościowane na 1. Prawa strona jest prawdziwa
-wtedy i tylko wtedy kiedy <math>\neg (\phi \Rightarrow \neg \psi)</math> jest wartościowane na
-, więc wtedy gdy <math>(\phi \Rightarrow \neg \psi)</math> jest wartościowane na 0. To z kolei
-zdarzyć się może jedynie gdy <math>\phi</math> jest wartościowane na 1
-i <math>\neg \psi</math> na 0, a więc wtedy gdy zarówno <math>\phi</math> jak i
-<math>\psi</math> są wartościowane na 1. Wobec tego obie formuły są
-równoważne.
-Równie dobrym rozwiązaniem jest sprawdzenie wszystkich
+* <math>(p \Rightarrow \neg q)</math>
-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 <math>\wedge</math> lub <math>\vee</math> można zastąpić równoważną formułą w
-której jedynymi spójnikami są <math>\Rightarrow</math> oraz <math>\neg</math>. 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.
-{{cwiczenie|[Uzupelnij]||
+ład
+{{cwiczenie|[Uzupelnij]||
-Udowodnij następujące równoważności
-# <math>\neg \neg p \equiv p</math>
-# <math>p\Rightarrow q \equiv \neg p \vee q</math>
+Rozmiarem formuły nazwiemy ilość występujących w niej spójników.
-# <math>p \Rightarrow (q \Rightarrow r) \equiv (p \wedge q) \Rightarrow r</math>
+Na przykład formuła <math>\neg \neg q</math> ma rozmiar 2, a formuła
-# <math>\neg( p \wedge q) \equiv \neg p \vee \neg q</math>
+<math>(p\Rightarrow q)</math> ma rozmiar 1. Przypuśćmy, że jedyną zmienną zdaniową
-# <math>\neg( p \vee q) \equiv \neg p \wedge \neg q</math>
+jaką wolno nam użyć jest <math>p</math>. Ile można skonstruować rożnych
-# <math>p \wedge (q \vee r) \equiv (p \wedge q) \vee (p\wedge r)</math>
+formuł o rozmiarze 3?
-# <math>p \vee (q \wedge r) \equiv (p \vee q) \wedge (p\vee r)</math>
-# <math>(p \Rightarrow q) \Rightarrow (\neg p \Rightarrow \neg q)</math>
 ; Solution.
-: Przedstwiamy przykładowe dowody kilku pierwszych równoważności.
-:# Jeśli <math>p</math> jest wartościowane na 1, to zgodnie z tabelą dla negacji [[##eq:tabeleInterpretacjiKRZ|Uzupelnic eq:tabeleInterpretacjiKRZ|]]
+: Oznaczmy przez <math>f_n</math> liczbę formuł o rozmiarze <math>n</math> (czyli liczbę
-<math>\neg p</math> jest wartościowane na 0 i <math>\neg \neg p</math> jest wartościowane na 1. Jeśli <math>p</math> jest wartościowane
-na 0 to <math>\neg p</math> jest wartościowane na 1 i <math>\neg \neg p</math> jest wartościowane na 0. Formuły przyjmują
-te same wartości dla każdego wartościowania więc są równoważne.
-:# Jedyną możliwością aby lewa strona była fałszywa jest
+formuł w których jest <math>n</math> spójników). Interesuje nas <math>f_3</math>. Każda
-aby <math>p</math> było wartościowane na 1, a <math>q</math> na 0. Prawa
-stona jest fałszywa jedynie gdy <math>\neg p</math> oraz <math>q</math> są wartościowane
+formuła o rozmiarze 3 powstaje albo z dwóch formuł o rozmiarach 1
-na 0. Czyli prawa strona jest fałszywa jedynie
-gdy <math>p</math> jest wartościowane na 1 i <math>q</math> na 0. Formuły są więc
-równoważne.
-:# Analogicznie do poprzedniego punktu łatwo się
+poprzez połączenie ich spójnikiem <math>\Rightarrow</math> albo z jednej formuły o
-przekonać, że jedynym wartościowaniem które falsyfikuje lewą
-stronę jest takie które wartościuje <math>p</math> i <math>q</math> na 1 oraz <math>r</math>
-na 0. Tą samą własność ma formuła po prawej stronie, więc
-formuły są równoważne.
-:# Przykład rozwiązania przez rozważenie wszystkich
+rozmiarze 2 poprzez dodanie do niej spójnika <math>\neg</math>. Co
-możliwości
-<center><math>
+więcej każda taka formuła powstaje tylko w jeden sposób. Wynika
-\begintabular {|c|c|c|c|c|c|c|}\hline
+stąd następująca zależność:
-</math>p<math> & </math>q<math> & </math>p q<math> & </math> (p q)<math>& </math> p<math> & </math> q<math>&  </math>  p   q<math>\\\hline
-& 0 & 0 & 1 & 1 & 1 & 1\\
-& 1 & 0 & 1 & 1 & 0 & 1\\
-& 0 & 0 & 1 & 0 & 1 & 1\\
-& 1 & 1 & 0 & 0 & 0 & 0\\\hline
-\endtabular  \hspace{1cm}
-</math></center>
-W pierwszych dwóch kolumnach są zapisane wartościowania
-zmiennych <math>p</math> i <math>q</math> 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.
-:# W równoważności z poprzedniego punktu, podstawiąjąc za <math>p</math>
-formułę <math>\neg p</math> oraz za <math>q</math> formułę <math>\neg q</math> otrzymamy
-równoważność
 <center><math>
-\neg( \neg p \wedge \neg q) \equiv \neg \neg p \vee \neg \neg
-q.
-</math></center>
-Stosując dwukrotnie równoważność z pierwszego punktu do prawej strony
-otrzymujemy
-<center><math>
+f_3= f_2 + (f_1)^2
-\neg( \neg p \wedge \neg q) \equiv  p \vee     q.
 </math></center>
-Negując tą równoważność obustronnie otrzymamy
-<center><math>
-\neg \neg( \neg p \wedge \neg q) \equiv\neg(  p \vee     q).
+Wiemy, że są tylko dwie formuły o rozmiarze 1, są to <math>\neg p</math> oraz
-</math></center>
+<math>p \Rightarrow p</math>. Stąd mamy <math>f_1=2</math>. Dla formuł o rozmiarze 2 możemy
-Stosując równoważność z pierwszego punktu do lewej strony
+zauważyć podobną zależność. Każda taka formuła jest albo zbudowana z
-otrzymamy szukaną równoważność.
-}}
+dwóch formuł z których jedna (niekoniecznie pierwsza) ma rozmiar 1 a
-{{cwiczenie|[Uzupelnij]||
+druga 0  za pomocą <math>\Rightarrow</math>, albo jest zbudowana z formuły o rozmiarze
-Sprawdź które z następujących formuł są tautologiami
+za pomocą negacji. Zauważmy też, że istnieje formuła o rozmiarze
-# <math>( (p \vee r)\wedge( q \vee \neg r) )\Rightarrow (p \vee q)</math>
+, jest to <math>p</math>. Mamy więc następujący wzór dla <math>f_2</math>
-# <math>(p \vee q) \Rightarrow ( (p \vee r)\wedge( q \vee \neg r)
-)</math>
-# <math>( (p \wedge r)\vee( q \wedge \neg r) )\Rightarrow (p \wedge
-q)</math>
-# <math>(p \wedge q) \Rightarrow ( (p \wedge r)\vee( q \wedge \neg r)
+<center><math>
-)</math>
-; Solution.
-:
-:# Spróbujmy znaleźć wartościowanie które falsyfikuje tą
-formułę. Skoro implikacja ma być fałszywa to formuła <math>(p \vee q)</math> (czyli następnik) musi być
-fałszywa. Tak jest tylko wtedy kiedy zarówno <math>p</math> jak i <math>q</math> są
-fałszywe. Zobaczmy co się wtedy dzieje z poprzednikim implikacji,
-czyli formułą
-<center><math>
+f_2= 1 \cdot f_1 + f_1 \cdot 1 +f_1 = 3 \cdot f_1
-(p \vee r)\wedge( q \vee \neg r).
 </math></center>
-Jeśli teraz ustalimy <math>r</math> na fałsz to <math>(p \vee q)</math> będzie
-fałszywe a jeśli ustalimy <math>r</math> na
-prawdę to <math>( q \vee \neg r)</math> 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ą.
-:# Formuła nie jest tautologią. Wystarczy wartościować <math>p</math> i
-<math>r</math> na prawdę i <math>q</math> na fałsz.
-:# Formuła nie jest tautologią. Wystarczy wartościować <math>p</math> i
+Z dwóch ostatnich wzorów otrzymujemy
-<math>r</math> na prawdę i <math>q</math> na fałsz.
-:# Przykład rozwiązania przez rozważenie wszystkich
-możliwości
 <center><math>
-\begintabular {|c|c|c|c|c|c|c|c|}\hline
-</math>p<math> & </math>q<math> & </math>r<math> &</math>(p  q)<math> &</math> (p  r)<math>&</math> ( q   r)<math>
-&</math> (p  r)( q   r)<math>& </math>(p  q)  ( (p  r)( q   r))<math>\\\hline
+f_3= 3 \cdot f_1 + (f_1)^2= 6+4 = 10
-& 0 & 0 & 0 & 0 & 0 & 0 & 1 \\
-& 0 & 1 & 0 & 0 & 0 & 0& 1 \\
-& 1 & 0 & 0 & 0 & 1 & 1& 1 \\
-& 1 & 1 & 0 & 0 & 0 & 0& 1 \\
-& 0 & 0 & 0 & 0 & 0 & 0& 1 \\
-& 0 & 1 & 0 & 1 & 0 & 1& 1 \\
-& 1 & 0 & 1 & 0 & 1 & 1& 1 \\
-& 1 & 1 & 1 & 1 & 0 & 1& 1 \\\hline
-\endtabular  \hspace{1cm}
 </math></center>
-W kolumnie odpowiadającej badanej formule są same 1, więc
-jest ona tautologią.
-}}
-Binarne spójniki logiczne interpretowaliśmy jako funkcje z <math>\mathbb{B}
+Skoro jest ich niewiele to możemy wszystkie wypisać
-\times \mathbb{B} \rightarrow \mathbb{B}</math>. 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.
-W poniższej tabeli przedstawiamy wszystkie spójniki binarne.
+:# <math>\neg \neg \neg p</math>
-<center><math>
-\begintabular {|c|c|c|c|c|c||c|}\hline
-Numer & </math>p<nowiki>=</nowiki>0<math> &</math> p<nowiki>=</nowiki>0<math> &</math> p<nowiki>=</nowiki>1<math> &</math> p<nowiki>=</nowiki>1<math> && \\
-funkcji& </math>q<nowiki>=</nowiki>0<math> & </math>q<nowiki>=</nowiki>1<math> & </math>q<nowiki>=</nowiki>0<math> & </math>q<nowiki>=</nowiki>1<math> && \\ \hline
-& 0 & 0 & 0 & 0 && </math>F<math>\\
-& 0 & 0 & 0 & 1 && </math><math>\\
-& 0 & 0 & 1 & 0 && </math>(p  q)<math>\\
-& 0 & 0 & 1 & 1 && </math>p<math> \\
-& 0 & 1 & 0 & 0 && </math> (q p)<math> \\
-& 0 & 1 & 0 & 1 && </math>q<math> \\
-& 0 & 1 & 1 & 0 && </math>XOR<math> \\
-& 0 & 1 & 1 & 1 && </math><math> \\
-& 1 & 0 & 0 & 0 && </math>NOR<math> \\
-& 1 & 0 & 0 & 1 && </math><math> \\
-& 1 & 0 & 1 & 0 && </math> q<math> \\
-& 1 & 0 & 1 & 1 && </math> q  p<math> \\
-& 1 & 1 & 0 & 0 && </math>  p <math>\\
-& 1 & 1 & 0 & 1 && </math> p  q <math>\\
-& 1 & 1 & 1 & 0 && </math> NAND<math> \\
-& 1 & 1 & 1 & 1 && </math>T <math>\\\hline
-\endtabular  \hspace{1cm}
-</math></center>
-Spójnik binarny <math>\circ</math> będziemy nazywać "przemiennym" jeśli zachodzi
+:# <math>\neg \neg (p \Rightarrow p)</math>
-następująca równoważność
-<center><math>
-p \circ q \equiv q \circ p
+:# <math>\neg (p \Rightarrow \neg p)</math>
-</math></center>
-{{cwiczenie|[Uzupelnij]||
-Sprawdź następujące równoważności
-# <math>x NAND y \equiv \neg (x \wedge y)</math>
+:# <math>\neg (p \Rightarrow (p\Rightarrow p))</math>
-# <math>x NOR y \equiv \neg (x \vee y)</math>
-# <math>x XOR y \equiv \neg (x \Leftrightarrow y)</math>
-; Solution.
+:# <math>\neg (\neg p \Rightarrow  p)</math>
-:   }}
-{{cwiczenie|[Uzupelnij]||
-Ile spójników binarnych jest przemiennych? Wypisz je wszystkie.
+:# <math>\neg ((p\Rightarrow p) \Rightarrow  p)</math>
-{hint}{1}
-; Hint .
-: Wygodnie jest reprezentować spójniki binarne w tabeli
-kwadratowej. Na przykład alternatywę
-zdefiniowaliśmy jako
-<center><math>
-\begintabular {|c|c c|}\hline
+:# <math> (\neg p)\Rightarrow  (\neg p)</math>
-</math><math> & 0 & 1 \\\hline
-& 0 & 1 \\
-& 1 & 1 \\\hline
-\endtabular .
-</math></center>
-Jaką własność musi posiadać tabela aby spójnik definiowany przez nią był
-przemienny?
-; Solution.
-: Dla przemienności spójnika <math>\circ</math> istotne jest aby <math> 1\circ 0 =  0 \circ 1</math>. Dla pozostałych
-przypadków wartościowań równoważnośc [[##eq:przemienność|Uzupelnic eq:przemienność|]]
-jest zawsze spełniona. Każdy spójnik binarny możemy
-zdefiniować za pomocą tabelki kwadratowej, np. alternatywę
-zdefiniowaliśmy jako
-<center><math>
+:# <math> (\neg p)\Rightarrow  (p \Rightarrow p)</math>
-\begintabular {|c|c c|}\hline
-</math><math> & 0 & 1 \\\hline
-& 0 & 1 \\
-& 1 & 1 \\\hline
-\endtabular .
-</math></center>
-Warunek przemienności oznacza, że wartość w polu o
+:# <math> (p \Rightarrow p) \Rightarrow  (\neg p)</math>
-współrzędnych <math>(0,1)</math> jest równa wartości w polu o
-współrzędnych <math>(1,0)</math>. Takich tabel jest 8, więc mamy 8
-spójników przemiennych. Nietrudno je teraz odnaleźć w tabeli
-[[##defn:spójniki|Uzupelnic defn:spójniki|]]. Są to
-:# <math>F</math>
-:# <math>\wedge</math>
-:# <math>XOR</math>
+:# <math> (p \Rightarrow p)\Rightarrow  (p \Rightarrow p)</math>
-:# <math>\vee</math>
-:# <math>NOR</math>
-:# <math>\Leftrightarrow</math>
+}}
-:# <math>NAND</math>
-:# <math>T</math>
-}}
+Język logiki zdaniowej można równoważnie zdefiniować nie
-Spójnik binarny <math>\circ</math> będziemy nazywać "łącznym" jeśli zachodzi
+używając nawiasów za pomocą Odwrotnej Notacji Polskiej
-następująca równoważność
-<center><math>
+Odwrotna Notacja Polska.
-p \circ (q \circ r) \equiv     (p \circ q) \circ r.
-</math></center>
-Jeśli spójnik <math>\circ</math> jest łączny to dowolne dwie formuły, które są zbudowane
-jedynie ze spójników <math>\circ</math> 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.
-{{cwiczenie|[Uzupelnij]||
+==Aksjomatyka Klasycznego Rachunku Zdań==
-Udowodnij, że następujące spójniki są łączne
-# <math>\vee</math>
+Podobnie jak nie wszystkie zdania języka naturalnego mają sens, nie
-# <math>\wedge</math>
+wszystkie formuły opisują prawdziwe schematy wnioskowania, lub
-# <math>\Leftrightarrow</math>
+zdania które bylibyśmy skłonni uznać za prawdziwe. W tym rozdziale
-# <math>XOR</math>
+skupimy się na tym które spośród wszystkich formuł zdaniowych
-; Solution.
+wyróżnić jako prawdziwe.
-:
-:# Formuła <math>(p \vee q) \vee r</math> jest fałszywa jedynie
-wtedy gdy <math>p</math>,<math>q</math> i <math>r</math> są wartościowane na fałsz. Tak
-samo jest dla formuły <math>p \vee( q \vee r )</math> więc są one
-równoważne.
-:# Formuła <math>(p \wedge q) \wedge r</math> jest prawdziwa jedynie
-wtedy gdy <math>p</math>,<math>q</math> i <math>r</math> są wartościowane na prawdę. Tak
-samo jest dla formuły <math>p \wedge( q \wedge r )</math> więc są one
-równoważne.
-:# Zbadamy równoważność formuł <math>(p \Leftrightarrow q) \Leftrightarrow r</math>
+===Aksjomaty===
-i <math> p \Leftrightarrow(q \Leftrightarrow r)</math> za pomocą tabeli
-<center><math>
-\begintabular {|c|c|c|c|c|c|c|}\hline
-</math>p<math> &</math> q<math> &</math> r <math>&</math>(p  q)<math> & </math>(p  q)  r<math>& </math>(q  r )<math>&</math> p (q  r)<math>\\\hline
-& 0 & 0 & 1 & 0 & 1 & 0 \\
-& 0 & 1 & 1 & 1 & 0 & 1 \\
-& 1 & 0 & 0 & 1 & 0 & 1 \\
-& 1 & 1 & 0 & 0 & 1 & 0 \\
-& 0 & 0 & 0 & 1 & 1 & 1 \\
-& 0 & 1 & 0 & 0 & 0 & 0 \\
-& 1 & 0 & 1 & 0 & 0 & 0 \\
-& 1 & 1 & 1 & 1 & 1 & 1 \\\hline
-\endtabular  \hspace{1cm}
-</math></center>
-Kolumna 4 i 6 są identyczne więc odpowiadające im
+Wielu matematyków zgadza się dzisiaj co do tego że zdania pasujące
-formuły są równoważne. Spójnik <math>\Leftrightarrow</math> jest więc łączny.
+do poniższych schematów powinny być uznane za prawdziwe:
-:# ...
+Aksjomaty klasycznego rachunku zdań.
-}}
-Możemy również rozważać spójniki 3 i więcej argumentowe. Spójnik
-<math>k</math>-argumetowy powinien odpowiadać funkcji <math>\mathbb{B}^k \rightarrow \mathbb{B}</math>.
-ład
-W poniższej tabeli przedstawiamy przykład spójnika trójargumentowego
-<center><math>
+# <math>(\phi \Rightarrow (\psi \Rightarrow \phi))</math> (formuła ta jest nazywana
+aksjomatem K)
-\begintabular {|c c c|c||}\hline
-</math>p<math> & </math>q<math> & </math>r<math> &</math>(p, q,r)<math> \\\hline
-& 0 & 0 & 0 \\
-& 0 & 1 & 1 \\
-& 1 & 0 & 1 \\
-& 1 & 1 & 0 \\
-& 0 & 0 & 1 \\
-& 0 & 1 & 0 \\
-& 1 & 0 & 0 \\
-& 1 & 1 & 1 \\\hline
-\endtabular  \hspace{1cm}
-</math></center>
-ład
-{{cwiczenie|[Uzupelnij]||
+# <math>(\phi \Rightarrow (\nu \Rightarrow \psi) \Rightarrow \left((\phi \Rightarrow \nu) \Rightarrow
-Udowodnij, że różnych spójników <math>k</math>-argumentowych jest dokładnie
+(\phi \Rightarrow \nu) \right)</math> (formuła ta jest nazywana
-<math>2^{2^k}</math>.
-; Solution.
+aksjomatem S)
-:   }}
-==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
-<math>\mathbb{B}</math>. Na przykład formuła <math>p \Rightarrow (q\Rightarrow r)</math> wyznacza funkcję
-<math>f_{p \Rightarrow (q\Rightarrow r)}</math> opisaną poniższą tabelą
-<center><math>
+# <math>(\neg \phi \Rightarrow \psi) \Rightarrow (\neg \phi \Rightarrow \neg
-\begintabular {|c|c|c|c|}\hline
+\psi) \Rightarrow \phi</math>
-p & q & r & </math>f_{p  (q r)}<math> \\\hline
-& 0 & 0 & 1 \\
-& 0 & 1 & 1 \\
-& 1 & 0 & 1 \\
-& 1 & 1 & 1 \\
-& 0 & 0 & 1 \\
-& 0 & 1 & 1 \\
-& 1 & 0 & 0 \\
-& 1 & 1 & 1 \\\hline
-\endtabular
-</math></center>
-Mówimy, wtedy że formuła <math>\phi</math> definuje funkcję <math>f_{\phi}</math>.
-Skończony zbiór funkcji boolowskich <math>\Gamma</math> 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 <math>\Gamma</math>.
-{{twierdzenie|[Uzupelnij]||
+Zdania pasujące do powyższych schematów to wszystkie zdania które
-Zbiór <math>\{\wedge, \vee, \neg\}</math> jest funkcjonalnie pełny.
+można otrzymać podstawiając w miejsce <math>\phi, \nu, \psi</math> dowolne
-}}
-{{dowod|[Uzupelnij]||
+formuły.
-}}
-{{twierdzenie|[Uzupelnij]||
-Zbiory <math>\{\wedge,  \neg\}</math>, <math>\{\vee,  \neg\}</math> są funkcjonalnie pełne.
+===Reguła dowodzenia===
-}}
-{{dowod|[Uzupelnij]||
-}}
-Udowodnij, że zbiór <math>\{\Rightarrow,  \neg\}</math> jest funkcjonalnie
+Przyglądnijmy się teraz jak posługujemy się implikacją we
-pełny.
-{{twierdzenie|[Uzupelnij]||
+wniskowaniu. W przykładzie z początku wykładu implikacja odpowiadała
-Zbiór <math>\{NOR\}</math> jest funkcjonalnie pełny.
+konstrukcji językowej:
-}}
-Udowodnij, że zbiór <math>\{NAND\}</math> jest funkcjonalnie pełny.
-{{cwiczenie|[Uzupelnij]||
-Zdefiniuj alternatywę przy pomocy samej implikacji.
+"'jeśli"' <math>\phi</math> "'to"' <math>\psi</math>.
-; Solution.
-: Łatwo sprawdzić że formuła <math>p \Rightarrow (p \Rightarrow q)</math> jest równoważna
-formule <math>p\vee q</math>.
-}}
-Jakie funkcje binarne da się zdefiniować przy pomocy samej
-implikacji?
-{{cwiczenie|[Uzupelnij]||
+W takim przypadku jeśli akceptujemy powyższą implikacjię jako zdanie
-Udowodnij, że poniższe zbiory nie są funkcjonalnie pełne
+prawdziwe oraz jeśli zdanie <math>\phi</math> jako prawdziwe to powinniśmy
-# <math>\{\wedge\}</math>
+także zaakceptować <math>\psi</math>. Przedstawiony sposób wnioskowania nosi
-# <math>\{\vee\}</math>
+nazwę reguły "Modus Ponens" (nazywana też regułą odrywania, często będziemy używać skrótu MP) i jest
-# <math>\{\Leftrightarrow\}</math>
+skrótowo notowany w poniższy sposób
-# <math>\{XOR\}</math>
-; Solution.
-:
-:# Oznaczmy zbiór formuł w których jedynym spójnikiem jest <math>\wedge</math> przez
+<center><math>
-<math>F_\wedge</math>. Udowodnimy, że każda formuła z <math>F_\wedge</math> przyjmuje zawsze wartość 1, jeśli jej zmienne są
-wartościowane na 1. Rozmiarem formuły będziemy nazywać liczbę wystąpień spójnika <math>\wedge</math> w formule.
-Dowód będzie indukcyjny ze względu na
-rozmiar formuły.
-Baza indukcji: Każda formuła z <math>F_\wedge</math> o rozmiarze 0 jest postaci <math>x</math>, gdzie
-<math>x</math> jest zmienną. Wobec tego przy wartościowaniu zmiennych na 1 formuła <math>x</math> też jest
-wartościowana na 1. A więc każda formuła o rozmiarze 0 ma postulowaną własność.
-Krok indukcyjny: Ustalmy dowolne <math>n>0</math> i przyjmijmy, że
-wszystkie formuły o mniejszym rozmiarze mają postulowaną
-własność. Niech <math>\nu</math> będzie dowolną formułą z <math>F_\wedge</math> o rozmiarze
-<math>n</math>. Skoro <math>n>1</math> to <math>\nu</math> musi być postaci <math>\phi \wedge
-\psi</math>. Rozważmy wartościowanie które wszyskim zmiennym
-przypisuje wartość 1. Ponieważ rozmiary <math>\phi</math> oraz <math>\psi</math>
-są silnie mniejsze od <math>n</math> to z założenia indukcyjnego
-otrzymujemy, że dla naszego wartościowania obie przyjmują
-wartość 1. Wobec tego zgodnie z tabelą
-[[##eq:tabeleInterpretacjiKRZANDOR|Uzupelnic eq:tabeleInterpretacjiKRZANDOR|]] cała formuła <math>\phi \wedge
-\psi</math> też przyjmuje wartość 1. Dowiedliśmy więc, że każda
-formuła o rozmiarze <math>n</math> ma postulowaną własność.
-Wiemy już że każda <math>F_\wedge</math> przyjmuje zawsze wartość 1, jeśli jej zmienne są
+\frac{\phi \Rightarrow \psi, \phi}{\psi}.
-wartościowane na 1. Wobec tego niemożliwe jest zdefiniowanie
-np. spójnika <math>F</math> gdyż definująca go formuła musiałby
-przyjąć wartość 0 na takim wartościowaniu.
-:# Dowód analogiczny do poprzedniego.
+</math></center>
-}}
-{{cwiczenie|[Uzupelnij]||
-Czy funkcje binarne zdefiniowane za pomocą formuł zawierającyh jedynie przemienne spójniki muszą być przemienne?
+Reguła modus ponens posłuży nam do uzupełniania zbioru aksjomatów  o
-{hint}{1}
+ich konsekwencje logiczne, które również uznamy za prawdziwe. Aby
-; Hint .
-: Przyjrzyj się formułom zbudowanym z <math>\Leftrightarrow</math>
-}}
-{{cwiczenie|[Uzupelnij]||
+precyzyjnie zdefiniować zbiór wszystkich konsekwencji logicznych
-(z wykładu prof. P.M.Idziaka)
+aksjomatów definiujemy poniżej pojęcie dowodu.
-Niech <math>F_n</math> oznacza ilość boolowskich funkcji <math>n</math> argumetnowych,
-a <math>P_n</math> ilość boolowskich funkcji <math>n</math> argumentowych, takich że
-przy pomocy każdej z nich da się zdefiniować dowolną funkcję
-boolowską (czyli jeśli <math>\circ</math> jest takim spójnikiem to zbiór
-<math>\{\circ\}</math> jest funkcjonalnie pełny). Udowdnij istenienie
-poniższej granicy i wyznacz jej wartość
-<center><math>
-\lim_{n \rightarrow \infty} \frac{P_n}{F_n}
-</math></center>
-; Solution.
+Ciąg formuł <math>\phi_0, \dots ,\phi_n</math> jest dowodem formuły <math>\psi</math>
-:   }}
-==Postacie normalne==
+wtedy i tylko wtedy, gdy:
-"Literałem" nazywamy formułę która jest zmienną zdaniową lub
-negacją zmiennej zdaniowej.
-Zauważmy, że formuła konstruowana w dowodzie twierdzenia
-[[##thm:AndOrNegFP|Uzupelnic thm:AndOrNegFP|]] jest w pewnej standartowej postaci - formuła
-jest alternatywą formuł które są koniunkcjami literałów.
-Przypomnijmy, że dla <math>p \Rightarrow q</math> zbudujemy formułę
-<center><math>
+# <math>\phi_n</math> jest formułą <math>\psi</math>
-(p \wedge q) \vee (\neg p \wedge q) \vee (\neg p \wedge \neg q).
-</math></center>
-Formuła jest w dyzjunktywnej postaci normalnej (DNF) jeśli jest alternatywą formuł które są koniunkcjami
-literałów. Czyli wtedy gdy jest postaci
-<center><math>
+# dla każdego <math>i\leq n</math> formuła <math>\phi_i</math> jest aksjomatem
-\phi_1\vee \dots \vee \phi_n
+lub istnieją <math>j,k <i</math> takie, że formuła <math>\phi_i</math>
-</math></center>
-oraz każda z formuł <math>\phi_i</math> jest koniunkcją literałów, czyli jest postaci
+jest wynikiem zastosowania reguły modus ponens do
-<center><math>
+formuł <math>\phi_j, \phi_k</math>.
-l_1^i \wedge \dots \wedge l_k^i
-</math></center>
-dla pewnych literałów <math>l_1^i, \dots,l_k^i</math>
-{{twierdzenie|[Uzupelnij]||
+W drugim punkcie powyższej definicji jeśli formuła <math>\phi_i</math> nie jest
-Dla każedej formuły istnieje równoważna formuła w DNF.
+aksjomatem (a więc powstaje przez zastosowanie MP) to formuły
-}}
-{{dowod|[Uzupelnij]||
+<math>\phi_j,\phi_k</math> muszą pasować do przesłanek reguły MP, a więc
-Wynika bezpośrednio z konstrukcji w dowodzie twierdzenia
+<math>\phi_j</math> musi być postaci <math>\phi_k \Rightarrow \phi_i</math> lub <math>\phi_k</math> postaci
-[[##thm:AndOrNegFP|Uzupelnic thm:AndOrNegFP|]].
-}}
-Formuła jest w koniunktywnej postaci normalnej (CNF) jeśli jest koniunkcją formuł które są
+<math>\phi_j \Rightarrow \phi_i</math>.
-alternatywami literałów.
-{{twierdzenie|[Uzupelnij]||
-Dla każdej formuły istnieje równoważna formuła w CNF.
-}}
-{{dowod|[Uzupelnij]||
+Formułę nazywamy "twierdzeniem klasycznego rachunku zdań"
-}}
+jeśli istnieje jej dowód  z aksjomatów klasycznego rachunku
-{{cwiczenie|[Uzupelnij]||
+zdań [[##defn:AksjomatyKRZ|Uzupelnic defn:AksjomatyKRZ|]].
-Jak sprawdzić, czy formuła w CNF jest tautologią?
-; Solution.
-: Niech rozważaną formułą będzie
-<center><math>
+===Przykład===
-\phi_1\wedge \dots \wedge \phi_n
-</math></center>
-Aby była tautologią konieczne jest aby każda z formuł <math>\phi_i</math> była tautologią.
-Ponieważ każda z formuł <math>\phi_i</math> jest alternatywą literałów to jest tautologią jedynie wtedy
-jeśli istnieje taki literał który występuje w <math>\phi_i</math> zarówno pozytywnie (czyli jako zmienna)
-jak i negatywnie (czyli jako zanegowana zmienna).
-}}
-{{cwiczenie|[Uzupelnij]||
+Zastanówmy się na formułą postaci <math>\phi \Rightarrow \phi</math>. Intuicja
-Dla poniższych formuł wypisz ich najkrótsze równoważne formuły w
+podpowiada, że taką formułę powinniśmy uznać za prawdziwą. Nie
-CNF
-# <math>p \Leftrightarrow q</math>
+pasuje ona jednak do żadnego ze schematów aksjomatów
-# <math>p \Rightarrow (q \Rightarrow p)</math>
+[[##defn:AksjomatyKRZ|Uzupelnic defn:AksjomatyKRZ|]]. Formuła ta jest jednak twierdzeniem
+klasycznego rachunku zdań. Poniżej przedstawiamy jej dowód. Aby
-# <math>(p \Rightarrow q) \Rightarrow p</math>
+łatwiej dopasować formuły do schematów aksjomatów użyliśmy
-# <math>(p \vee a \vee b) \wedge (\neg q \vee \neg a) \wedge (r \vee \neg b \vee \neg
+nawiasów kwadratowych dla nawiasów,
-c) \wedge (c \vee p))</math>
-# <math>(p \wedge q) \vee (r \wedge s)</math>
+które pochodzą ze  schematów.
-; Solution.
-:   }}
-===Spełnialność===
-Spośród wszystkich formuł wyróżnimy też zbiór formuł spełnialnych.
+# <math>[\phi \Rightarrow [(q \Rightarrow \phi) \Rightarrow \phi)]\Rightarrow [[\phi \Rightarrow (q \Rightarrow \phi)] \Rightarrow [\phi \Rightarrow
-Formuła jest spełnialna jeśli istenieje takie wartościowanie
+\phi]]</math> formuła ta jest aksjomatem zgodnym ze schematem S
-które wartościuje tą formułę na 1.
-Formuły spełnialne są w ścisłym związku z tautologiami.
-{{twierdzenie|[Uzupelnij]||
-Formuła <math>\phi</math> jest tautologią wtedy i tylko wtedy kiedy formuła
+# <math>\phi \Rightarrow [(q \Rightarrow \phi) \Rightarrow \phi]</math> aksjomat zgodny ze
-<math>\neg \phi</math> nie jest spełnialna.
-}}
-{{dowod|[Uzupelnij]||
+schematem K
-Przypuśćmy, że formuła <math>\phi</math> jest tautologią. Wtedy dla każdego wartościowania <math>v</math> mamy
-<math>v(\phi)=1</math>. Stąd otrzymujemy że dla każdego wartościowania <math>v</math> mamy<math>v(\neg \phi)=0</math>, a więc
-nie istnieje wartościwanie, które spełnia <math>\neg \phi</math>, czyli formuła ta nie jest spełnialna.
-Przypuśćmy, że formuła <math>\neg \phi</math> nie jest spełnialna, czyli nie istnieje wartościowanie <math>v</math>
-takie, że <math>v(\neg \phi)=0</math>. Wynika stąd, że dla każdego wartościowania mamy <math>v(\phi)=1</math>, a więc <math>\phi</math> jest tautologią.
-}}
-{{cwiczenie|[Uzupelnij]||
+# <math>(\phi \Rightarrow (q \Rightarrow \phi)) \Rightarrow (\phi \Rightarrow \phi)</math> z modus ponens z
+formuł 1 i 2.
-Sprawdź spełnialność następujących formuł
-# <math>(\neg p \vee q) \wedge (\neg q \vee \neg r) \wedge (\neg q \vee \neg p)</math>
-# <math>(\neg p \vee q) \wedge (\neg q \vee \neg r) \wedge (\neg q \vee  p)</math>
+# <math>\phi \Rightarrow [q \Rightarrow \phi]</math> aksjomat zgodny ze schematem
-; Solution.
+K
-:   }}
-==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
+# <math>(\phi \Rightarrow \phi)</math> z modus ponens z formuł 3 i 4
-oznaczać przez <math>I_\Rightarrow</math> to zbiór tych formuł które da się dowodnić
-przy pomocy reguły MP z aksjomatów S i K.
-Aksjomaty <math>I_\Rightarrow</math>
-# <math>(\phi \Rightarrow (\psi \Rightarrow \phi))</math> (formuła ta jest nazywana
-aksjomatem K)
-# <math>(\phi \Rightarrow (\nu \Rightarrow \psi) \Rightarrow \left((\phi \Rightarrow \nu) \Rightarrow
-(\phi \Rightarrow \nu) \right)</math> (formuła ta jest nazywana
-aksjomatem S)
-W pełnej wersji logiki intucjonistycznej
+===Podsumowanie===
-pojawiają się również aksjomaty dla spójników <math>\wedge, \vee</math> oraz <math>\neg</math>.
-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ą
-<math>\Rightarrow</math> da się udowodnić przy pomocy aksjomatów
-[[##defn:AksjomatyIntImp|Uzupelnic defn:AksjomatyIntImp|]]. 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|[Uzupelnij]||
-Każde twierdzenie logiki intuicjonistycznej
-jest twierdzeniem klasycznego rachunku zdań.
-}}
-{{dowod|[Uzupelnij]||
+Klasyczny rachunek zdań, czyli zbiór formuł które uznajemy za
-Każdy dowód twierdzenia logiki inuicjonistycznej jest równocześnie dowodem
+prawdziwe zdefiniowaliśmy wyróżniając pewne formuły jako aksjomaty
-twierdzenia klasycznego rachunku zdań.
-}}
-Implikacja w drugą stronę nie zachodzi. Istnieją formuły zbudowane
+[[##defn:AksjomatyKRZ|Uzupelnic defn:AksjomatyKRZ|]] i dorzucając do nich wszystkie formuły,
-jedynie przy pomocy <math>\Rightarrow</math>, które nie należą do <math>I_\Rightarrow</math> pomimo
-że są twierdzeniami klasycznego rachunku zdań. Przykładem takiej formuły jest prawo
-Pierce'a:
-<center><math>
+które dają się z nich wywnioskować przy pomocy reguły modus ponens.
-((p \Rightarrow q) \Rightarrow p ) \Rightarrow p
+Warto zwrócić uwagę, że pomimo tego iż w doborze aksjomatów i reguł
-</math></center>
+wnioskowania kierowaliśmy się intuicyjnym pojęciem implikacji i
-W zadaniu [[##zad:aksjomatyTatuologie|Uzupelnic zad:aksjomatyTatuologie|]] pokazaliśmy, że formuła ta jest w istocie tautologią
+konsekwencji, klasyczny rachunek zdań jest teorią syntaktyczną,
-więc w myśl twierdzenia Posta [[##thm:zupełnośćPost|Uzupelnic thm:zupełnośćPost|]] również
-twierdeniem klasycznego rachunku zdań.
-W poniższych zadaniach wykażemy poniższe twierdzenie
+zbiorem pewnych napisów o których znaczeniu nie musimy nic mówić.
-{{twierdzenie|[Uzupelnij]||
-Prawo Pierce'a nie jest twierdzeniem intuicjonizmu.
-}}
-Zauważmy, że oznacza to również że każdy dowód prawa Pierce'a w
+Warto przyglądnąć się przyjętym aksjomatom i zastanowić się
-logice klasycznej korzysta z aksjomatu 3 [[##defn:AksjomatyKRZ|Uzupelnic defn:AksjomatyKRZ|]], a więc wymaga
-używania spójnika <math>\neg</math>.
-Aby udowodnić twierdzenie [[##thm:PrawoPiercea|Uzupelnic thm:PrawoPiercea|]] zdefiniujemy
+jakim zdaniom odpowiadają i czy rzeczywiście bylibyśmy skłonni
-jeszcze jedną logikę którą nazwiemy <math>I_3</math>. Podobnie do
-[[##defn:matrycaBool|Uzupelnic defn:matrycaBool|]] zdefiniujemy matrycę tym razem 3-elementową.
-Matrycą <math>\mathbb{M}_3</math> będziemy nazywać zbiór trójelementowy
+uznać je za prawdziwe. Pomocne może być interpretowanie formuł
-<math>M_3=\{0,1,2\}</math> w którym 2 jest wyróżnioną wartością prawdy, wraz z
-funkcją odpowiadają za interpretacje <math>\Rightarrow</math> zdefiniowaną następująco
-<center><math>
+postaci <math>\phi \Rightarrow (\nu \Rightarrow \psi)</math> jako ",,jeśli prawdziwe jest
-\begintabular {|c|c c c|}\hline
+<math>\phi</math> i prawdziwe jest <math>\nu</math> to prawdziwe jest <math>\psi</math>"". W
-</math><math> & 0 & 1 & 2\\\hline
-& 2 & 2 & 2\\
-& 0 & 2 & 2\\
-& 0 & 1 & 2\\\hline
-\endtabular  \hspace{1cm}
-</math></center>
-W przypadku rozważanej matrycy <math>\mathbb{M}_3</math> wartościowanie będzie
+kolejnych rozdziałach przekonamy się że taka interpretacja jest
-funkcją przypisującą zmiennym zdaniowym elementy zbioru <math>M_3</math>.
-Podobnie jak dla logiki klasycznej wartościowanie zmiennych
-rozszzerzamy na wartościowanie formuł zgodnie z tabelą
-[[##eq:tabeleInterpretacjiInt3|Uzupelnic eq:tabeleInterpretacjiInt3|]].
-ład
+uzasadniona.
-Dla wartościowania <math>v</math> takiego, że <math>v(p)=2, v(q)=1, v(r)=0</math>
-formuła
-<center><math>
-(p \Rightarrow q) \Rightarrow r
-</math></center>
-przyjmuje wartość 0.
+==Matryca boolowska==
-ład
-Tautologią logiki <math>I_3</math> będziemy nazywać każdą formułę
-implikacyjną,
-która przy każdym wartościowaniu zmiennych w <math>M_3</math> przyjmuje
-wartość 2.
-{{cwiczenie|[Uzupelnij]||
-Udowodnij, że aksjomaty S i K są tautologiami <math>I_3</math>.
+W poprzednim rozdziale zdefiniowaliśmy klasyczny rachunek zdań jako
-; Solution.
+teorię aksjomatyczną. Jeśli pozwolimy sobie na używanie skończonych
-:   }}
-{{cwiczenie|[Uzupelnij]||
+zbiorów i funkcji, możemy równoważnie zdefiniować klasyczny rachunek
-Udowodnij, że jeśli formuła postaci <math>\phi \Rightarrow \psi</math> oraz formuła <math>\phi</math>
+zdań za pomocą tzw. matrycy boolowskiej.
-są tautologiami <math>I_3</math> to formuła <math>\psi</math> jest tautologią <math>I_3</math>.
-; Solution.
-:   }}
-{{cwiczenie|[Uzupelnij]||
-Udowodnij, że każde twierdzenie logiki <math>I_\Rightarrow</math> jest
+Dwuelementową matrycą boolowską nazywamy zbiór dwuelementowy
-tautologią <math>I_3</math>.
-{hint}{1}
+<math>\mathbb{B}=\{0,1\}</math> w którym 1 jest wyróżnioną wartością prawdy, wraz z
-; Hint .
-: Przeprowadź rozumowanie indukcyjne ze względu na długość dowodu.
-Pomocne będą poprzednie zadania.
-; Solution.
+dwoma funkcjami odpowiadającymi za interpretacje spójników
-:   }}
-{{cwiczenie|[Uzupelnij]||
+<math>\Rightarrow</math> oraz <math>\neg</math> zdefiniowanymi następująco
-Sprawdź, czy prawo Pierce'a jest tautologią <math>I_3</math>.
-{hint}{1}
-; Hint .
-: Nie jest.
-; Solution.
-: Dla wartościowania <math>v</math> takiego, że <math>v(p)=1</math> i <math>v(q)=0</math> kolejne
-fomruły przyjmują następujace wartości
-:# <math>v(p\Rightarrow q) =0</math>
+<center><math>
+\begintabular {|c|c c|}\hline
+ & 0 & 1 \\\hline
+& 1 & 1 \\
+& 0 & 1 \\\hline
+\endtabular  \hspace{1cm}
+\begintabular {|c|c|}\hline
+</math>p<math> & </math> p<math> \\\hline
-:# <math>v((p\Rightarrow q)\Rightarrow p) =2</math>
+& 1  \\
-:# <math>v(((p\Rightarrow q)\Rightarrow p)\Rightarrow p) =1</math>
+& 0  \\\hline
-Wobec tego prawo Pierce'a nie jest tautologią <math>I_3</math> gdyż
+\endtabular
-wyróżnioną wartością prawdy <math>I_3</math> w jest 2.
-}}
-Podsumujmy wyniki powyższych zadań. Wskazaliśmy logikę <math>I_3</math>
+</math></center>
-taką, że każda twierdzenie intuicjonizmu jest tautologią <math>I_3</math>.
-Skoro prawo Pierce'a nie jest tautologią <math>I_3</math> to nie jest też
-twierdzeniem <math>I_\Rightarrow</math>.
+Wartościowaniem nazywamy funkcję która przypisuje zmiennym
+zdaniowym elementy zbioru <math>\mathbb{B}</math>. Wartościowanie zmiennych
+można rozszerzyć na wartościowanie formuł interpretując spójniki
+<math>\Rightarrow</math> oraz <math>\neg</math> jako funkcje zgodnie z tabelami
+[[##eq:tabeleInterpretacjiKRZ|Uzupelnic eq:tabeleInterpretacjiKRZ|]].
+ład
+Niech <math>v</math> będzie wartościowaniem zmiennych takim, że <math>v(p)=0,
+v(q)=1, v(r)=0</math>. Wtedy
+* formuła <math>q \Rightarrow p</math> jest wartościowana na
+(będziemy to zapisywać jako <math>v(q \Rightarrow p)=0</math>),
+* formuła <math>r \Rightarrow (q \Rightarrow p)</math> jest wartościowana na 1 (czyli <math>v(r \Rightarrow (q \Rightarrow p))=1</math>)
+* formuła <math>\neg p \Rightarrow r</math> jest wartościowana na  0 (czyli <math>v(\neg p \Rightarrow r)=0</math>)
+ład
+{{cwiczenie|[Uzupelnij]||
+Przy wartościowaniu <math>v</math> z przykładu [[##eg:wartosciowania|Uzupelnic eg:wartosciowania|]] jakie
+wartości przyjmują następujące formuły
+# <math>p \Rightarrow (q \Rightarrow r)</math>
+# <math>p \Rightarrow (p \Rightarrow q)</math>
+# <math>\neg \neg q \Rightarrow p</math>
+# <math>(\neg q\Rightarrow q) \Rightarrow (q \Rightarrow \neg q)</math>
+; Solution.
+:
+:# <math>v(p \Rightarrow (q \Rightarrow r))=1</math>
+:# <math>v(p \Rightarrow (p \Rightarrow q))=1</math>
+:# <math>v(\neg \neg q \Rightarrow p)=0</math>
+:# <math>v((\neg q\Rightarrow q) \Rightarrow (q \Rightarrow \neg q))=0</math>
+}}
+{{cwiczenie|[Uzupelnij]||
+# Podaj przykład wartościowania zmiennych tak aby poniższe formuły
+były wartościowane na 0
+## <math>p \Rightarrow (q \Rightarrow r)</math>
+## <math>(\neg p \Rightarrow q)</math>
+## <math>(p\Rightarrow q) \Rightarrow q</math>
+# Podaj przykład wartościowania zmiennych tak aby poniższe formuły
+były wartościowane na 1
+## <math>\neg (p \Rightarrow q)</math>
+## <math>\neg (\neg p \Rightarrow  \neg q)</math>
+## <math>(\neg q\Rightarrow q) \Rightarrow (q \Rightarrow \neg q)</math>
+; Solution.
+: Wartościowania będziemy oznaczać przez <math>v</math>
+:#
+:## <math>v(p)=1, v(q)=1, v(r)=0</math>
+:## <math>v(p)=0,v(q)=0</math>
+:## <math>v(p)=0,v(q)=0</math>
+:#
+:## <math>v(p)=1,v(q)=0</math>
+:## <math>v(p)=0,v(q)=1)</math>
+:## <math>v(q)=1</math>
+}}
+===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. <math>p \Rightarrow p</math>).
+Takie formuły będziemy nazywać "'tautologiami"'.
+{{cwiczenie|[Uzupelnij]||
+Sprawdź czy poniższe formuły są tautologiami
+# <math>(\phi \Rightarrow (\psi \Rightarrow \phi))</math>
+# <math>(\phi \Rightarrow (\nu \Rightarrow \psi) \Rightarrow \left((\phi \Rightarrow \nu) \Rightarrow
+(\phi \Rightarrow \nu) \right)</math>
+# <math>(\neg \phi \Rightarrow \psi) \Rightarrow (\neg \phi \Rightarrow \neg
+\psi) \Rightarrow \phi</math>
+# <math>((\phi \Rightarrow q) \Rightarrow p) \Rightarrow p</math>
+{hint}{1}
+; Hint .
+: Spróbuj poszukać wartościowań dla których formuła przyjmuje
+wartość 0
+{hint}{1}
+; Hint .
+: Można też sprawdzić wszystkie możliwości wartościowań.
+; Solution.
+:   }}
+Nie przez przypadek pierwsze trzy formuły z poprzedniego zadania
+odpowiadają aksjomatom klasycznego rachunku zdań
+[[##defn:AksjomatyKRZ|Uzupelnic defn:AksjomatyKRZ|]]. Okazuje się że istnieje ścisły związek
+pomiędzy tautologiami a twierdzeniami klasycznego rachunku zdań. Mówi o tym ważny wynik Emil Post.
+{{twierdzenie|[Uzupelnij]||
+{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ń).
+{{cwiczenie|[Uzupelnij]||
+Udowodnij że każde twierdzenie klasycznego rachunku zdań jest tautologią.
+{hint}{1}
+; Hint .
+: Pokazaliśmy już w zadaniu
+[[##zad:aksjomatyTatuologie|Uzupelnic zad:aksjomatyTatuologie|]], że aksjomaty są tautologiami.
+Zacznij od pokazania, że zastosowanie reguły MP  do tautologii daje
+tautologię.
+{hint}{1}
+; Hint .
+: Udowodnij, twierdznie przez indukcję ze względu na długość
+dowodu.
+; Solution.
+:   }}
+===Inne spójniki===
+Do tej pory jedynymi rozważanymi spójnikami była implikacja i
+negacja. W analogiczny sposób do [[##eq:tabeleInterpretacjiKRZ|Uzupelnic eq:tabeleInterpretacjiKRZ|]]
+możemy wprowadzać kolejne spójniki. Często używane spójniki to
+koniunkcja (spójnik "'i"') oznaczana przez <math>\wedge</math> oraz
+alternatywa (spójnik "'lub"') oznaczana przez <math>\vee</math>, które
+będziemy interpretować w następujący sposób:
+<center><math>
+\begintabular {|c|c c|}\hline
+ & 0 & 1 \\\hline
+& 0 & 0 \\
+& 0 & 1 \\\hline
+\endtabular  \hspace{1cm}
+\begintabular {|c|c c|}\hline
+ & 0 & 1 \\\hline
+& 0 & 1 \\
+& 1 & 1 \\\hline
+\endtabular
+</math></center>
+Zgodnie z intuicją koniunkcja <math>\phi \wedge \psi</math> jest wartościowana
+na 1 wtedy i tylko wtedy gdy zarówno <math>\phi</math> jak i <math>\psi</math> są
+wartościowane na 1. Alternatywa <math>\phi \vee \psi</math> jest wartościowana
+na 1 jeśli przynajmniej jedna z formuł <math>\phi, \psi</math> jest
+wartościowana na 1.
+Formuły <math>\phi</math> oraz <math>\psi</math> są "równoważne" (oznaczamy ten fakt
+przez <math>\phi \equiv \psi</math> wtedy i tylko wtedy gdy dla każdego
+wartościowania formuła <math>\phi</math> przyjmuje tą samą wartość co
+formuła <math>\psi</math>.
+{{cwiczenie|[Uzupelnij]||
+Udowodnij, że następujące formuły są równoważne
+# <math>\phi \vee \psi \equiv \neg \phi \Rightarrow \psi </math>
+# <math>\phi \wedge \psi \equiv \neg (\phi \Rightarrow \neg \psi)</math>
+; Solution.
+:
+:# Lewa strona jest fałszywa jedynie gdy <math>\phi</math> oraz
+<math>\psi</math> są wartościowane na 0. Prawa strona jest fałszywa
+wtedy i tylko wtedy kiedy <math>\neg \phi</math> jest wartościowane na
+oraz <math>\psi</math> 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 <math>\phi</math> oraz
+<math>\psi</math> są wartościowane na 0, a więc jest równoważna lewej.
+:# Lewa strona jest prawdziwa jedynie gdy <math>\phi</math> oraz
+<math>\psi</math> są wartościowane na 1. Prawa strona jest prawdziwa
+wtedy i tylko wtedy kiedy <math>\neg (\phi \Rightarrow \neg \psi)</math> jest wartościowane na
+, więc wtedy gdy <math>(\phi \Rightarrow \neg \psi)</math> jest wartościowane na 0. To z kolei
+zdarzyć się może jedynie gdy <math>\phi</math> jest wartościowane na 1
+i <math>\neg \psi</math> na 0, a więc wtedy gdy zarówno <math>\phi</math> jak i
+<math>\psi</math> 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 <math>\wedge</math> lub <math>\vee</math> można zastąpić równoważną formułą w
+której jedynymi spójnikami są <math>\Rightarrow</math> oraz <math>\neg</math>. 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.
+{{cwiczenie|[Uzupelnij]||
+Udowodnij następujące równoważności
+# <math>\neg \neg p \equiv p</math>
+# <math>p\Rightarrow q \equiv \neg p \vee q</math>
+# <math>p \Rightarrow (q \Rightarrow r) \equiv (p \wedge q) \Rightarrow r</math>
+# <math>\neg( p \wedge q) \equiv \neg p \vee \neg q</math>
+# <math>\neg( p \vee q) \equiv \neg p \wedge \neg q</math>
+# <math>p \wedge (q \vee r) \equiv (p \wedge q) \vee (p\wedge r)</math>
+# <math>p \vee (q \wedge r) \equiv (p \vee q) \wedge (p\vee r)</math>
+# <math>(p \Rightarrow q) \Rightarrow (\neg p \Rightarrow \neg q)</math>
+; Solution.
+: Przedstwiamy przykładowe dowody kilku pierwszych równoważności.
+:# Jeśli <math>p</math> jest wartościowane na 1, to zgodnie z tabelą dla negacji [[##eq:tabeleInterpretacjiKRZ|Uzupelnic eq:tabeleInterpretacjiKRZ|]]
+<math>\neg p</math> jest wartościowane na 0 i <math>\neg \neg p</math> jest wartościowane na 1. Jeśli <math>p</math> jest wartościowane
+na 0 to <math>\neg p</math> jest wartościowane na 1 i <math>\neg \neg p</math> jest wartościowane na 0. Formuły przyjmują
+te same wartości dla każdego wartościowania więc są równoważne.
+:# Jedyną możliwością aby lewa strona była fałszywa jest
+aby <math>p</math> było wartościowane na 1, a <math>q</math> na 0. Prawa
+stona jest fałszywa jedynie gdy <math>\neg p</math> oraz <math>q</math> są wartościowane
+na 0. Czyli prawa strona jest fałszywa jedynie
+gdy <math>p</math> jest wartościowane na 1 i <math>q</math> na 0. Formuły są więc
+równoważne.
+:# Analogicznie do poprzedniego punktu łatwo się
+przekonać, że jedynym wartościowaniem które falsyfikuje lewą
+stronę jest takie które wartościuje <math>p</math> i <math>q</math> na 1 oraz <math>r</math>
+na 0. Tą samą własność ma formuła po prawej stronie, więc
+formuły są równoważne.
+:# Przykład rozwiązania przez rozważenie wszystkich
+możliwości
+<center><math>
+\begintabular {|c|c|c|c|c|c|c|}\hline
+</math>p<math> & </math>q<math> & </math>p q<math> & </math> (p q)<math>& </math> p<math> & </math> q<math>&  </math>  p   q<math>\\\hline
+& 0 & 0 & 1 & 1 & 1 & 1\\
+& 1 & 0 & 1 & 1 & 0 & 1\\
+& 0 & 0 & 1 & 0 & 1 & 1\\
+& 1 & 1 & 0 & 0 & 0 & 0\\\hline
+\endtabular  \hspace{1cm}
+</math></center>
+W pierwszych dwóch kolumnach są zapisane wartościowania
+zmiennych <math>p</math> i <math>q</math> 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.
+:# W równoważności z poprzedniego punktu, podstawiąjąc za <math>p</math>
+formułę <math>\neg p</math> oraz za <math>q</math> formułę <math>\neg q</math> otrzymamy
+równoważność
+<center><math>
+\neg( \neg p \wedge \neg q) \equiv \neg \neg p \vee \neg \neg
+q.
+</math></center>
+Stosując dwukrotnie równoważność z pierwszego punktu do prawej strony
+otrzymujemy
+<center><math>
+\neg( \neg p \wedge \neg q) \equiv  p \vee     q.
+</math></center>
+Negując tą równoważność obustronnie otrzymamy
+<center><math>
+\neg \neg( \neg p \wedge \neg q) \equiv\neg(  p \vee     q).
+</math></center>
+Stosując równoważność z pierwszego punktu do lewej strony
+otrzymamy szukaną równoważność.
+}}
+{{cwiczenie|[Uzupelnij]||
+Sprawdź które z następujących formuł są tautologiami
+# <math>( (p \vee r)\wedge( q \vee \neg r) )\Rightarrow (p \vee q)</math>
+# <math>(p \vee q) \Rightarrow ( (p \vee r)\wedge( q \vee \neg r)
+)</math>
+# <math>( (p \wedge r)\vee( q \wedge \neg r) )\Rightarrow (p \wedge
+q)</math>
+# <math>(p \wedge q) \Rightarrow ( (p \wedge r)\vee( q \wedge \neg r)
+)</math>
+; Solution.
+:
+:# Spróbujmy znaleźć wartościowanie które falsyfikuje tą
+formułę. Skoro implikacja ma być fałszywa to formuła <math>(p \vee q)</math> (czyli następnik) musi być
+fałszywa. Tak jest tylko wtedy kiedy zarówno <math>p</math> jak i <math>q</math> są
+fałszywe. Zobaczmy co się wtedy dzieje z poprzednikim implikacji,
+czyli formułą
+<center><math>
+(p \vee r)\wedge( q \vee \neg r).
+</math></center>
+Jeśli teraz ustalimy <math>r</math> na fałsz to <math>(p \vee q)</math> będzie
+fałszywe a jeśli ustalimy <math>r</math> na
+prawdę to <math>( q \vee \neg r)</math> 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ą.
+:# Formuła nie jest tautologią. Wystarczy wartościować <math>p</math> i
+<math>r</math> na prawdę i <math>q</math> na fałsz.
+:# Formuła nie jest tautologią. Wystarczy wartościować <math>p</math> i
+<math>r</math> na prawdę i <math>q</math> na fałsz.
+:# Przykład rozwiązania przez rozważenie wszystkich
+możliwości
+<center><math>
+\begintabular {|c|c|c|c|c|c|c|c|}\hline
+</math>p<math> & </math>q<math> & </math>r<math> &</math>(p  q)<math> &</math> (p  r)<math>&</math> ( q   r)<math>
+&</math> (p  r)( q   r)<math>& </math>(p  q)  ( (p  r)( q   r))<math>\\\hline
+& 0 & 0 & 0 & 0 & 0 & 0 & 1 \\
+& 0 & 1 & 0 & 0 & 0 & 0& 1 \\
+& 1 & 0 & 0 & 0 & 1 & 1& 1 \\
+& 1 & 1 & 0 & 0 & 0 & 0& 1 \\
+& 0 & 0 & 0 & 0 & 0 & 0& 1 \\
+& 0 & 1 & 0 & 1 & 0 & 1& 1 \\
+& 1 & 0 & 1 & 0 & 1 & 1& 1 \\
+& 1 & 1 & 1 & 1 & 0 & 1& 1 \\\hline
+\endtabular  \hspace{1cm}
+</math></center>
+W kolumnie odpowiadającej badanej formule są same 1, więc
+jest ona tautologią.
+}}
+Binarne spójniki logiczne interpretowaliśmy jako funkcje z <math>\mathbb{B}
+\times \mathbb{B} \rightarrow \mathbb{B}</math>. 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.
+W poniższej tabeli przedstawiamy wszystkie spójniki binarne.
+<center><math>
+\begintabular {|c|c|c|c|c|c||c|}\hline
+Numer & </math>p<nowiki>=</nowiki>0<math> &</math> p<nowiki>=</nowiki>0<math> &</math> p<nowiki>=</nowiki>1<math> &</math> p<nowiki>=</nowiki>1<math> && \\
+funkcji& </math>q<nowiki>=</nowiki>0<math> & </math>q<nowiki>=</nowiki>1<math> & </math>q<nowiki>=</nowiki>0<math> & </math>q<nowiki>=</nowiki>1<math> && \\ \hline
+& 0 & 0 & 0 & 0 && </math>F<math>\\
+& 0 & 0 & 0 & 1 && \\
+& 0 & 0 & 1 & 0 && </math>(p  q)<math>\\
+& 0 & 0 & 1 & 1 && </math>p<math> \\
+& 0 & 1 & 0 & 0 && </math> (q p)<math> \\
+& 0 & 1 & 0 & 1 && </math>q<math> \\
+& 0 & 1 & 1 & 0 && </math>XOR<math> \\
+& 0 & 1 & 1 & 1 &&  \\
+& 1 & 0 & 0 & 0 && </math>NOR<math> \\
+& 1 & 0 & 0 & 1 &&  \\
+& 1 & 0 & 1 & 0 && </math> q<math> \\
+& 1 & 0 & 1 & 1 && </math> q  p<math> \\
+& 1 & 1 & 0 & 0 && </math>  p <math>\\
+& 1 & 1 & 0 & 1 && </math> p  q <math>\\
+& 1 & 1 & 1 & 0 && </math> NAND<math> \\
+& 1 & 1 & 1 & 1 && </math>T <math>\\\hline
+\endtabular  \hspace{1cm}
+</math></center>
+Spójnik binarny <math>\circ</math> będziemy nazywać "przemiennym" jeśli zachodzi
+następująca równoważność
+<center><math>
+p \circ q \equiv q \circ p
+</math></center>
+{{cwiczenie|[Uzupelnij]||
+Sprawdź następujące równoważności
+# <math>x NAND y \equiv \neg (x \wedge y)</math>
+# <math>x NOR y \equiv \neg (x \vee y)</math>
+# <math>x XOR y \equiv \neg (x \Leftrightarrow y)</math>
+; Solution.
+:   }}
+{{cwiczenie|[Uzupelnij]||
+Ile spójników binarnych jest przemiennych? Wypisz je wszystkie.
+{hint}{1}
+; Hint .
+: Wygodnie jest reprezentować spójniki binarne w tabeli
+kwadratowej. Na przykład alternatywę
+zdefiniowaliśmy jako
+<center><math>
+\begintabular {|c|c c|}\hline
+ & 0 & 1 \\\hline
+& 0 & 1 \\
+& 1 & 1 \\\hline
+\endtabular .
+</math></center>
+Jaką własność musi posiadać tabela aby spójnik definiowany przez nią był
+przemienny?
+; Solution.
+: Dla przemienności spójnika <math>\circ</math> istotne jest aby <math> 1\circ 0 =  0 \circ 1</math>. Dla pozostałych
+przypadków wartościowań równoważnośc [[##eq:przemienność|Uzupelnic eq:przemienność|]]
+jest zawsze spełniona. Każdy spójnik binarny możemy
+zdefiniować za pomocą tabelki kwadratowej, np. alternatywę
+zdefiniowaliśmy jako
+<center><math>
+\begintabular {|c|c c|}\hline
+ & 0 & 1 \\\hline
+& 0 & 1 \\
+& 1 & 1 \\\hline
+\endtabular .
+</math></center>
+Warunek przemienności oznacza, że wartość w polu o
+współrzędnych <math>(0,1)</math> jest równa wartości w polu o
+współrzędnych <math>(1,0)</math>. Takich tabel jest 8, więc mamy 8
+spójników przemiennych. Nietrudno je teraz odnaleźć w tabeli
+[[##defn:spójniki|Uzupelnic defn:spójniki|]]. Są to
+:# <math>F</math>
+:# <math>\wedge</math>
+:# <math>XOR</math>
+:# <math>\vee</math>
+:# <math>NOR</math>
+:# <math>\Leftrightarrow</math>
+:# <math>NAND</math>
+:# <math>T</math>
+}}
+Spójnik binarny <math>\circ</math> będziemy nazywać "łącznym" jeśli zachodzi
+następująca równoważność
+<center><math>
+p \circ (q \circ r) \equiv     (p \circ q) \circ r.
+</math></center>
+Jeśli spójnik <math>\circ</math> jest łączny to dowolne dwie formuły, które są zbudowane
+jedynie ze spójników <math>\circ</math> 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.
+{{cwiczenie|[Uzupelnij]||
+Udowodnij, że następujące spójniki są łączne
+# <math>\vee</math>
+# <math>\wedge</math>
+# <math>\Leftrightarrow</math>
+# <math>XOR</math>
+; Solution.
+:
+:# Formuła <math>(p \vee q) \vee r</math> jest fałszywa jedynie
+wtedy gdy <math>p</math>,<math>q</math> i <math>r</math> są wartościowane na fałsz. Tak
+samo jest dla formuły <math>p \vee( q \vee r )</math> więc są one
+równoważne.
+:# Formuła <math>(p \wedge q) \wedge r</math> jest prawdziwa jedynie
+wtedy gdy <math>p</math>,<math>q</math> i <math>r</math> są wartościowane na prawdę. Tak
+samo jest dla formuły <math>p \wedge( q \wedge r )</math> więc są one
+równoważne.
+:# Zbadamy równoważność formuł <math>(p \Leftrightarrow q) \Leftrightarrow r</math>
+i <math> p \Leftrightarrow(q \Leftrightarrow r)</math> za pomocą tabeli
+<center><math>
+\begintabular {|c|c|c|c|c|c|c|}\hline
+</math>p<math> &</math> q<math> &</math> r <math>&</math>(p  q)<math> & </math>(p  q)  r<math>& </math>(q  r )<math>&</math> p (q  r)<math>\\\hline
+& 0 & 0 & 1 & 0 & 1 & 0 \\
+& 0 & 1 & 1 & 1 & 0 & 1 \\
+& 1 & 0 & 0 & 1 & 0 & 1 \\
+& 1 & 1 & 0 & 0 & 1 & 0 \\
+& 0 & 0 & 0 & 1 & 1 & 1 \\
+& 0 & 1 & 0 & 0 & 0 & 0 \\
+& 1 & 0 & 1 & 0 & 0 & 0 \\
+& 1 & 1 & 1 & 1 & 1 & 1 \\\hline
+\endtabular  \hspace{1cm}
+</math></center>
+Kolumna 4 i 6 są identyczne więc odpowiadające im
+formuły są równoważne. Spójnik <math>\Leftrightarrow</math> jest więc łączny.
+:# ...
+}}
+Możemy również rozważać spójniki 3 i więcej argumentowe. Spójnik
+<math>k</math>-argumetowy powinien odpowiadać funkcji <math>\mathbb{B}^k \rightarrow \mathbb{B}</math>.
+ład
+W poniższej tabeli przedstawiamy przykład spójnika trójargumentowego
+<center><math>
+\begintabular {|c c c|c||}\hline
+</math>p<math> & </math>q<math> & </math>r<math> &</math>(p, q,r)<math> \\\hline
+& 0 & 0 & 0 \\
+& 0 & 1 & 1 \\
+& 1 & 0 & 1 \\
+& 1 & 1 & 0 \\
+& 0 & 0 & 1 \\
+& 0 & 1 & 0 \\
+& 1 & 0 & 0 \\
+& 1 & 1 & 1 \\\hline
+\endtabular  \hspace{1cm}
+</math></center>
+ład
+{{cwiczenie|[Uzupelnij]||
+Udowodnij, że różnych spójników <math>k</math>-argumentowych jest dokładnie
+<math>2^{2^k}</math>.
+; Solution.
+:   }}
+==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
+<math>\mathbb{B}</math>. Na przykład formuła <math>p \Rightarrow (q\Rightarrow r)</math> wyznacza funkcję
+<math>f_{p \Rightarrow (q\Rightarrow r)}</math> opisaną poniższą tabelą
+<center><math>
+\begintabular {|c|c|c|c|}\hline
+p & q & r & </math>f_{p  (q r)}<math> \\\hline
+& 0 & 0 & 1 \\
+& 0 & 1 & 1 \\
+& 1 & 0 & 1 \\
+& 1 & 1 & 1 \\
+& 0 & 0 & 1 \\
+& 0 & 1 & 1 \\
+& 1 & 0 & 0 \\
+& 1 & 1 & 1 \\\hline
+\endtabular
+</math></center>
+Mówimy, wtedy że formuła <math>\phi</math> definuje funkcję <math>f_{\phi}</math>.
+Skończony zbiór funkcji boolowskich <math>\Gamma</math> 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 <math>\Gamma</math>.
+{{twierdzenie|[Uzupelnij]||
+Zbiór <math>\{\wedge, \vee, \neg\}</math> jest funkcjonalnie pełny.
+}}
+{{dowod|[Uzupelnij]||
+}}
+{{twierdzenie|[Uzupelnij]||
+Zbiory <math>\{\wedge,  \neg\}</math>, <math>\{\vee,  \neg\}</math> są funkcjonalnie pełne.
+}}
+{{dowod|[Uzupelnij]||
+}}
+Udowodnij, że zbiór <math>\{\Rightarrow,  \neg\}</math> jest funkcjonalnie
+pełny.
+{{twierdzenie|[Uzupelnij]||
+Zbiór <math>\{NOR\}</math> jest funkcjonalnie pełny.
+}}
+Udowodnij, że zbiór <math>\{NAND\}</math> jest funkcjonalnie pełny.
+{{cwiczenie|[Uzupelnij]||
+Zdefiniuj alternatywę przy pomocy samej implikacji.
+; Solution.
+: Łatwo sprawdzić że formuła <math>p \Rightarrow (p \Rightarrow q)</math> jest równoważna
+formule <math>p\vee q</math>.
+}}
+Jakie funkcje binarne da się zdefiniować przy pomocy samej
+implikacji?
+{{cwiczenie|[Uzupelnij]||
+Udowodnij, że poniższe zbiory nie są funkcjonalnie pełne
+# <math>\{\wedge\}</math>
+# <math>\{\vee\}</math>
+# <math>\{\Leftrightarrow\}</math>
+# <math>\{XOR\}</math>
+; Solution.
+:
+:# Oznaczmy zbiór formuł w których jedynym spójnikiem jest <math>\wedge</math> przez
+<math>F_\wedge</math>. Udowodnimy, że każda formuła z <math>F_\wedge</math> przyjmuje zawsze wartość 1, jeśli jej zmienne są
+wartościowane na 1. Rozmiarem formuły będziemy nazywać liczbę wystąpień spójnika <math>\wedge</math> w formule.
+Dowód będzie indukcyjny ze względu na
+rozmiar formuły.
+Baza indukcji: Każda formuła z <math>F_\wedge</math> o rozmiarze 0 jest postaci <math>x</math>, gdzie
+<math>x</math> jest zmienną. Wobec tego przy wartościowaniu zmiennych na 1 formuła <math>x</math> też jest
+wartościowana na 1. A więc każda formuła o rozmiarze 0 ma postulowaną własność.
+Krok indukcyjny: Ustalmy dowolne <math>n>0</math> i przyjmijmy, że
+wszystkie formuły o mniejszym rozmiarze mają postulowaną
+własność. Niech <math>\nu</math> będzie dowolną formułą z <math>F_\wedge</math> o rozmiarze
+<math>n</math>. Skoro <math>n>1</math> to <math>\nu</math> musi być postaci <math>\phi \wedge
+\psi</math>. Rozważmy wartościowanie które wszyskim zmiennym
+przypisuje wartość 1. Ponieważ rozmiary <math>\phi</math> oraz <math>\psi</math>
+są silnie mniejsze od <math>n</math> to z założenia indukcyjnego
+otrzymujemy, że dla naszego wartościowania obie przyjmują
+wartość 1. Wobec tego zgodnie z tabelą
+[[##eq:tabeleInterpretacjiKRZANDOR|Uzupelnic eq:tabeleInterpretacjiKRZANDOR|]] cała formuła <math>\phi \wedge
+\psi</math> też przyjmuje wartość 1. Dowiedliśmy więc, że każda
+formuła o rozmiarze <math>n</math> ma postulowaną własność.
+Wiemy już że każda <math>F_\wedge</math> przyjmuje zawsze wartość 1, jeśli jej zmienne są
+wartościowane na 1. Wobec tego niemożliwe jest zdefiniowanie
+np. spójnika <math>F</math> gdyż definująca go formuła musiałby
+przyjąć wartość 0 na takim wartościowaniu.
+:# Dowód analogiczny do poprzedniego.
+}}
+{{cwiczenie|[Uzupelnij]||
+Czy funkcje binarne zdefiniowane za pomocą formuł zawierającyh jedynie przemienne spójniki muszą być przemienne?
+{hint}{1}
+; Hint .
+: Przyjrzyj się formułom zbudowanym z <math>\Leftrightarrow</math>
+}}
+{{cwiczenie|[Uzupelnij]||
+(z wykładu prof. P.M.Idziaka)
+Niech <math>F_n</math> oznacza ilość boolowskich funkcji <math>n</math> argumetnowych,
+a <math>P_n</math> ilość boolowskich funkcji <math>n</math> argumentowych, takich że
+przy pomocy każdej z nich da się zdefiniować dowolną funkcję
+boolowską (czyli jeśli <math>\circ</math> jest takim spójnikiem to zbiór
+<math>\{\circ\}</math> jest funkcjonalnie pełny). Udowdnij istenienie
+poniższej granicy i wyznacz jej wartość
+<center><math>
+\lim_{n \rightarrow \infty} \frac{P_n}{F_n}
+</math></center>
+; Solution.
+:   }}
+==Postacie normalne==
+"Literałem" nazywamy formułę która jest zmienną zdaniową lub
+negacją zmiennej zdaniowej.
+Zauważmy, że formuła konstruowana w dowodzie twierdzenia
+[[##thm:AndOrNegFP|Uzupelnic thm:AndOrNegFP|]] jest w pewnej standartowej postaci - formuła
+jest alternatywą formuł które są koniunkcjami literałów.
+Przypomnijmy, że dla <math>p \Rightarrow q</math> zbudujemy formułę
+<center><math>
+(p \wedge q) \vee (\neg p \wedge q) \vee (\neg p \wedge \neg q).
+</math></center>
+Formuła jest w dyzjunktywnej postaci normalnej (DNF) jeśli jest alternatywą formuł które są koniunkcjami
+literałów. Czyli wtedy gdy jest postaci
+<center><math>
+\phi_1\vee \dots \vee \phi_n
+</math></center>
+oraz każda z formuł <math>\phi_i</math> jest koniunkcją literałów, czyli jest postaci
+<center><math>
+l_1^i \wedge \dots \wedge l_k^i
+</math></center>
+dla pewnych literałów <math>l_1^i, \dots,l_k^i</math>
+{{twierdzenie|[Uzupelnij]||
+Dla każedej formuły istnieje równoważna formuła w DNF.
+}}
+{{dowod|[Uzupelnij]||
+Wynika bezpośrednio z konstrukcji w dowodzie twierdzenia
+[[##thm:AndOrNegFP|Uzupelnic thm:AndOrNegFP|]].
+}}
+Formuła jest w koniunktywnej postaci normalnej (CNF) jeśli jest koniunkcją formuł które są
+alternatywami literałów.
+{{twierdzenie|[Uzupelnij]||
+Dla każdej formuły istnieje równoważna formuła w CNF.
+}}
+{{dowod|[Uzupelnij]||
+}}
+{{cwiczenie|[Uzupelnij]||
+Jak sprawdzić, czy formuła w CNF jest tautologią?
+; Solution.
+: Niech rozważaną formułą będzie
+<center><math>
+\phi_1\wedge \dots \wedge \phi_n
+</math></center>
+Aby była tautologią konieczne jest aby każda z formuł <math>\phi_i</math> była tautologią.
+Ponieważ każda z formuł <math>\phi_i</math> jest alternatywą literałów to jest tautologią jedynie wtedy
+jeśli istnieje taki literał który występuje w <math>\phi_i</math> zarówno pozytywnie (czyli jako zmienna)
+jak i negatywnie (czyli jako zanegowana zmienna).
+}}
+{{cwiczenie|[Uzupelnij]||
+Dla poniższych formuł wypisz ich najkrótsze równoważne formuły w
+CNF
+# <math>p \Leftrightarrow q</math>
+# <math>p \Rightarrow (q \Rightarrow p)</math>
+# <math>(p \Rightarrow q) \Rightarrow p</math>
+# <math>(p \vee a \vee b) \wedge (\neg q \vee \neg a) \wedge (r \vee \neg b \vee \neg
+c) \wedge (c \vee p))</math>
+# <math>(p \wedge q) \vee (r \wedge s)</math>
+; Solution.
+:   }}
+===Spełnialność===
+Spośród wszystkich formuł wyróżnimy też zbiór formuł spełnialnych.
+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|[Uzupelnij]||
+Formuła <math>\phi</math> jest tautologią wtedy i tylko wtedy kiedy formuła
+<math>\neg \phi</math> nie jest spełnialna.
+}}
+{{dowod|[Uzupelnij]||
+Przypuśćmy, że formuła <math>\phi</math> jest tautologią. Wtedy dla każdego wartościowania <math>v</math> mamy
+<math>v(\phi)=1</math>. Stąd otrzymujemy że dla każdego wartościowania <math>v</math> mamy<math>v(\neg \phi)=0</math>, a więc
+nie istnieje wartościwanie, które spełnia <math>\neg \phi</math>, czyli formuła ta nie jest spełnialna.
+Przypuśćmy, że formuła <math>\neg \phi</math> nie jest spełnialna, czyli nie istnieje wartościowanie <math>v</math>
+takie, że <math>v(\neg \phi)=0</math>. Wynika stąd, że dla każdego wartościowania mamy <math>v(\phi)=1</math>, a więc <math>\phi</math> jest tautologią.
+}}
+{{cwiczenie|[Uzupelnij]||
+Sprawdź spełnialność następujących formuł
+# <math>(\neg p \vee q) \wedge (\neg q \vee \neg r) \wedge (\neg q \vee \neg p)</math>
+# <math>(\neg p \vee q) \wedge (\neg q \vee \neg r) \wedge (\neg q \vee  p)</math>
+; Solution.
+:   }}
+==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 <math>I_\Rightarrow</math> to zbiór tych formuł które da się dowodnić
+przy pomocy reguły MP z aksjomatów S i K.
+Aksjomaty <math>I_\Rightarrow</math>
+# <math>(\phi \Rightarrow (\psi \Rightarrow \phi))</math> (formuła ta jest nazywana
+aksjomatem K)
+# <math>(\phi \Rightarrow (\nu \Rightarrow \psi) \Rightarrow \left((\phi \Rightarrow \nu) \Rightarrow
+(\phi \Rightarrow \nu) \right)</math> (formuła ta jest nazywana
+aksjomatem S)
+W pełnej wersji logiki intucjonistycznej
+pojawiają się również aksjomaty dla spójników <math>\wedge, \vee</math> oraz <math>\neg</math>.
+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ą
+<math>\Rightarrow</math> da się udowodnić przy pomocy aksjomatów
+[[##defn:AksjomatyIntImp|Uzupelnic defn:AksjomatyIntImp|]]. 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|[Uzupelnij]||
+Każde twierdzenie logiki intuicjonistycznej
+jest twierdzeniem klasycznego rachunku zdań.
+}}
+{{dowod|[Uzupelnij]||
+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 <math>\Rightarrow</math>, które nie należą do <math>I_\Rightarrow</math> pomimo
+że są twierdzeniami klasycznego rachunku zdań. Przykładem takiej formuły jest prawo
+Pierce'a:
+<center><math>
+((p \Rightarrow q) \Rightarrow p ) \Rightarrow p
+</math></center>
+W zadaniu [[##zad:aksjomatyTatuologie|Uzupelnic zad:aksjomatyTatuologie|]] pokazaliśmy, że formuła ta jest w istocie tautologią
+więc w myśl twierdzenia Posta [[##thm:zupełnośćPost|Uzupelnic thm:zupełnośćPost|]] również
+twierdeniem klasycznego rachunku zdań.
+W poniższych zadaniach wykażemy poniższe twierdzenie
+{{twierdzenie|[Uzupelnij]||
+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 [[##defn:AksjomatyKRZ|Uzupelnic defn:AksjomatyKRZ|]], a więc wymaga
+używania spójnika <math>\neg</math>.
+Aby udowodnić twierdzenie [[##thm:PrawoPiercea|Uzupelnic thm:PrawoPiercea|]] zdefiniujemy
+jeszcze jedną logikę którą nazwiemy <math>I_3</math>. Podobnie do
+[[##defn:matrycaBool|Uzupelnic defn:matrycaBool|]] zdefiniujemy matrycę tym razem 3-elementową.
+Matrycą <math>\mathbb{M}_3</math> będziemy nazywać zbiór trójelementowy
+<math>M_3=\{0,1,2\}</math> w którym 2 jest wyróżnioną wartością prawdy, wraz z
+funkcją odpowiadają za interpretacje <math>\Rightarrow</math> zdefiniowaną następująco
+<center><math>
+\begintabular {|c|c c c|}\hline
+ & 0 & 1 & 2\\\hline
+& 2 & 2 & 2\\
+& 0 & 2 & 2\\
+& 0 & 1 & 2\\\hline
+\endtabular  \hspace{1cm}
+</math></center>
+W przypadku rozważanej matrycy <math>\mathbb{M}_3</math> wartościowanie będzie
+funkcją przypisującą zmiennym zdaniowym elementy zbioru <math>M_3</math>.
+Podobnie jak dla logiki klasycznej wartościowanie zmiennych
+rozszzerzamy na wartościowanie formuł zgodnie z tabelą
+[[##eq:tabeleInterpretacjiInt3|Uzupelnic eq:tabeleInterpretacjiInt3|]].
+ład
+Dla wartościowania <math>v</math> takiego, że <math>v(p)=2, v(q)=1, v(r)=0</math>
+formuła
+<center><math>
+(p \Rightarrow q) \Rightarrow r
+</math></center>
+przyjmuje wartość 0.
+ład
+Tautologią logiki <math>I_3</math> będziemy nazywać każdą formułę
+implikacyjną,
+która przy każdym wartościowaniu zmiennych w <math>M_3</math> przyjmuje
+wartość 2.
+{{cwiczenie|[Uzupelnij]||
+Udowodnij, że aksjomaty S i K są tautologiami <math>I_3</math>.
+; Solution.
+:   }}
+{{cwiczenie|[Uzupelnij]||
+Udowodnij, że jeśli formuła postaci <math>\phi \Rightarrow \psi</math> oraz formuła <math>\phi</math>
+są tautologiami <math>I_3</math> to formuła <math>\psi</math> jest tautologią <math>I_3</math>.
+; Solution.
+:   }}
+{{cwiczenie|[Uzupelnij]||
+Udowodnij, że każde twierdzenie logiki <math>I_\Rightarrow</math> jest
+tautologią <math>I_3</math>.
+{hint}{1}
+; Hint .
+: Przeprowadź rozumowanie indukcyjne ze względu na długość dowodu.
+Pomocne będą poprzednie zadania.
+; Solution.
+:   }}
+{{cwiczenie|[Uzupelnij]||
+Sprawdź, czy prawo Pierce'a jest tautologią <math>I_3</math>.
+{hint}{1}
+; Hint .
+: Nie jest.
+; Solution.
+: Dla wartościowania <math>v</math> takiego, że <math>v(p)=1</math> i <math>v(q)=0</math> kolejne
+fomruły przyjmują następujace wartości
+:# <math>v(p\Rightarrow q) =0</math>
+:# <math>v((p\Rightarrow q)\Rightarrow p) =2</math>
+:# <math>v(((p\Rightarrow q)\Rightarrow p)\Rightarrow p) =1</math>
+Wobec tego prawo Pierce'a nie jest tautologią <math>I_3</math> gdyż
+wyróżnioną wartością prawdy <math>I_3</math> w jest 2.
+}}
+Podsumujmy wyniki powyższych zadań. Wskazaliśmy logikę <math>I_3</math>
+taką, że każda twierdzenie intuicjonizmu jest tautologią <math>I_3</math>.
+Skoro prawo Pierce'a nie jest tautologią <math>I_3</math> to nie jest też
+twierdzeniem <math>I_\Rightarrow</math>.
+UWAGA! W dalszej części będziemy się posługiwać wyłącznie
-UWAGA! W dalszej części będziemy się posługiwać wyłącznie
 "'logiką klasyczną"'.
 {amsplain}