Test b

\titleLogika dla informatyków\author{Jerzy Tiuryn\and Jerzy Tyszkiewicz\and Paweł Urzyczyn}\date{Sierpień 2006}\maketitle

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 uł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 uniknięcia,,błędnego koła musimy więc tutaj zauważyć, że logika formalna nieopisuje rzeczywistych wywodów matematyka, ale ich uproszczonemodele, które bez zastrzeżeń można uważać za zwykłe obiektymatematyczne. Mimo tego ograniczenia, logika matematyczna dostarczaniezwykle ważnych wniosków o charakterze filozoficznymi metamatematycznym.

Logika formalna była kiedyś ezoteryczną 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ń}\setcounter{twierdzenie}{0}\label{aleksander

Jak powiedzieliśmy wyżej, logika matematyczna zajmuje się badaniemrozmaitych systemów formalnych, modelujących rzeczywiste sposobywnioskowania matematycznego. Do najprostszych takich systemów należą 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 (zdaniami orzekającymi), 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 implikacja\/ $\to$. Wygodne są też stałe logiczne\/ $\mathrm{\perp }$ (fałsz) i $\mathrm{\top }$ (prawda),które można uważać za zeroargumentowe spójniki logiczne.Dlatego nasza pierwsza definicja jest taka:

\begin{definicja} \rm Ustalamy pewien przeliczalnie nieskończony zbiór Parser nie mógł rozpoznać (nieznana funkcja „\zmz”): {\displaystyle \zmz} symboli, które będziemy nazywać zmiennymi zdaniowymi\/ i zwykle oznaczać literami $p$, $q$, itp. Pojęcie formuły zdaniowej\/ definiujemy przez indukcję:

• item Zmienne zdaniowe oraz $\mathrm{\perp }$ i $\mathrm{\top }$ są formułami zdaniowymi;
• em Jeśli napis $\phi$ jest formułą zdaniową, to także napis $\mathrm{\neg }\phi$ jest formułą zdaniową;
• item Jeśli napisy $\phi$ i $\psi$ są formułami zdaniowymi to napisy $(\phi \to \psi )$, $(\phi \vee \psi )$ i $(\phi \wedge \psi )$też są formułami zdaniowymi.

Inaczej mówiąc, formuły zdaniowe to elementy najmniejszego zbioru napisów Parser nie mógł rozpoznać (nieznana funkcja „\zfz”): {\displaystyle \zfz} , zawierającego Parser nie mógł rozpoznać (nieznana funkcja „\zmz”): {\displaystyle \zmz\cup\{\bot,\top\}} i takiego, że dla dowolnych </math>\varphi,\psi\in\zfzParser nie mógł rozpoznać (błąd składni): {\displaystyle także } \neg\varphi,(\varphi\to\psi), (\varphi\vee\psi), (\varphi\wedge\psi)</math> należą do Parser nie mógł rozpoznać (nieznana funkcja „\zfz”): {\displaystyle \zfz} .\end{definicja}

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;
2. Koniunkcja i alternatywa;
3. Implikacja.

Zatem na przykład wyrażenie $\mathrm{\neg }\phi \vee \psi \to \vartheta$ oznacza $((\mathrm{\neg }\phi \vee \psi )\to \vartheta )$, ale napis $\phi \vee \psi \wedge \vartheta$ jest niepoprawny.

Znaczenie formuł} W {\it logice klasycznej\/

formuły jest wartość logiczna tj. ,,prawda (1) lub ,,fałsz (0).Aby określić wartość formuły zdaniowej trzeba jednak najpierw ustalić wartości zmiennych.

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

• item 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} ;
• item Parser nie mógł rozpoznać (nieznana funkcja „\wfz”): {\displaystyle \wfz{p}{\varrho}=\varrho(p)} , gdy $p$ jest symbolem zdaniowym;
• em Parser nie mógł rozpoznać (nieznana funkcja „\wfz”): {\displaystyle \wfz{\neg\varphi}\varrho=1-\wfz{\varphi}\varrho} ;
• m </math>\wfz{\varphi\vee\psi}{\varrho}=\max\{\wfz{\varphi}{\varrho}, \wfz{\psi}{\varrho}\}</math>;
• m </math>\wfz{\varphi\wedge\psi}{\varrho}=\min\{\wfz{\varphi}{\varrho}, \wfz{\psi}{\varrho}\}</math>;
• em Parser nie mógł rozpoznać (nieznana funkcja „\wfz”): {\displaystyle \wfz{\varphi\to\psi}{\varrho}=0} , gdy Parser nie mógł rozpoznać (nieznana funkcja „\wfz”): {\displaystyle \wfz\varphi\varrho=1} i Parser nie mógł rozpoznać (nieznana funkcja „\wfz”): {\displaystyle \wfz\psi\varrho=0} ;
• em Parser nie mógł rozpoznać (nieznana funkcja „\wfz”): {\displaystyle \wfz{\varphi\to\psi}\varrho=1} , \wpp.

