Informatyka MIMUW

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

2. \( v(p \Rightarrow (p \Rightarrow q))=1 \)

3. \( v(\neg \neg q \Rightarrow p)=0 \)

4. \( v((\neg q\Rightarrow q) \Rightarrow (q \Rightarrow \neg q))=0 \)

1. (a) \( v(p)=1, v(q)=1, v(r)=0 \)

    (b) \( v(p)=0,v(q)=0 \)

    (c) \( v(p)=0,v(q)=0 \)

2. (a) \( v(p)=1,v(q)=0 \)

    (b) \( v(p)=0,v(q)=1) \)

    (c) \( v(q)=1 \)

Wszystkie podane formuły są tautologiami.

Podajemy przykład rozwiązania dla pierwszej formuły.

Ponieważ w kolumnie odpowiadającej formule \( \displaystyle (\phi \Rightarrow (\psi \Rightarrow \phi)) \) są same 1 to formuła ta jest tautologią.

Zaczniemy od pokazania, że jeśli formuły \( \displaystyle \phi \Rightarrow \psi \) oraz \( \displaystyle \phi \) są tautologiami, to formuła \( \displaystyle \psi \) jest tautologią. Dla dowodu niewprost przypuśćmy, że nie jest. Wtedy istnieje wartościowanie, które oznaczymy przez \( \displaystyle v \), dla którego \( \displaystyle v(\psi)=0 \). Ponieważ \( \displaystyle \phi \) jest tautologią, to \( \displaystyle v(\phi)=1 \). Ponieważ jednak \( \displaystyle v(\psi)=0 \) oraz \( \displaystyle v(\phi)=1 \), to z tabeli interpretacji 4.1 dostajemy \( \displaystyle v(\phi \Rightarrow \psi)=0 \). Jest to sprzeczne z faktem, że \( \displaystyle \phi \Rightarrow \psi \) jest tautologią.

Udowodnimy teraz indukcyjnie, że każda formuła, która ma dowód w klasycznym rachunku zdań, jest tautologią klasycznego rachunku zdań. Indukcję poprowadzimy ze względu na długość dowodu (długością dowodu nazywamy ilość formuł w ciągu będącym dowodem).

1. Baza indukcji. Jeśli formuła \( \displaystyle \phi \) ma dowód długości jeden, to musi być jednym z aksjomatów. W ćwiczeniu 4.1 pokazaliśmy, że wszystkie aksjomaty są tautologiami, wobec czego \( \displaystyle \phi \) jest tautologią.
2. Krok indukcyjny. Weźmy dowolne \( \displaystyle n\in N \) takie, że \( \displaystyle n>1 \) i przypuśćmy, że wszystkie formuły o dowodach silnie krótszych od \( \displaystyle n \) są tautologiami. Pokażemy, że wszystkie formuły o dowodach długości \( \displaystyle n \) są tautologiami. Weźmy dowolną formułę \( \displaystyle \Phi \) o dowodzie długości \( \displaystyle n \), niech \( \displaystyle \phi_1, \dots,\phi_{n-1},\phi_n=\Phi \) będzie dowodem \( \displaystyle \Phi \). Jeśli \( \displaystyle \Phi \) jest aksjomatem to z ćwiczenia 4.1 wynika, że \( \displaystyle \Phi \) jest tautologią. W przeciwnym przypadku \( \displaystyle \Phi \) musiała powstać przez zastosowanie reguły MP do pewnych formuł \( \displaystyle \phi_i, \phi_j \). Ponieważ \( \displaystyle \phi_i \) występuje w dowodzie formuły \( \displaystyle \Phi \) to ciąg formuł \( \displaystyle \phi_1, \dots,\phi_i \) jest dowodem formuły \( \displaystyle \phi_i \). Ponieważ istnieje dowód formuły, \( \displaystyle \phi_i \) o długości silnie mniejszej od \( \displaystyle n \) to z założenia indukcyjnego formuła \( \displaystyle \phi_i \) jest tautologią. Analogiczne rozumowanie dla \( \displaystyle \phi_j \) pokazuje, że formuła \( \displaystyle \phi_j \) też jest tautologią. Wobec tego z faktu udowodnionego na początku tego ćwiczenia wynika, że również \( \displaystyle \Phi \) jest tautologią, jako formuła powstająca przez zastosowanie reguły MP do tautologii. Wobec dowolności wyboru \( \displaystyle \Phi \) otrzymujemy, że wszystkie formuły o dowodach długości \( \displaystyle n \) są tautologiami.

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

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

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

