KolejnaStronaTestow

Uwaga: przekonwertowane latex2mediawiki; prawdopodobnie trzeba wprowadzi� poprawki

 =   
 =   
by 60
 =   
by 60
by -
 =   
by 10

{Spis treści} = 8pt = 0pt

{twierdzenie}{Twierdzenie} {wniosek}[twierdzenie]{Wniosek} {moral}[twierdzenie]{Morał} {lemat}[twierdzenie]{Lemat} {fakt}[twierdzenie]{Fakt} {przyklad}[twierdzenie]{Przykład} {definicja}[twierdzenie]{Definicja}

{Obrazek} [1]{{{ #1}}} [1]Szablon:PU: {{{ JTy ?}}}

{} {} {}

{} {{1{-}1}} Szablon:Na Szablon:Na

{{}-2.7mu{}} {{{-}-2.7mu{}-2.7mu{}}} Szablon:S

Logika dla informatyków {Jerzy Tiuryn Jerzy Tyszkiewicz Paweł Urzyczyn} {Sierpień 2006}

Wnioskowanie o prawdziwości rozmaitych stwierdzeń jest powszednim zajęciem matematyków i nie tylko matematyków. Dlatego filozofowie i matematycy od dawna zajmowali się systematyzacją metod wnioskowania i kryteriów ich poprawności. Oczywiście ostatecznym kryterium poprawności rozumowania pozostaje zawsze zdrowy rozsądek i przekonanie o słuszności wywodu. Logika, która narodziła się jako nauka o rozumowaniu, jest jednak ważnym i potrzebnym narzędziem, które to przekonanie ułatwia.

Szczególną rolę wśród rozmaitych działów logiki zajmuje logika matematyczna, poświęcona opisowi i analizie języka matematyki oraz poprawności wnioskowań matematycznych. Jest to dyscyplina w pewnym sensie paradoksalna: będąc sama częścią matematyki, traktuje matematykę jako swój przedmiot zainteresowania. Dla uniknięcia "błędnego koła" musimy więc tutaj zauważyć, że logika formalna nie opisuje rzeczywistych wywodów matematyka, ale ich uproszczone modele, które bez zastrzeżeń można uważać za zwykłe obiekty matematyczne. Mimo tego ograniczenia, logika matematyczna dostarcza niezwykle ważnych wniosków o charakterze filozoficznym i metamatematycznym.

Logika formalna była kiedyś ezoteryczną nauką z pogranicza filozofii i matematyki, potem stała się pełnoprawnym działem czystej matematyki. Jeszcze później, wraz z narodzinami informatyki, zaczęła być coraz bardziej 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óre z działów informatyki, w których metody logiki formalnej stały się standardowym narzędziem zarówno badacza jak i praktyka.

Rachunek zdań

{twierdzenie}{0}

Jak powiedzieliśmy wyżej, logika matematyczna zajmuje się badaniem rozmaitych systemów formalnych, modelujących rzeczywiste sposoby wnioskowania 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 to w jaki sposób prawdziwość zdań złożonych zależy od prawdziwości ich skł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:

Definicja

Ustalamy pewien przeliczalnie nieskończony zbiór  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 $\phi$ jest formułą zdaniową, to także napis

$\mathrm{\neg }\phi$ jest formułą zdaniową;

• 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 „\sc”): {\displaystyle {\cal F}_{{\sc Z}}} , zawierającego ZZ $\cup \{\mathrm{\perp },\mathrm{\top }\}$ i takiego, że dla dowolnych Parser nie mógł rozpoznać (nieznana funkcja „\sc”): {\displaystyle \varphi,\psi\in{\cal F}_{{\sc Z}}} także $\mathrm{\neg }\phi ,(\phi \to \psi ),(\phi \vee \psi ),(\phi \wedge \psi )$ należą do Parser nie mógł rozpoznać (nieznana funkcja „\sc”): {\displaystyle {\cal 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;
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 logice klasycznej interpretacją 

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.

Definicja

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ślamy przez 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} ;
• $[[p]{]}_{\varrho }=\varrho (p)$, gdy $p$ jest symbolem zdaniowym;
• Parser nie mógł rozpoznać (nieznana funkcja „\wfz”): {\displaystyle \wfz{\neg\varphi}\varrho=1-\wfz{\varphi}\varrho} ;
• $[[\phi \vee \psi ]{]}_{\varrho }=\max \{[[\phi ]{]}_{\varrho },[[\psi ]{]}_{\varrho }\}$;
• $[[\phi \wedge \psi ]{]}_{\varrho }=\min \{[[\phi ]{]}_{\varrho },[[\psi ]{]}_{\varrho }\}$;
• $[[\phi \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} ;

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

Łatwo można zauważyć, że Parser nie mógł rozpoznać (nieznana funkcja „\wfz”): {\displaystyle [\![ \varphi\to\psi ]\!]_{\varrho} = \max\{\wfz\psi\varrho,1-\wfz\varphi\varrho\}} , 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 Uzupelnic 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

{3.0cm} $\mathrm{\neg }\phi$ oznaczają odpowiednio $\phi \to \mathrm{\perp }$;
{2.0cm} $\mathrm{\top }\mathrm{\neg }\mathrm{\perp }$;
{2.0cm} $\phi \vee \psi \mathrm{\neg }\phi \to \psi$;
{2.0cm} $\phi \wedge \psi \mathrm{\neg }(\phi \to \mathrm{\neg }\psi )$.

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} wtedy i tylko wtedy, 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łniona przez 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).

Definicja

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 wtedy i tylko wtedy, gdy $\phi$ nie jest tautologią.

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ę otrzymaną z $\phi$ przez jednoczesną zamianę każdego wystąpienia zmiennej zdaniowej $p$ na formuę $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 }\}$.