\end{definicja}

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

 Często stosowanym skrótem jest notacja $\underset{i\in I}{\bigvee }{\phi }_i$    oznaczająca alternatywę wszystkich formuł ${\phi }_i$, gdzie $i$  przebiega skończony zbiór $I$. Analogicznie stosuje się  zapis $\underset{i\in I}{\bigwedge }{\phi }_i$.

Notacja i terminologia: Jeśli Parser nie mógł rozpoznać (nieznana funkcja „\kl”): {\displaystyle \kl\varphi_\varrho=1} to piszemy też $\varrho \models \phi$ lub $\models \phi [\varrho ]$ i mówimy, że $\phi$ 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 $\mathrm{\Gamma }\models \phi$ oznacza, że każde wartościowanie spełniające wszystkie formuły z $\mathrm{\Gamma }$ spełnia także formułę $\phi$. Mówimy wtedy, że $\phi$ jest semantyczną konsekwencją\/ zbioru $\mathrm{\Gamma }$. Jeśli $\mathrm{\Gamma }=\mathrm{\varnothing }$ to zamiast $\mathrm{\Gamma }\models \phi$ piszemy po prostu $\models \phi$. Oznacza to, że formuła $\phi$ jest spełnionaprzez każde wartościowanie. Na koniec powiedzmy jeszcze, że formułami równoważnymi\/ nazywamy takie formuły $\phi$ i $\psi$, których wartości przy każdym wartościowaniu są takie same (tj. takie, że równoważność Parser nie mógł rozpoznać (nieznana funkcja „\oto”): {\displaystyle \varphi\oto\psi} jest tautologią ---patrz niżej).

\begin{definicja}\rm       Formuła $\phi$ jest spełnialna\/, gdy $\varrho \models \phi$     zachodzi dla pewnego wartościowania $\rho$. Jeśli zaś $\models \phi$   to mówimy, że $\phi$ jest   tautologią\/ (klasycznego) rachunku zdań. Oczywiście $\mathrm{\neg }\phi$  jest spełnialna \wtw, gdy $\phi$ nie jest tautologią.\end{definicja}

===Tautologie rachunku zdań===

 Niech $S$ będzie funkcją przypisujacą symbolom zdaniowym pewne formuły.    Jeśli $\phi$ jest formułą zdaniową, to przez $S(\phi )$ oznaczymy   formu\lę otrzymaną z $\phi$ przez jednoczesną zamianę każdego wystąpienia zmiennej       zdaniowej $p$ na formu\lę $S(p)$. Mówimy, że formuła $S(\phi )$ jest    instancją\/ schematu zdaniowego $\phi$. Używamy oznaczenia   $S(\mathrm{\Gamma })=\{S(\psi )|\psi \in \mathrm{\Gamma }\}$.

\begin{fakt}    Jeżeli\/ $\mathrm{\Gamma }$ jest zbiorem formu\l\ rachunku zdań i     $\mathrm{\Gamma }\models \phi$, to także $S(\mathrm{\Gamma })\models S(\phi )$.   W szczególności, jeśli $\phi$ jest tautologią   to $S(\phi )$ jest też tautologią.\end{fakt}\vspace{-5mm}\begin{dowod} Ćwiczenie.\end{dowod}

