Logika dla informatyków/Rachunek zdań

Wnioskowanie o prawdziwości rozmaitych stwierdzeń jest powszednimzajęciem matematyków i nie tylko matematyków. Dlategofilozofowie i matematycy od dawna zajmowali się systematyzacją metodwnioskowania i kryteriów ich poprawności. Oczywiście ostatecznymkryterium poprawności rozumowania pozostaje zawsze zdrowy rozsądek iprzekonanie o słuszności wywodu. Logika, która narodziła się jakonauka o rozumowaniu, jest jednak ważnym i potrzebnym narzędziem, któreto przekonanie\boldsymbol{s}}\def\blank{\hbox{\sf Błatwia.

Szczególną rolę wśród rozmaitych działów logiki zajmuje logikamatematyczna, poświęcona opisowi i analizie języka matematyki orazpoprawności wnioskowań matematycznych. Jest to dyscyplina w pewnymsensie paradoksalna: będąc sama częścią matematyki, traktujematematykę jako swój przedmiot zainteresowania. Dla\boldsymbol{s}}\def\blank{\hbox{\sf Bniknięcia,,błędnego koła musimy więc tutaj zauważyć, że logika formalna nieopisuje rzeczywistych wywodów matematyka, ale ich\boldsymbol{s}}\def\blank{\hbox{\sf Bproszczonemodele, które bez zastrzeżeń można\boldsymbol{s}}\def\blank{\hbox{\sf Bważać za zwykłe obiektymatematyczne. Mimo tego ograniczenia, logika matematyczna dostarczaniezwykle ważnych wniosków o charakterze filozoficznymi metamatematycznym.

Logika formalna była kiedyś\Delta\vdashzoteryczną nauką z pogranicza filozofii imatematyki, potem stała się pełnoprawnym działem czystej matematyki.Jeszcze później, wraz z narodzinami informatyki, zaczęła być corazbardziej postrzegana jako dziedzina matematyki stosowanej, a zwłaszcza podstaw informatyki.

Logika matematyczna stosowana jest dziś szeroko w informatyce. Semantyka i weryfikacja programów, teoria złożoności i teoria automatów,programowanie funkcyjne i programowanie w logice --- to tylko niektórez działów informatyki, w których metody logiki formalnej stały się standardowym narzędziem zarówno badacza jak i praktyka.

Rachunek zdań

Jak powiedzieliśmy wyżej, logika matematyczna zajmuje się badaniemrozmaitych systemów formalnych, modelujących rzeczywiste sposobywnioskowania matematycznego. Do najprostszych takich systemównależą różne warianty logiki zdaniowej\/ zwanej teżrachunkiem zdań\/. Język rachunku zdań jest bardzo prosty. Nie ma w nim wyrażeń stwierdzających jakiś stan rzeczy, zajście jakichś faktów, czy też wyrażeń orzekających o własnościach obiektów.Przedmiotem naszego zainteresowania są tu tylko możliwe zależności pomiędzy stwierdzeniami \begin{eqnarray*}zdaniami orzekającymi\end{eqnarray*}, oraz tow jaki sposób prawdziwość zdań złożonych zależy od prawdziwości ichskładowych. Sens samych składowych pozostaje tu całkowicie dowolny i nieistotny. Dlatego w rachunku zdań odpowiadają im po prostu zmienne zdaniowe\/. Zdania złożone budujemy ze zmiennych za pomocąspójników logicznych\/ takich jak alternatywa\/ $\vee$,koniunkcja\/ $\wedge$, negacja $\mathrm{\neg }$, czy \rightarrowlikacja\/ $\to$. Wygodne są też stałe logiczne\/ $\mathrm{\perp }$ \begin{eqnarray*}fałsz\end{eqnarray*} i $\mathrm{\top }$ \begin{eqnarray*}prawda\end{eqnarray*},które można\boldsymbol{s}}\def\blank{\hbox{\sf Bważać za zeroargumentowe spójniki logiczne.Dlatego nasza pierwsza definicja jest taka:

Definicja

Ustalamy pewien przeliczalnie nieskończony zbiór Parser nie mógł rozpoznać (błąd składni): {\displaystyle \\mbox{\small ZZ}} symboli, które będziemy nazywać zmiennymi zdaniowymi\/ i zwykle oznaczać literami $p$, $q$, itp. Pojęcie formuły zdaniowej\/ definiujemy przez indukcję:

• Zmienne zdaniowe oraz $\mathrm{\perp }$ i $\mathrm{\top }$ są formułami zdaniowymi;
• Jeśli napis Parser nie mógł rozpoznać (nieznana funkcja „\var”): {\displaystyle \var\varphi} jest formułą zdaniową, to także napis Parser nie mógł rozpoznać (nieznana funkcja „\var”): {\displaystyle \neg\var\varphi} jest formułą zdaniową;
• Jeśli napisy Parser nie mógł rozpoznać (nieznana funkcja „\var”): {\displaystyle \var\varphi} i $\psi$ są formułami zdaniowymi to napisy Parser nie mógł rozpoznać (błąd składni): {\displaystyle \begin{eqnarray*}\var\varphi\to\psi\end{eqnarray*}} , Parser nie mógł rozpoznać (błąd składni): {\displaystyle \begin{eqnarray*}\var\varphi\vee\psi\end{eqnarray*}} i Parser nie mógł rozpoznać (błąd składni): {\displaystyle \begin{eqnarray*}\var\varphi\wedge\psi\end{eqnarray*}} też są formułami zdaniowymi.

Inaczej mówiąc, formuły zdaniowe to\Delta\vdashlementy najmniejszego zbiorunapisów Parser nie mógł rozpoznać (błąd składni): {\displaystyle \\F_{{\sc Z}}} , zawierającego Parser nie mógł rozpoznać (błąd składni): {\displaystyle \\mbox{\small ZZ}\cup\{\bot,\top\}} i takiego, że dla dowolnych </math>\var\varphi,\psi\in\\F_Szablon:\sc ZParser nie mógł rozpoznać (błąd składni): {\displaystyle także } \neg\var\varphi,\begin{eqnarray*}\var\varphi\to\psi\end{eqnarray*},\begin{eqnarray*}\var\varphi\vee\psi\end{eqnarray*}, \begin{eqnarray*}\var\varphi\wedge\psi\end{eqnarray*}</math> należą do Parser nie mógł rozpoznać (błąd składni): {\displaystyle \\F_{{\sc Z}}} .

Konwencje notacyjne: Dla pełnej jednoznaczności składni nasze formuły są w pełni nawiasowane. W praktyce wiele nawiasów pomijamy, stosując przy tym następujące priorytety:

1. Negacja;

1. Koniunkcja i alternatywa;

1. Implikacja.

Zatem na przykład wyrażenie Parser nie mógł rozpoznać (nieznana funkcja „\var”): {\displaystyle \neg\var\varphi\vee\psi\to\vartheta} oznacza Parser nie mógł rozpoznać (błąd składni): {\displaystyle \begin{eqnarray*}\begin{eqnarray*}\neg\var\varphi\vee\psi\end{eqnarray*}\to\vartheta\end{eqnarray*}} , ale napis Parser nie mógł rozpoznać (nieznana funkcja „\var”): {\displaystyle \var\varphi\vee\psi\wedge \vartheta} jest niepoprawny.

formuły jest wartość logiczna tj. ,,prawda \begin{eqnarray*}1\end{eqnarray*} lub ,,fałsz \begin{eqnarray*}0\end{eqnarray*}.Aby określić wartość formuły zdaniowej trzeba jednak najpierw\boldsymbol{s}}\def\blank{\hbox{\sf Bstalić wartości zmiennych.

Definicja

Przez wartościowanie zdaniowe\/ rozumiemy dowolną funkcję $\varrho$,która zmiennym zdaniowym przypisuje wartości logiczne 0 lub 1. Wartość formuły\/ zdaniowej Parser nie mógł rozpoznać (nieznana funkcja „\var”): {\displaystyle \var\varphi} przy wartościowaniu $\varrho$ oznaczamy przez Parser nie mógł rozpoznać (nieznana funkcja „\wfz”): {\displaystyle \wfz\var\varphi\varrho} i określamyprzez indukcję:

• Parser nie mógł rozpoznać (nieznana funkcja „\wfz”): {\displaystyle \wfz\bot\varrho=0} oraz Parser nie mógł rozpoznać (nieznana funkcja „\wfz”): {\displaystyle \wfz\top\varrho=1} ;
• Parser nie mógł rozpoznać (nieznana funkcja „\wf”): {\displaystyle \wf\prooftree p \justifies \varrho \using \textrm{\begin{eqnarray*}W\end{eqnarray*}}\endprooftree=\varrho\begin{eqnarray*}p\end{eqnarray*}} , gdy $p$ jest symbolem zdaniowym;
• Parser nie mógł rozpoznać (nieznana funkcja „\wfz”): {\displaystyle \wfz{\neg\var\varphi}\varrho=1-\wfz{\var\varphi}\varrho} ;
• </math>\wf\prooftree \var\varphi\vee\psi \justifies \varrho \using \textrm{\begin{eqnarray*}W\end{eqnarray*

\endprooftree=\max\{\wf\prooftree \var\varphi \justifies \varrho \using \textrm{\begin{eqnarray*}W\end{eqnarray*}}\endprooftree,\wf\prooftree \psi \justifies \varrho}\ \using \textrm{\begin{eqnarray*}W\end{eqnarray*}}\endprooftree</math>;

</math>\wf\prooftree \var\varphi\wedge\psi \justifies \varrho \using \textrm{\begin{eqnarray*}W\end{eqnarray*}}\endprooftree=\min\{\wf\prooftree \var\varphi \justifies \varrho \using \textrm{\begin{eqnarray*}W\end{eqnarray*}}\endprooftree,\wf\prooftree \psi \justifies \varrho}\ \using \textrm{\begin{eqnarray*}W\end{eqnarray*}}\endprooftree</math>;

Parser nie mógł rozpoznać (nieznana funkcja „\wf”): {\displaystyle \wf\prooftree \var\varphi\to\psi \justifies \varrho \using \textrm{\begin{eqnarray*}W\end{eqnarray*}}\endprooftree=0} , gdy Parser nie mógł rozpoznać (nieznana funkcja „\wfz”): {\displaystyle \wfz\var\varphi\varrho=1} i Parser nie mógł rozpoznać (nieznana funkcja „\wfz”): {\displaystyle \wfz\psi\varrho=0} ;

Parser nie mógł rozpoznać (nieznana funkcja „\wfz”): {\displaystyle \wfz{\var\varphi\to\psi}\varrho=1} , \wpp.

}}

Łatwo można zauważyć, że </math>\wf\prooftree \var\varphi\to\psi \justifies \varrho \using \textrm{\begin{eqnarray*}W\end{eqnarray*}}\endprooftree = \max\{\wfz\psi\varrho,1-\wfz\var\varphi\varrho\}</math>, czyli Parser nie mógł rozpoznać (nieznana funkcja „\wfz”): {\displaystyle \wfz{\var\varphi\to\psi}\varrho=\wfz{\neg\var\varphi\vee\psi}\varrho} , dladowolnego $\varrho$. A zatem zamiast formuły Parser nie mógł rozpoznać (nieznana funkcja „\var”): {\displaystyle \var\varphi\to\psi} moglibyśmy z równym powodzeniem\boldsymbol{s}}\def\blank{\hbox{\sf Bżywać wyrażenia Parser nie mógł rozpoznać (nieznana funkcja „\var”): {\displaystyle \neg\var\varphi\vee\psi} , lub też odwrotnie: zamiast alternatywy Parser nie mógł rozpoznać (nieznana funkcja „\var”): {\displaystyle \var\varphi\vee\psi} pisać Parser nie mógł rozpoznać (nieznana funkcja „\var”): {\displaystyle \neg\var\varphi\to\psi} .Nasz wybór spójników nie jest więc ,,najoszczędniejszy, w istocie w logice klasycznej wystarczy\boldsymbol{s}}\def\blank{\hbox{\sf Bżywać np. \rightarrowlikacji i fałszu \begin{eqnarray*}Ćwiczenie #udacczleka\end{eqnarray*}. Czasem i my będziemy korzystać z tego wygodnego\boldsymbol{s}}\def\blank{\hbox{\sf Bproszczenia, przyjmując, że ,,oficjalnymi spójnikami są tylko \rightarrowlikacja i fałsz, a pozostałe to skróty notacyjne, tj. że napisy\begin{tabbing}\hspace{3.0cm}\quad \= Parser nie mógł rozpoznać (nieznana funkcja „\var”): {\displaystyle \neg\var\varphi} \qquad \= oznaczają odpowiednio \quad\=Parser nie mógł rozpoznać (nieznana funkcja „\var”): {\displaystyle \var\varphi\to\bot} ;\\\hspace{2.0cm}\ \ \ \> $\mathrm{\top }$\> \ \ \ \ \> $\mathrm{\neg }\mathrm{\perp }$;\\ \hspace{2.0cm}\ \ \ \> Parser nie mógł rozpoznać (nieznana funkcja „\var”): {\displaystyle \var\varphi\vee\psi} \> \ \ \ \ \> Parser nie mógł rozpoznać (nieznana funkcja „\var”): {\displaystyle \neg\var\varphi\to\psi} ;\\ \hspace{2.0cm}\ \ \ \> Parser nie mógł rozpoznać (nieznana funkcja „\var”): {\displaystyle \var\varphi\wedge\psi} \> \ \ \ \ \> Parser nie mógł rozpoznać (błąd składni): {\displaystyle \neg\begin{eqnarray*}\var\varphi\to\neg\psi\end{eqnarray*}} .\end{tabbing}Będziemy też czasem pisać Parser nie mógł rozpoznać (nieznana funkcja „\var”): {\displaystyle \var\varphi\\leftrightarrow\psi} zamiast Parser nie mógł rozpoznać (błąd składni): {\displaystyle \begin{eqnarray*}\var\varphi\to\psi\end{eqnarray*}\wedge\begin{eqnarray*}\psi\to\var\varphi\end{eqnarray*}} . Zauważmy, że Parser nie mógł rozpoznać (nieznana funkcja „\wfz”): {\displaystyle \wfz{\var\varphi\\leftrightarrow\psi}\varrho=1} \wtw, gdy Parser nie mógł rozpoznać (nieznana funkcja „\wfz”): {\displaystyle \wfz{\var\varphi\to\psi}\varrho=\wfz{\psi\to\var\varphi}\varrho} .

Często stosowanym skrótem jest notacja Parser nie mógł rozpoznać (nieznana funkcja „\var”): {\displaystyle \bigvee_{i\in I}\var\varphi_i} oznaczająca alternatywę wszystkich formuł Parser nie mógł rozpoznać (nieznana funkcja „\var”): {\displaystyle \var\varphi_i} , gdzie $i$przebiega skończony zbiór $I$. Analogicznie stosuje sięzapis Parser nie mógł rozpoznać (nieznana funkcja „\var”): {\displaystyle \bigwedge_{i\in I}\var\varphi_i} .

Notacja i terminologia: Jeśli Parser nie mógł rozpoznać (nieznana funkcja „\kl”): {\displaystyle \kl\var\varphi_\varrho=1} to piszemy też Parser nie mógł rozpoznać (nieznana funkcja „\var”): {\displaystyle \varrho\models\var\varphi} lub Parser nie mógł rozpoznać (nieznana funkcja „\var”): {\displaystyle \models\var\varphi[\varrho]} i mówimy, że Parser nie mógł rozpoznać (nieznana funkcja „\var”): {\displaystyle \var\varphi} jest spełniona\/ przez wartościowanie $\varrho$. Jeśli $\mathrm{\Gamma }$ jest zbiorem formuł zdaniowych, oraz $\varrho \models \gamma$ dla wszystkich $\gamma \in \mathrm{\Gamma }$, to piszemy $\varrho \models \mathrm{\Gamma }$.Wreszcie Parser nie mógł rozpoznać (nieznana funkcja „\var”): {\displaystyle \Gamma\models\var\varphi} oznacza, że każde wartościowanie spełniające wszystkie formuły z $\mathrm{\Gamma }$ spełnia także formułę Parser nie mógł rozpoznać (nieznana funkcja „\var”): {\displaystyle \var\varphi} . Mówimy wtedy, że Parser nie mógł rozpoznać (nieznana funkcja „\var”): {\displaystyle \var\varphi} jest semantyczną konsekwencją\/ zbioru $\mathrm{\Gamma }$. Jeśli $\mathrm{\Gamma }=\mathrm{\varnothing }$ to zamiast Parser nie mógł rozpoznać (nieznana funkcja „\var”): {\displaystyle \Gamma\models\var\varphi} piszemy po prostu Parser nie mógł rozpoznać (nieznana funkcja „\var”): {\displaystyle \models\var\varphi} . Oznacza to, że formuła Parser nie mógł rozpoznać (nieznana funkcja „\var”): {\displaystyle \var\varphi} jest spełnionaprzez każde wartościowanie. Na koniec powiedzmy jeszcze, że formułami równoważnymi\/ nazywamy takie formuły Parser nie mógł rozpoznać (nieznana funkcja „\var”): {\displaystyle \var\varphi} i $\psi$, których wartości przy każdym wartościowaniu są takiesame \begin{eqnarray*}tj. takie, że równoważność Parser nie mógł rozpoznać (nieznana funkcja „\var”): {\displaystyle \var\varphi\\leftrightarrow\psi} jest tautologią ---patrz niżej\end{eqnarray*}.

Definicja

Formuła Parser nie mógł rozpoznać (nieznana funkcja „\var”): {\displaystyle \var\varphi} jest spełnialna\/, gdy Parser nie mógł rozpoznać (nieznana funkcja „\var”): {\displaystyle \varrho\models\var\varphi} zachodzi dla pewnego wartościowania $\rho$. Jeśli zaś Parser nie mógł rozpoznać (nieznana funkcja „\var”): {\displaystyle \models\var\varphi} to mówimy, że Parser nie mógł rozpoznać (nieznana funkcja „\var”): {\displaystyle \var\varphi} jesttautologią\/ \begin{eqnarray*}klasycznego\end{eqnarray*} rachunku zdań. Oczywiście Parser nie mógł rozpoznać (nieznana funkcja „\var”): {\displaystyle \neg\var\varphi} jest spełnialna \wtw, gdy Parser nie mógł rozpoznać (nieznana funkcja „\var”): {\displaystyle \var\varphi} nie jest tautologią.

Niech $S$ będzie funkcją przypisujacą symbolom zdaniowym pewne formuły.Jeśli Parser nie mógł rozpoznać (nieznana funkcja „\var”): {\displaystyle \var\varphi} jest formułą zdaniową, to przez Parser nie mógł rozpoznać (błąd składni): {\displaystyle S\begin{eqnarray*}\var\varphi\end{eqnarray*}} oznaczymy formu\lę otrzymaną z Parser nie mógł rozpoznać (nieznana funkcja „\var”): {\displaystyle \var\varphi} przez jednoczesną zamianę każdego wystąpienia zmiennej zdaniowej $p$ na formu\lę Parser nie mógł rozpoznać (błąd składni): {\displaystyle S\begin{eqnarray*}p\end{eqnarray*}} . Mówimy, że formuła Parser nie mógł rozpoznać (błąd składni): {\displaystyle S\begin{eqnarray*}\var\varphi\end{eqnarray*}} jest instancją\/ schematu zdaniowego Parser nie mógł rozpoznać (nieznana funkcja „\var”): {\displaystyle \var\varphi} . Używamy oznaczenia Parser nie mógł rozpoznać (błąd składni): {\displaystyle S\begin{eqnarray*}\Gamma\end{eqnarray*} = \{S\begin{eqnarray*}\psi\end{eqnarray*}\ |\ \psi\in\Gamma\}} .

Fakt

Jeżeli\/ $\mathrm{\Gamma }$ jest zbiorem formu\l\ rachunku zdań i Parser nie mógł rozpoznać (nieznana funkcja „\var”): {\displaystyle \Gamma\models\var\varphi} , to także Parser nie mógł rozpoznać (błąd składni): {\displaystyle S\begin{eqnarray*}\Gamma\end{eqnarray*}\models S\begin{eqnarray*}\var\varphi\end{eqnarray*}} . W szczególności, jeśli Parser nie mógł rozpoznać (nieznana funkcja „\var”): {\displaystyle \var\varphi} jest tautologią to Parser nie mógł rozpoznać (błąd składni): {\displaystyle S\begin{eqnarray*}\var\varphi\end{eqnarray*}} jest też tautologią.

Dowód

{{{3}}}

Przykład

Następujące formuły \begin{eqnarray*}i wszystkie ich instancje\end{eqnarray*} są tautologiami rachunku zdań:%

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \begin{eqnarray*}\neg q\to\neg p\end{eqnarray*}\to \begin{eqnarray*}p\to q\end{eqnarray*}} ;

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \begin{eqnarray*}p\to r\end{eqnarray*}\to\begin{eqnarray*}\begin{eqnarray*}q\to r\end{eqnarray*}\to\begin{eqnarray*}p\vee q \to r\end{eqnarray*}\end{eqnarray*}} ;

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \begin{eqnarray*}r\to p\end{eqnarray*}\to\begin{eqnarray*}\begin{eqnarray*}r\to q\end{eqnarray*}\to\begin{eqnarray*}r\to\begin{eqnarray*}p\wedge q\end{eqnarray*}\end{eqnarray*}\end{eqnarray*}} ;

\begin{eqnarray*}p\leftrightarrow\begin{eqnarray*}q\leftrightarrow r\end{eqnarray*}\end{eqnarray*}</math>;

Parser nie mógł rozpoznać (błąd składni): {\displaystyle p\wedge\top\\leftrightarrow p} .

Dowód

{{{3}}}

Niektóre z powyższych formu\l\ wskazują na analogię pomiędzy\rightarrowlikacją i\boldsymbol{s}}\def\blank{\hbox{\sf Bporządkowaniem \begin{eqnarray*}np. zawieraniem zbiorów\end{eqnarray*}. Implikację$p\to q$ można odczytać tak: ,,warunek $p$ jest silniejszy \begin{eqnarray*}mniejszy lub równy\end{eqnarray*} od $q$. Formu\lę \begin{eqnarray*}#1\end{eqnarray*} czytamy wtedy: ,,fałsz jest najsilniejszym warunkiem \begin{eqnarray*}najmniejszym\Delta\vdashlementem\end{eqnarray*}. Formuły \begin{eqnarray*}#8\end{eqnarray*} stwierdzają, że alternatywa $p\vee q$ jest najsilniejszym warunkiem, który wynika zarówno z $p$ jak i z $q$ \begin{eqnarray*}czyli jest kresem górnym pary $\{p,q\}$, jak suma zbiorów\end{eqnarray*}. Formuły \begin{eqnarray*}#9\end{eqnarray*} wyrażają dualną własność koniunkcji: to jest kres dolny, czyli najsłabszy warunek \rightarrowlikujący oba argumenty.Prawa de Morgana \begin{eqnarray*}#11,#12\end{eqnarray*} wskazują też na analogie koniunkcja -- iloczyn, alternatywa -- suma, negacja -- dopełnienie. Ta ostatnia widoczna jest też w prawach wyłączonego środka \begin{eqnarray*}#5\end{eqnarray*}, podwójnej negacji \begin{eqnarray*}#6\end{eqnarray*} i kontrapozycji \begin{eqnarray*}#7\end{eqnarray*}.

O ile \begin{eqnarray*}#9\end{eqnarray*} wskazuje na analogię pomiędzy koniunkcją i iloczynemmnogościowym, o tyle warto zauważyć, że koniunkcja ma teżwłasności podobne do iloczynu kartezjańskiego. Jeśli zbiór funkcjiz $A$ do $B$ oznaczymy przez $[A\to B]$, to mamy \begin{eqnarray*}bardzo naturalną\end{eqnarray*}równoliczność $[A\times B\to C]\sim [A\to [B\to C]]$. Podobieństwo tego związku do formuły \begin{eqnarray*}#10\end{eqnarray*} nie jest wcale przypadkowe. Wrócimy do tego w Rozdziale #logint.

Formuła \begin{eqnarray*}#12a\end{eqnarray*} wyraża \rightarrowlikację z pomocą negacji i alternatywyi jest często bardzo przydatna, gdy np. chcemy przekształcić jakąśformułę do prostszej postaci.

Formuła \begin{eqnarray*}#2\end{eqnarray*} mówi, że dodatkowe założenie można zawsze zignorować. Formuła \begin{eqnarray*}#3\end{eqnarray*} \begin{eqnarray*}prawo Frege\end{eqnarray*} wyraża dystrybutywność \rightarrowlikacji względem siebie samej i może być odczytywana tak:jeśli $r$ wynika z $q$ w kontekście $p$, to ten kontekst może być włączony do założenia i konkluzji. Formuła \begin{eqnarray*}#4\end{eqnarray*} \begin{eqnarray*}prawo Peirce'a\end{eqnarray*} wyraża przy pomocy samej \rightarrowlikacji zasadniczą własnośćlogiki klasycznej: możliwość rozumowania przez zaprzeczenie. Sensprawa Peirce'a widać najlepiej gdy $q$ jest fałszem, otrzymujemy wtedyprawo Claviusa: Parser nie mógł rozpoznać (błąd składni): {\displaystyle \begin{eqnarray*}\neg p\to p\end{eqnarray*}\to p} .

Warto zauważyć, że formuły w parach \begin{eqnarray*}#6\end{eqnarray*} i \begin{eqnarray*}#7\end{eqnarray*} nie są wcale tak symetryczne jak się wydaje na pierwszy rzut oka. Na przykład, pierwsza z formu\l \begin{eqnarray*}#6\end{eqnarray*} to w istocie Parser nie mógł rozpoznać (błąd składni): {\displaystyle p \to \begin{eqnarray*}\begin{eqnarray*}p\to\bot\end{eqnarray*}\to\bot\end{eqnarray*}} .Wiedząc, że $p$ i $p\to \mathrm{\perp }$, natychmiast zgadzamy się na $\mathrm{\perp }$. Intuicyjne\boldsymbol{s}}\def\blank{\hbox{\sf Bzasadnienie drugiej formuły jest zaś w istocie związane z prawem \begin{eqnarray*}#5\end{eqnarray*}.

Własnością, która często\boldsymbol{s}}\def\blank{\hbox{\sf Bchodzi naszej\boldsymbol{s}}\def\blank{\hbox{\sf Bwagi, jest łączność równoważności \begin{eqnarray*}#13\end{eqnarray*}. W zwiazku z tym, wyrażenie Parser nie mógł rozpoznać (nieznana funkcja „\var”): {\displaystyle \var\varphi \\leftrightarrow \psi \\leftrightarrow \vartheta} można z czystym sumieniem pisać bez nawiasów. Zwróćmy jednak\boldsymbol{s}}\def\blank{\hbox{\sf Bwagę na to, że oznacza ono zupełnie co innego niż stwierdzenie że Parser nie mógł rozpoznać (nieznana funkcja „\var”): {\displaystyle \var\varphi} , $\psi$ i $\vartheta$ są sobie nawzajem równoważne!

Ostatnie na liście są dwie równoważności wyrażające taką myśl: fałsz jest,,elementem neutralnym dla alternatywy, a prawda dla koniunkcji.Dlatego $\mathrm{\perp }$ możemy\boldsymbol{s}}\def\blank{\hbox{\sf Bważać za ,,pustą alternatywę a $\mathrm{\top }$ za ,,pustą koniunkcję. Powyżej pominięto dobrze znane prawa: łączność i przemienność koniunkcji i alternatywy, ich wzajemną dystrybutywność, przechodniość,zwrotność \rightarrowlikacji itp.

Definicja

{{{3}}}

\def\blank{\hbox{\sf Btożsamiamy w myśl Przykładu #taut-rz\begin{eqnarray*}#14\end{eqnarray*} ze stałą 

$\mathrm{\top }$

, a stała

$\mathrm{\perp }$

totyle co koniunkcja z jednym pustym składnikiem.}}

Fakt

Dla każdej formuły zdaniowej istnieje równoważna jej formuław koniunkcyjnej postaci normalnej.

<span id="

Dowód jest przez indukcję \zwn długość formuły. Symbole zdaniowe są oczywiście w postaci normalnej. Zgodnie z naszą definicją, także stałe logiczne są postaciami normalnymi. Jeśli Parser nie mógł rozpoznać (nieznana funkcja „\var”): {\displaystyle \var\varphi} jest w postaci \begin{eqnarray*}*\end{eqnarray*}, to Parser nie mógł rozpoznać (nieznana funkcja „\var”): {\displaystyle \neg\var\varphi} można przekształcić w koniunkcyjną postać normalną stosując prawa De Morgana i prawa dystrybutywności:

\hfil </math>\psi\vee\begin{eqnarray*}\vartheta\wedge\zeta\end{eqnarray*}\\leftrightarrow\begin{eqnarray*}\psi\vee\vartheta\end{eqnarray*}\wedge\begin{eqnarray*}\psi\vee\zeta\end{eqnarray*}</math>\hfil</math>\psi\vee\begin{eqnarray*}\vartheta\vee\zeta\end{eqnarray*}\\leftrightarrow\begin{eqnarray*}\psi\vee\vartheta\end{eqnarray*}\vee\begin{eqnarray*}\psi\vee\zeta\end{eqnarray*}</math>.

Podobnie postępujemy z alternatywą dwóch formuł w postaci normalnej.\footnote{Ta procedura jest niestetywykładnicza \begin{eqnarray*}Ćwiczenie [[#wziawszy}\end{eqnarray*}.]]Przypadek koniunkcji jest oczywisty, a \rightarrowlikacjęeliminujemy z pomocą prawa #taut-rz\begin{eqnarray*}#12a\end{eqnarray*}. Szczegóły pozostawiamy Czytelnikowi." style="font-variant:small-caps">Dowód

{{{3}}}

\subsection*{Ćwiczenia}\begin{small}

1. 1. Zbadać, czy następujące formuły są tautologiami rachunku zdańi czy są spełnialne:

1. 1. 1. Parser nie mógł rozpoznać (błąd składni): {\displaystyle \begin{eqnarray*}p\to r\end{eqnarray*}\wedge\begin{eqnarray*}q\to s\end{eqnarray*}\wedge\begin{eqnarray*}\neg p\vee \neg s\end{eqnarray*}\to \begin{eqnarray*}\neg p\vee \neg q\end{eqnarray*}} ;
      2. Parser nie mógł rozpoznać (błąd składni): {\displaystyle \begin{eqnarray*}p\to q\end{eqnarray*}\vee\begin{eqnarray*}q\to r\end{eqnarray*}} ;
      3. Parser nie mógł rozpoznać (błąd składni): {\displaystyle \begin{eqnarray*}\begin{eqnarray*}p\to q\end{eqnarray*}\to r\end{eqnarray*}\wedge\neg\begin{eqnarray*}\begin{eqnarray*}\begin{eqnarray*}q\to r\end{eqnarray*}\to r\end{eqnarray*}\to r\end{eqnarray*}\end{eqnarray*}} ;
      4. Parser nie mógł rozpoznać (błąd składni): {\displaystyle \begin{eqnarray*}p\to q\end{eqnarray*}\wedge\begin{eqnarray*}\neg p\to r\end{eqnarray*}\to \begin{eqnarray*}r\to\neg q\end{eqnarray*}} ;
      5. Parser nie mógł rozpoznać (błąd składni): {\displaystyle \begin{eqnarray*}\begin{eqnarray*}\neg p\to q\end{eqnarray*}\to r\end{eqnarray*}\to \neg\begin{eqnarray*}p\to q\end{eqnarray*}} ;
      6. Parser nie mógł rozpoznać (błąd składni): {\displaystyle p\vee\begin{eqnarray*}\neg p\wedge q\end{eqnarray*}\vee\begin{eqnarray*}\neg p\wedge\neg q\end{eqnarray*}} ;
      7. Parser nie mógł rozpoznać (błąd składni): {\displaystyle \begin{eqnarray*}p\to q\end{eqnarray*}\vee \begin{eqnarray*}p\to \neg q\end{eqnarray*}} ;
      8. Parser nie mógł rozpoznać (błąd składni): {\displaystyle q\vee r\to \begin{eqnarray*}p\vee q\to p\vee r\end{eqnarray*}} ;
      9. </math>\begin{eqnarray*}p\vee q\vee r\end{eqnarray*}\wedge\begin{eqnarray*}q\vee\begin{eqnarray*}\neg p\wedge s\end{eqnarray*}\end{eqnarray*}\wedge \begin{eqnarray*}\neg s\vee q\vee r\end{eqnarray*}\to q</math>.

1. Czy następujące zbiory formuł są spełnialne?
   1. $\{p\to \mathrm{\neg }q,q\to \mathrm{\neg }r,r\to \mathrm{\neg }p\}$;
   2. $\{p\to q,q\to r,r\vee s\leftrightarrow \mathrm{\neg }q\}$;
   3. Parser nie mógł rozpoznać (błąd składni): {\displaystyle \{\neg\begin{eqnarray*}\neg q\vee p\end{eqnarray*}, p\vee\neg r, q\to\neg r\}} ;
   4. Parser nie mógł rozpoznać (błąd składni): {\displaystyle \{s\to q, p\vee\neg q, \neg\begin{eqnarray*}s\wedge p\end{eqnarray*}, s\}} .

\item Czy zachodzą następujące konsekwencje?

1. $p\wedge q\to \mathrm{\neg }r,p\models r\to \mathrm{\neg }q$;
2. Parser nie mógł rozpoznać (błąd składni): {\displaystyle p\to q, p\to\begin{eqnarray*}q\to r\end{eqnarray*}\models p\to r} ;
3. Parser nie mógł rozpoznać (błąd składni): {\displaystyle p\to\begin{eqnarray*}q\to r\end{eqnarray*}, p\to q\models q\to r} ;
4. Parser nie mógł rozpoznać (błąd składni): {\displaystyle \begin{eqnarray*}p\to q\end{eqnarray*}\to r, \neg p\models r} ;
5. Parser nie mógł rozpoznać (błąd składni): {\displaystyle \begin{eqnarray*}p\to q\end{eqnarray*}\to r, \neg r\models p} ;
6. $p\to q,r\to \mathrm{\neg }q\models r\to \mathrm{\neg }p$.

\item Dla dowolnej formuły Parser nie mógł rozpoznać (nieznana funkcja „\var”): {\displaystyle \var\varphi} niech Parser nie mógł rozpoznać (nieznana funkcja „\var”): {\displaystyle \hat{\var\varphi}} oznaczadualizację formuły Parser nie mógł rozpoznać (nieznana funkcja „\var”): {\displaystyle \var\varphi} , tzn. formułę powstającą z Parser nie mógł rozpoznać (nieznana funkcja „\var”): {\displaystyle \var\varphi } przez zastąpienie każdego wystąpienia $\wedge$ symbolem $\vee$ orazkażdego wystąpienia $\vee$ symbolem $\wedge$. \begin{renumerate}\item Dowieść,że Parser nie mógł rozpoznać (nieznana funkcja „\var”): {\displaystyle \var\varphi} jest tautologią wtw, gdy Parser nie mógł rozpoznać (nieznana funkcja „\var”): {\displaystyle \neg\hat{\var\varphi}} jest tautologią.\item Dowieść, że Parser nie mógł rozpoznać (nieznana funkcja „\var”): {\displaystyle \var\varphi\\leftrightarrow\psi} jest tautologią wtw, gdy Parser nie mógł rozpoznać (nieznana funkcja „\var”): {\displaystyle \hat{\var\varphi}\\leftrightarrow\hat{\psi}} jest tautologią.\end{renumerate}

\item Znależć formułę zdaniową Parser nie mógł rozpoznać (nieznana funkcja „\var”): {\displaystyle \var\varphi} , która jest spełniona dokładnieprzy wartościowaniach $\varrho$ spełniających warunki:

1. Dokładnie dwie spośród wartości Parser nie mógł rozpoznać (błąd składni): {\displaystyle \varrho\begin{eqnarray*}p\end{eqnarray*}} , Parser nie mógł rozpoznać (błąd składni): {\displaystyle \varrho\begin{eqnarray*}q\end{eqnarray*}} i Parser nie mógł rozpoznać (błąd składni): {\displaystyle \varrho\begin{eqnarray*}r\end{eqnarray*}} są równe 1.
2. Parser nie mógł rozpoznać (błąd składni): {\displaystyle \varrho\begin{eqnarray*}p\end{eqnarray*} = \varrho\begin{eqnarray*}q\end{eqnarray*} \not= \varrho\begin{eqnarray*}r\end{eqnarray*}} .

Rozwiązanie: Można to robić na różne sposoby, ale najprościej po prostu wypisać alternatywę koniunkcji, np. </math>\begin{eqnarray*}p\wedge q\wedge \neg r\end{eqnarray*}\vee\begin{eqnarray*}p \wedge\neg q \wedge r\end{eqnarray*}</math>.

\item Udowodnić, że dla dowolnej funkcji $f:\{0,1{\}}^k\to \{0,1\}$istnieje formuła Parser nie mógł rozpoznać (nieznana funkcja „\var”): {\displaystyle \var\varphi} , w której występują tylko spójniki $\to$ i $\mathrm{\perp }$oraz zmienne zdaniowe ze zbioru $\{p_1,\dots ,p_k\}$, o tej własności, że dladowolnego wartościowania zdaniowego $\varrho$ zachodzi równośćParser nie mógł rozpoznać (nieznana funkcja „\wfz”): {\displaystyle \wfz\var\varphi\varrho = f\begin{eqnarray*}\varrho\begin{eqnarray*}p_1\end{eqnarray*},\ldots, \varrho\begin{eqnarray*}p_k\end{eqnarray*}\end{eqnarray*}} . \begin{eqnarray*}Inaczej mówiąc, formuła Parser nie mógł rozpoznać (nieznana funkcja „\var”): {\displaystyle \var\varphi} definiuje funkcję zerojedynkową $f$.\end{eqnarray*}

Wskazówka: Indukcja \zwn $k$.

\item Niech $X$ będzie dowolnym zbiorem niepustym. Dowolną funkcję Parser nie mógł rozpoznać (nieznana funkcja „\warpi”): {\displaystyle \warpi:\\mbox{\small ZZ}\to\pot X} nazwijmy wartościowaniem\/ w zbiorze Parser nie mógł rozpoznać (nieznana funkcja „\pot”): {\displaystyle \pot X} . Każdej formule zdaniowej Parser nie mógł rozpoznać (nieznana funkcja „\var”): {\displaystyle \var\varphi} przypiszemy teraz pewien podzbiór Parser nie mógł rozpoznać (nieznana funkcja „\wfz”): {\displaystyle \wfz\var\varphi\warpi} zbioru $X$, który nazwiemy jej wartością\/ przy wartościowaniu Parser nie mógł rozpoznać (nieznana funkcja „\warpi”): {\displaystyle \warpi} .

• Parser nie mógł rozpoznać (nieznana funkcja „\wfz”): {\displaystyle \wfz\bot\warpi=\emptyset} oraz Parser nie mógł rozpoznać (nieznana funkcja „\wfz”): {\displaystyle \wfz\top\warpi=X} ;
• Parser nie mógł rozpoznać (nieznana funkcja „\wf”): {\displaystyle \wf\prooftree p \justifies \warpi \using \textrm{\begin{eqnarray*}W\end{eqnarray*}}\endprooftree=\warpi\begin{eqnarray*}p\end{eqnarray*}} , gdy $p$ jest symbolem zdaniowym;
• Parser nie mógł rozpoznać (nieznana funkcja „\wfz”): {\displaystyle \wfz{\neg\var\varphi}\warpi= X-\wfz{\var\varphi}\warpi} ;
• </math>\wf\prooftree \var\varphi\vee\psi \justifies \warpi \using \textrm{\begin{eqnarray*}W\end{eqnarray*}}\endprooftree=\wf\prooftree \var\varphi \justifies \warpi \using \textrm{\begin{eqnarray*}W\end{eqnarray*}}\endprooftree\cup\wf\prooftree \psi \justifies \warpi \using \textrm{\begin{eqnarray*}W\end{eqnarray*}}\endprooftree</math>;
• </math>\wf\prooftree \var\varphi\wedge\psi \justifies \warpi \using \textrm{\begin{eqnarray*}W\end{eqnarray*}}\endprooftree=\wf\prooftree \var\varphi \justifies \warpi \using \textrm{\begin{eqnarray*}W\end{eqnarray*}}\endprooftree\cap\wf\prooftree \psi \justifies \warpi \using \textrm{\begin{eqnarray*}W\end{eqnarray*}}\endprooftree</math>;
• </math>\wf\prooftree \var\varphi\to\psi \justifies \warpi}= \begin{eqnarray*}X-\wfz{\var\varphi \using \textrm{\begin{eqnarray*}W\end{eqnarray*}}\endprooftree\warpi\end{eqnarray*}\cup\wfz\psi\warpi</math>.

Udowodnić, że formuła Parser nie mógł rozpoznać (nieznana funkcja „\var”): {\displaystyle \var\varphi} jest tautologią rachunku zdań \wtw, gdy jest prawdziwa\/ w Parser nie mógł rozpoznać (nieznana funkcja „\pot”): {\displaystyle \pot X} , tj. gdy dla dowolnego Parser nie mógł rozpoznać (nieznana funkcja „\warpi”): {\displaystyle \warpi} jej wartością jest cały zbiór $X$.%%Rozwiazanie

\item Uzupełnić szczegóły dowodu Faktu #pania.Pokazać, że długość postaci normalnej może wzrosnąć wykładniczo w stosunku do rozmiaru formuły początkowej.

\item Niech formuła Parser nie mógł rozpoznać (nieznana funkcja „\var”): {\displaystyle \var\varphi\to\psi} będzie tautologią rachunku zdań. Znaleźć taką formułę $\vartheta$, że:

• Zarówno Parser nie mógł rozpoznać (nieznana funkcja „\var”): {\displaystyle \var\varphi\to\vartheta} jak i $\vartheta \to \psi$ są tautologiami rachunku zdań.
• W formule $\vartheta$ występują tylko te zmienne zdaniowe,które występują zarówno w Parser nie mógł rozpoznać (nieznana funkcja „\var”): {\displaystyle \var\varphi} jak i w $\psi$.

\item Niech Parser nie mógł rozpoznać (nieznana funkcja „\var”): {\displaystyle \var\varphi\begin{eqnarray*}p\end{eqnarray*}} będzie pewną formułą, w którejwystępuje zmienna zdaniowa $p$ i niech $q$ będzie zmienną zdaniową niewystępującą w Parser nie mógł rozpoznać (nieznana funkcja „\var”): {\displaystyle \var\varphi\begin{eqnarray*}p\end{eqnarray*}} . Przez Parser nie mógł rozpoznać (nieznana funkcja „\var”): {\displaystyle \var\varphi\begin{eqnarray*}q\end{eqnarray*}} oznaczmy formułę powstałą z Parser nie mógł rozpoznać (nieznana funkcja „\var”): {\displaystyle \var\varphi\begin{eqnarray*}p\end{eqnarray*}} przez zamianę wszystkich $p$ na $q$. Udowodnić, że jeśli

\hfil Parser nie mógł rozpoznać (nieznana funkcja „\var”): {\displaystyle \var\varphi\begin{eqnarray*}p\end{eqnarray*}, \var\varphi\begin{eqnarray*}q\end{eqnarray*} \models p\leftrightarrow q} \hfil

to istnieje formuła $\psi$, nie zawierająca zmiennych $p$ ani $q$,taka że

\hfil Parser nie mógł rozpoznać (nieznana funkcja „\var”): {\displaystyle \var\varphi\begin{eqnarray*}p\end{eqnarray*}\models p\leftrightarrow\psi} .\hfil