Fakt

Jeżeli $\mathrm{\Gamma }$ jest zbiorem formurachunku 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ą.

Dowód

Ćwiczenie.

Przykład

= 2mm Następujące formuły (i wszystkie ich instancje) są tautologiami rachunku zdań:

1. $\mathrm{\perp }\to p$;
2. $p\to (q\to p)$;
3. $(p\to (q\to r))\to ((p\to q)\to (p\to r))$;
4. $((p\to q)\to p)\to p$;
5. $p\vee \mathrm{\neg }p$;
6. $p\to \mathrm{\neg }\mathrm{\neg }p$ oraz $\mathrm{\neg }\mathrm{\neg }p\to p$;
7. $(p\to q)\to (\mathrm{\neg }q\to \mathrm{\neg }p)$ oraz

$(\mathrm{\neg }q\to \mathrm{\neg }p)\to (p\to q)$;

1. $p\to (p\vee q)$, $q\to (p\vee q)$ oraz

$(p\to r)\to ((q\to r)\to (p\vee q\to r))$;

1. $(p\wedge q)\to p$, $(p\wedge q)\to q$ oraz

$(r\to p)\to ((r\to q)\to (r\to (p\wedge q)))$;

1. $((p\wedge q)\to r)\leftrightarrow (p\to (q\to r))$;
2. $\mathrm{\neg }(p\vee q)\leftrightarrow (\mathrm{\neg }p\wedge \mathrm{\neg }q)$;
3. $\mathrm{\neg }(p\wedge q)\leftrightarrow (\mathrm{\neg }p\vee \mathrm{\neg }q)$;
4. Parser nie mógł rozpoznać (nieznana funkcja „\oto”): {\displaystyle (p\to q)\oto (\neg p\vee q)} ;
5. $((p\leftrightarrow q)\leftrightarrow r)\leftrightarrow (p\leftrightarrow (q\leftrightarrow r))$;
6. Parser nie mógł rozpoznać (nieznana funkcja „\oto”): {\displaystyle p\vee\bot\oto p} oraz

Parser nie mógł rozpoznać (nieznana funkcja „\oto”): {\displaystyle p\wedge\top\oto p} .

Dowód

Łatwy.