\begin{przyklad}  \rm\parskip=2mmNastępujące formuły (i wszystkie ich instancje) są tautologiami rachunku zdań:%

1. tem $\mathrm{\perp }\to p$;
2. tem $p\to (q\to p)$;
3. tem $(p\to (q\to r))\to ((p\to q)\to (p\to r))$;
4. tem $((p\to q)\to p)\to p$;
5. tem $p\vee \mathrm{\neg }p$;
6. \item $p\to \mathrm{\neg }\mathrm{\neg }p$\quad oraz \quad $\mathrm{\neg }\mathrm{\neg }p\to p$;
7. tem $(p\to q)\to (\mathrm{\neg }q\to \mathrm{\neg }p)$ \quad oraz \quad $(\mathrm{\neg }q\to \mathrm{\neg }p)\to (p\to q)$;
8. \item $p\to (p\vee q)$, \quad $q\to (p\vee q)$\quad oraz \quad $(p\to r)\to ((q\to r)\to (p\vee q\to r))$;
9. \item $(p\wedge q)\to p$,\quad $(p\wedge q)\to q$\quad oraz \quad $(r\to p)\to ((r\to q)\to (r\to (p\wedge q)))$;
10. tem $((p\wedge q)\to r)\leftrightarrow (p\to (q\to r))$;
11. tem $\mathrm{\neg }(p\vee q)\leftrightarrow (\mathrm{\neg }p\wedge \mathrm{\neg }q)$;
12. tem $\mathrm{\neg }(p\wedge q)\leftrightarrow (\mathrm{\neg }p\vee \mathrm{\neg }q)$;
13. tem Parser nie mógł rozpoznać (nieznana funkcja „\oto”): {\displaystyle (p\to q)\oto (\neg p\vee q)} ;
14. em </math>((p\leftrightarrow q)\leftrightarrow r) \leftrightarrow (p\leftrightarrow(q\leftrightarrow r))</math>;
15. tem Parser nie mógł rozpoznać (nieznana funkcja „\oto”): {\displaystyle p\vee\bot\oto p} \quad oraz \quad Parser nie mógł rozpoznać (nieznana funkcja „\oto”): {\displaystyle p\wedge\top\oto p} .

\begin{dowod} Łatwy. \end{dowod}

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