1. Jeśli \( \mathrm {p} \) jest wartościowane na 1, to zgodnie z tabelą dla negacji 4.1 \( \neg p \) jest wartościowane na 0 i \( \neg \neg p \) jest wartościowane na 1. Jeśli \( \mathrm {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.

2. Jedyną możliwością, aby lewa strona była fałszywa jest, aby \( \mathrm {p} \) było wartościowane na 1, a \( \mathrm {q} \) na 0. Prawa stona jest fałszywa jedynie, gdy \( \neg p \) oraz \( \mathrm {q} \) są wartościowane na 0. Czyli prawa strona jest fałszywa, jedynie gdy \( \mathrm {p} \) jest wartościowane na 1 i \( \mathrm {q} \) na 0. Formuły są więc równoważne.

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

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

W pierwszych dwóch kolumnach są zapisane wartościowania zmiennych \( \mathrm {p} \) i \( \mathrm {q} \), a w pozostałych odpowiadające im wartościowania formuł zbudowanych z tych zmiennych. Ponieważ kolumna 4 i 7 są identyczne to formuły z zadania są równoważne.

5. W równoważności z poprzedniego punktu, podstawiąjąc za \( \mathrm {p} \) formułę \( \neg p \) oraz za \( \mathrm {q} \) formułę \( \neg q \) otrzymamy równoważność

\( \neg( \neg p \wedge \neg q) \equiv \neg \neg p \vee \neg\neg q. \)

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

\( \neg( \neg p \wedge \neg q) \equiv p \vee q. \)

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

\( \neg \neg( \neg p \wedge \neg q) \equiv\neg( p \vee q). \)

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

toggleSH(11)

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

\( (p \vee r)\wedge( q \vee \neg r). \)

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

2 Formuła nie jest tautologią. Wystarczy wartościować \( \mathrm {p} \) i \( \mathrm {r} \) na prawdę i \( \mathrm {q} \) na fałsz.

3. Formuła nie jest tautologią. Wystarczy wartościować \(\mathrm {p} \) i \( \mathrm {r} \) na prawdę i \( \mathrm {q} \) na fałsz.

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

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

Wygodnie jest reprezentować spójniki binarne w tabeli kwadratowej. Na przykład alternatywę zdefiniowaliśmy jako

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

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 4.3 jest zawsze spełniona. Każdy spójnik binarny możemy zdefiniować za pomocą tabelki kwadratowej, np. alternatywę zdefiniowaliśmy jako

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 4.6. Są to

1. \( F \)

2. \( \wedge \)

3. \( XOR \)

4. \( \vee \)

5. \( NOR \)

6. \( \Leftrightarrow \)

7. \( NAND \)

8. \( T \)

toggleSH(15)

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. \quad \mbox{(4.4)} \) Jeśli spójnik \( \circ \) jest łączny to dowolne dwie formuły, które są zbudowane jedynie ze spójników \( \circ \) są równoważne, jeśli występuje w nich tyle samo spójników. Dlatego dla łącznych spójników binarnych pomija się często nawiasy.

1. Formuła \( (p \vee q) \vee r \) jest fałszywa jedynie wtedy, gdy \( \mathrm {p} \),\( \mathrm {q} \) i \( \mathrm {r} \) są wartościowane na fałsz. Tak samo jest dla formuły \( p \vee( q \vee r ) \), więc są one równoważne.

2. Formuła \( (p \wedge q) \wedge r \) jest prawdziwa jedynie wtedy, gdy \( \mathrm {p} \),\( \mathrm {q} \) i \( \mathrm {r} \) są wartościowane na prawdę. Tak samo jest dla formuły \( p \wedge( q \wedge r ) \), więc są one równoważne.

3. Zbadamy równoważność formuł \( (p \Leftrightarrow q) \Leftrightarrow r \) i \( p \Leftrightarrow(q \Leftrightarrow r) \) za pomocą tabeli

Kolumna 4 i 6 są identyczne, więc odpowiadające im formuły są równoważne. Spójnik \( \Leftrightarrow \) jest więc łączny.

4. W ćwiczeniu 4.8 pokazaliśmy, że \( \displaystyle x XOR y \equiv \neg (x \Leftrightarrow y) \). Łatwo zauważyć, że

\( \displaystyle \neg a \Leftrightarrow b \equiv \neg (a\Leftrightarrow b) \equiv a \Leftrightarrow \neg b. \)

Wynika to z faktu, że każda z powyższych formuł jest prawdziwa wtedy i tylko wtedy, gdy dokładnie jedna z zmiennych jest wartościowana na 1. Wobec tego mamy

\( \displaystyle \begin{align*} p XOR (q XOR r)\equiv \\ \neg (p \Leftrightarrow \neg (q\Leftrightarrow r))\equiv \\ \neg \neg (p \Leftrightarrow (q\Leftrightarrow r)) \equiv \\ \neg \neg ((p \Leftrightarrow q)\Leftrightarrow r) \equiv \\ \neg (\neg (p \Leftrightarrow q)\Leftrightarrow r) \equiv \\ (p XOR q) XOR r. \end{align*} \)

Pokazaliśmy więc, że spójnik \( \displaystyle XOR \) jest łączny.