Niektóre z powyższych formuwskazują na analogię pomiędzy implikacją 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ę (Uzupelnic 1|) czytamy wtedy: "fałsz jest najsilniejszym warunkiem (najmniejszym elementem)". Formuły (Uzupelnic 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 (Uzupelnic 9|) wyrażają dualną własność koniunkcji: to jest kres dolny, czyli najsłabszy warunek implikujący oba argumenty. Prawa de Morgana (Uzupelnic 11|,Uzupelnic 12|) wskazują też na analogie koniunkcja -- iloczyn, alternatywa -- suma, negacja -- dopełnienie. Ta ostatnia widoczna jest też w prawach wyłączonego środka (Uzupelnic 5|), podwójnej negacji (Uzupelnic 6|) i kontrapozycji (Uzupelnic 7|).

O ile (Uzupelnic 9|) wskazuje na analogię pomiędzy koniunkcją i iloczynem mnogoś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 (Uzupelnic 10|) nie jest wcale przypadkowe. Wrócimy do tego w Rozdziale Uzupelnic logint|.

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

Formuła (Uzupelnic 2|) mówi, że dodatkowe założenie można zawsze zignorować. Formuła (Uzupelnic 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 (Uzupelnic 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 (Uzupelnic 6|) i (Uzupelnic 7|) nie są wcale tak symetryczne jak się wydaje na pierwszy rzut oka. Na przykład, pierwsza z formu (Uzupelnic 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 (Uzupelnic 5|).

Własnością, która często uchodzi naszej uwagi, jest łączność równoważności (Uzupelnic 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ł

Definicja

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

$\phi =(p_1^1\vee \cdots \vee p_1^{k_1})\wedge \cdots \wedge (p_r^1\vee \cdots \vee p_r^{k_r})$, (*)

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 Uzupelnic taut-rz|(Uzupelnic 14|) ze stałą $\mathrm{\top }$, a stała $\mathrm{\perp }$ to tyle co koniunkcja z jednym pustym składnikiem.

Fakt

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

Dowód

Dowód jest przez indukcję ze względu na 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:

Parser nie mógł rozpoznać (nieznana funkcja „\oto”): {\displaystyle \psi\vee(\vartheta\wedge\zeta)\oto (\psi\vee\vartheta)\wedge(\psi\vee\zeta)\psi\vee(\vartheta\vee\zeta)\oto (\psi\vee\vartheta)\vee(\psi\vee\zeta)}
.

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

{Ćwiczenia}

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

i czy są spełnialne:

1. 1. $(p\to r)\wedge (q\to s)\wedge (\mathrm{\neg }p\vee \mathrm{\neg }s)\to (\mathrm{\neg }p\vee \mathrm{\neg }q)$;
   2. $(p\to q)\vee (q\to r)$;
   3. $((p\to q)\to r)\wedge \mathrm{\neg }(((q\to r)\to r)\to r))$;
   4. $(p\to q)\wedge (\mathrm{\neg }p\to r)\to (r\to \mathrm{\neg }q)$;
   5. $((\mathrm{\neg }p\to q)\to r)\to \mathrm{\neg }(p\to q)$;
   6. $p\vee (\mathrm{\neg }p\wedge q)\vee (\mathrm{\neg }p\wedge \mathrm{\neg }q)$;
   7. $(p\to q)\vee (p\to \mathrm{\neg }q)$;
   8. $q\vee r\to (p\vee q\to p\vee r)$;
   9. $(p\vee q\vee r)\wedge (q\vee (\mathrm{\neg }p\wedge s))\wedge (\mathrm{\neg }s\vee q\vee r)\to q$.
2. 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. $\{\mathrm{\neg }(\mathrm{\neg }q\vee p),p\vee \mathrm{\neg }r,q\to \mathrm{\neg }r\}$;
   4. $\{s\to q,p\vee \mathrm{\neg }q,\mathrm{\neg }(s\wedge p),s\}$.
3. Czy zachodzą następujące konsekwencje?
   1. $p\wedge q\to \mathrm{\neg }r,p\models r\to \mathrm{\neg }q$;
   2. $p\to q,p\to (q\to r)\models p\to r$;
   3. $p\to (q\to r),p\to q\models q\to r$;
   4. $(p\to q)\to r,\mathrm{\neg }p\models r$;
   5. $(p\to q)\to r,\mathrm{\neg }r\models p$;
   6. $p\to q,r\to \mathrm{\neg }q\models r\to \mathrm{\neg }p$.
4. 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$.

1. Dowieść,że $\phi$ jest tautologią wtw, gdy $\mathrm{\neg }\hat{\phi }$

jest tautologią.

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

1. Znależć formułę zdaniową $\phi$, która jest spełniona dokładnie

przy wartościowaniach $\varrho$ spełniających warunki:

1. 1. Dokładnie dwie spośród wartości $\varrho (p)$, $\varrho (q)$

i $\varrho (r)$ są równe 1.

1. 1. $\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. $(p\wedge q\wedge \mathrm{\neg }r)\vee (p\wedge \mathrm{\neg }q\wedge r)$.

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 ze względu na $k$.

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

1. • Parser nie mógł rozpoznać (nieznana funkcja „\wfz”): {\displaystyle \wfz\botv=\emptyset} oraz Parser nie mógł rozpoznać (nieznana funkcja „\wfz”): {\displaystyle \wfz\topv=X} ;
   • $[[p]{]}_v=v(p)$, gdy $p$ jest symbolem zdaniowym;
   • Parser nie mógł rozpoznać (nieznana funkcja „\wfz”): {\displaystyle \wfz{\neg\varphi}v= X-\wfz{\varphi}v} ;
   • $[[\phi \vee \psi ]{]}_v=[[\phi ]{]}_v\cup [[\psi ]{]}_v$;
   • $[[\phi \wedge \psi ]{]}_v=[[\phi ]{]}_v\cap [[\psi ]{]}_v$;
   • Parser nie mógł rozpoznać (nieznana funkcja „\wfz”): {\displaystyle [\![ \varphi\to\psi ]\!]_{v}= (X-\wfz{\varphi}v) \cup\wfz\psiv} .

Udowodnić, że formuła $\phi$ jest tautologią rachunku zdań wtedy i tylko wtedy, gdy jest prawdziwa w Parser nie mógł rozpoznać (nieznana funkcja „\potX”): {\displaystyle \potX} , tj. gdy dla dowolnego $v$ jej wartością jest cały zbiór $X$.

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

1. Niech formuła $\phi \to \psi$ będzie tautologią

rachunku zdań. Znaleźć taką formułę $\vartheta$, że:

1. • Zarówno $\phi \to \vartheta$ jak i $\vartheta \to \psi$ są

tautologiami rachunku zdań.

1. • W formule $\vartheta$ występują tylko te zmienne zdaniowe,

które występują zarówno w $\phi$ jak i w $\psi$.

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

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

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

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