O ile (#9) 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 funkcji      z $A$ do $B$ oznaczymy przez $[A\to B]$, to mamy (bardzo naturalną)  równoliczność $[A\times B\to C]\sim [A\to [B\to C]]$. Podobieństwo  tego związku do formuły (#10) nie jest wcale przypadkowe.  Wrócimy do tego w Rozdziale #logint. 

Formuła (#12a) wyraża implikację z pomocą negacji i alternatywyi jest często bardzo przydatna, gdy np. chcemy przekształcić jakąśformułę do prostszej postaci. 

Formuła (#2) mówi, że dodatkowe założenie można zawsze  zignorować. Formuła (#3) (prawo Frege) wyraża dystrybutywność implikacji 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 (#4) (prawo Peirce'a) wyraża przy pomocy samej implikacji zasadniczą własnośćlogiki klasycznej: możliwość rozumowania przez zaprzeczenie. Sens  prawa Peirce'a widać najlepiej gdy $q$ jest fałszem, otrzymujemy wtedy  prawo Claviusa: $(\mathrm{\neg }p\to p)\to p$. 

 Warto zauważyć, że formuły w parach (#6) i (#7) nie są wcale tak symetryczne jak się wydaje na pierwszy rzut oka. Na przykład,    pierwsza z formu\l (#6) to w istocie $p\to ((p\to \mathrm{\perp })\to \mathrm{\perp })$.      Wiedząc, że $p$ i $p\to \mathrm{\perp }$, natychmiast zgadzamy się na $\mathrm{\perp }$. Intuicyjne uzasadnienie drugiej formuły jest zaś w istocie związane  z prawem (#5). 

Własnością, która często uchodzi naszej uwagi, jest łączność równoważności (#13). W zwiazku z tym, wyrażenie Parser nie mógł rozpoznać (nieznana funkcja „\oto”): {\displaystyle \varphi \oto \psi \oto \vartheta} można z czystym sumieniem pisać bez nawiasów. Zwróćmy jednak uwagę na to, że oznacza ono zupełnie co innego niż stwierdzenie że $\phi$, $\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 uważ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ść implikacji itp.

===Postać normalna formuł===

\begin{definicja}\rm Każdą zmienną zdaniową i negację zmiennej zdaniowej nazwijmy literałem\/. Mówimy, że formuła zdaniowa $\phi$ jest w {\it koniunkcyjnej postaci normalnej}, gdy $\phi$ jest koniunkcją alternatyw literałów, tj.

\hfil\hfil\hfil </math>\varphi = (p^1_1\vee\cdots\vee p^{k_1}_1)\wedge\cdots\wedge (p^1_r\vee\cdots\vee p^{k_r}_r)</math>,\hfil (*)

       gdzie $r\ge 0$, $k_i\ge 0$, dla $i=0,\dots r$, a wszystkie $p_j^i$ są literałami.  Przy tym pustą koniunkcję ($r=0$) utożsamiamy w myśl       Przykładu #taut-rz(#14) ze stałą $\mathrm{\top }$, a stała $\mathrm{\perp }$ totyle co koniunkcja z jednym pustym składnikiem.\end{definicja}

\begin{fakt}  Dla każdej formuły zdaniowej istnieje równoważna jej formuław koniunkcyjnej postaci normalnej.\end{fakt}\begin{dowod}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 $\phi$ jest w postaci (*), to $\mathrm{\neg }\phi$można przekształcić w koniunkcyjną postać normalną stosując prawa De Morgana i prawa dystrybutywności:

\hfil </math>\psi\vee(\vartheta\wedge\zeta)\oto (\psi\vee\vartheta)\wedge(\psi\vee\zeta)</math>\hfil </math>\psi\vee(\vartheta\vee\zeta)\oto (\psi\vee\vartheta)\vee(\psi\vee\zeta)</math>.

Podobnie postępujemy z alternatywą dwóch formuł w postaci normalnej.\footnote{Ta procedura jest niestety wykładnicza (Ćwiczenie [[#wziawszy}).]]Przypadek koniunkcji jest oczywisty, a implikację eliminujemy z pomocą prawa #taut-rz(#12a). Szczegóły pozostawiamy Czytelnikowi.\end{dowod}

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

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

1. 1. em $(p\to r)\wedge (q\to s)\wedge (\mathrm{\neg }p\vee \mathrm{\neg }s)\to (\mathrm{\neg }p\vee \mathrm{\neg }q)$;
   2. em $(p\to q)\vee (q\to r)$;
   3. em $((p\to q)\to r)\wedge \mathrm{\neg }(((q\to r)\to r)\to r))$;
   4. em $(p\to q)\wedge (\mathrm{\neg }p\to r)\to (r\to \mathrm{\neg }q)$;
   5. em $((\mathrm{\neg }p\to q)\to r)\to \mathrm{\neg }(p\to q)$;
   6. em $p\vee (\mathrm{\neg }p\wedge q)\vee (\mathrm{\neg }p\wedge \mathrm{\neg }q)$;
   7. em $(p\to q)\vee (p\to \mathrm{\neg }q)$;
   8. em $q\vee r\to (p\vee q\to p\vee r)$;
   9. m </math>(p\vee q\vee r)\wedge(q\vee(\neg p\wedge s))\wedge (\neg s\vee q\vee r) \to q</math>.

\item Czy następujące zbiory formuł są spełnialne?

1. em $\{p\to \mathrm{\neg }q,q\to \mathrm{\neg }r,r\to \mathrm{\neg }p\}$;
2. em $\{p\to q,q\to r,r\vee s\leftrightarrow \mathrm{\neg }q\}$;
3. em $\{\mathrm{\neg }(\mathrm{\neg }q\vee p),p\vee \mathrm{\neg }r,q\to \mathrm{\neg }r\}$;
4. em $\{s\to q,p\vee \mathrm{\neg }q,\mathrm{\neg }(s\wedge p),s\}$.

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

1. em $p\wedge q\to \mathrm{\neg }r,p\models r\to \mathrm{\neg }q$;
2. em $p\to q,p\to (q\to r)\models p\to r$;
3. em $p\to (q\to r),p\to q\models q\to r$;
4. em $(p\to q)\to r,\mathrm{\neg }p\models r$;
5. em $(p\to q)\to r,\mathrm{\neg }r\models p$;
6. em $p\to q,r\to \mathrm{\neg }q\models r\to \mathrm{\neg }p$.

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

 \item Znależć formułę zdaniową $\phi$, która jest spełniona dokładnie  przy wartościowaniach $\varrho$ spełniających warunki:

1. item Dokładnie dwie spośród wartości $\varrho (p)$, $\varrho (q)$ i $\varrho (r)$ są równe 1.
2. em $\varrho (p)=\varrho (q)=\varrho (r)$.

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

\item    Udowodnić, że dla dowolnej funkcji $f:\{0,1{\}}^k\to \{0,1\}$      istnieje formuła $\phi$, 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 dla  dowolnego wartościowania zdaniowego $\varrho$ zachodzi równość  Parser nie mógł rozpoznać (nieznana funkcja „\wfz”): {\displaystyle \wfz\varphi\varrho = f(\varrho(p_1),\ldots, \varrho(p_k))}
.     (Inaczej mówiąc, formuła $\phi$ definiuje funkcję zerojedynkową $f$.) 

  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:\zmz\to\pot X}
 nazwijmy wartościowaniem\/     w zbiorze Parser nie mógł rozpoznać (nieznana funkcja „\pot”): {\displaystyle \pot X}
. Każdej formule zdaniowej $\phi$ przypiszemy teraz     pewien podzbiór Parser nie mógł rozpoznać (nieznana funkcja „\wfz”): {\displaystyle \wfz\varphi\warpi}
 zbioru $X$, który nazwiemy jej    wartością\/ przy wartościowaniu Parser nie mógł rozpoznać (nieznana funkcja „\warpi”): {\displaystyle \warpi}
.

• item 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} ;
• item Parser nie mógł rozpoznać (nieznana funkcja „\wfz”): {\displaystyle \wfz{p}{\warpi}=\warpi(p)} , gdy $p$ jest symbolem zdaniowym;
• em Parser nie mógł rozpoznać (nieznana funkcja „\wfz”): {\displaystyle \wfz{\neg\varphi}\warpi= X-\wfz{\varphi}\warpi} ;
• m </math>\wfz{\varphi\vee\psi}{\warpi}=\wfz{\varphi}{\warpi}\cup \wfz{\psi}{\warpi}</math>;
• m </math>\wfz{\varphi\wedge\psi}{\warpi}=\wfz{\varphi}{\warpi}\cap \wfz{\psi}{\warpi}</math>;
• m </math>\wfz{\varphi\to\psi}{\warpi}= (X-\wfz{\varphi}\warpi) \cup\wfz\psi\warpi</math>.

 Udowodnić, że formuła $\phi$ 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 $\phi \to \psi$ będzie tautologią   rachunku zdań. Znaleźć taką formułę $\vartheta$, że:

• item Zarówno $\phi \to \vartheta$ jak i $\vartheta \to \psi$ są tautologiami rachunku zdań.
• em W formule $\vartheta$ występują tylko te zmienne zdaniowe, które występują zarówno w $\phi$ jak i w $\psi$.

 \item Niech $\phi (p)$ będzie pewną formułą, w której    występuje zmienna zdaniowa $p$ i niech $q$ będzie zmienną zdaniową nie    występującą w $\phi (p)$. Przez $\phi (q)$ oznaczmy formułę powstałą       z $\phi (p)$ przez zamianę wszystkich $p$ na $q$. Udowodnić, że jeśli

 \hfil $\phi (p),\phi (q)\models p\leftrightarrow q$\hfil

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

 \hfil $\phi (p)\models p\leftrightarrow \psi$.\hfil

\end{small}