Zadanie 1. Wprowadź odpowiednie oznaczenia i zapisz w postaci wyrażenia rachunku zdań, następujące stwierdzenie:
- Jeśli Twój pies to jamnik lub pudelek, to będziemy wspólnie chodzić do parku.
Zaprzecz temu zdaniu i wyraź to w języku potocznym.
- \((J\vee P)\Rightarrow W\).
Negacja tego zdania, to \((J\vee P)\wedge \lnot W\), czyli:
- Nie będziemy wspólnie chodzić do parku, mimo że posiadasz jamnika lub pudelka.
Zadanie 2. Znajdź przykład sytuacji z życia codziennego, którą można opisać wyrażeniem:
- \(((P\Rightarrow Q)\wedge \lnot Q)\Rightarrow \lnot P\).
Czy to jest tautologia rachunku zdań? Pokaż że tak, lub że nie.
- Skoro gdyby padał deszcz, to bym miał mokre ubranie, a nie mam mokrego ubrania, to znaczy że nie padał deszcz.
Istotnie, to jest tautologia rachunku zdań. Wiemy, że \(P\Rightarrow Q\) jest równoważne \(\lnot Q\Rightarrow \lnot P\). Czyli z założenia, że \(P\Rightarrow Q\) i \(\lnot Q\), wynika \(\lnot P\), czyli prawa strona implikacji.
Zadanie 3. Podaj zdanie powstałe przez zaprzeczenie:
- jeśli liczba n jest podzielna przez 3, to n jest podzielna przez 9
ale nie zaczynające się od przeczenia (tzn. nie należy zaczynać od "Nieprawda, że ..." itp.).
Złą odpowiedzią jest:
- Jeśli liczba n nie jest podzielna przez 3, to ...
- Liczba n jest podzielna przez 3 i nie jest podzielna przez 9.
Jeśli jako P oznaczymy ,liczba n jest podzielna przez 3', a przez Q oznaczymy ,liczba n jest podzielna przez 9' to pierwotne zdanie ma postać \(P\Rightarrow Q\). Wiemy, że implikacja \(P\Rightarrow Q\) jest fałszywa tylko wtedy gdy P jest prawdą, a Q jest fałszem. Czyli pisząc formalnie:
- \(\lnot\left(P\Rightarrow Q\right)\equiv P\wedge\lnot Q\).
Zadanie 4.
Oblicz wartość wyrażenia \((P \wedge \lnot Q)\Rightarrow ((\lnot P\vee Q)\Leftrightarrow (\top\wedge Q))\), dla \(P\equiv \top, Q\equiv\bot\).
- \((\top\wedge\lnot \bot)\Rightarrow ((\lnot \top\vee\bot)\Leftrightarrow (\top\wedge\bot)\).
Teraz obliczamy wartości kolejnych działań (działanie które będzie wykonane jest podkreślone):
- \((\top\wedge\underline{\lnot \bot})\Rightarrow ((\lnot \top\vee\bot)\Leftrightarrow (\top\wedge\bot)\),
- \((\underline{\top\wedge\top})\Rightarrow ((\lnot \top\vee\bot)\Leftrightarrow (\top\wedge\bot)\),
- \(\top\Rightarrow ((\underline{\lnot \top}\vee\bot)\Leftrightarrow (\top\wedge\bot)\),
- \(\top\Rightarrow ((\bot\vee\bot)\Leftrightarrow (\top\wedge\bot)\),
- \(\top\Rightarrow ((\underline{\bot\vee\bot})\Leftrightarrow (\top\wedge\bot)\),
- \(\top\Rightarrow (\bot\Leftrightarrow (\underline{\top\wedge\bot})\),
- \(\top\Rightarrow (\underline{\bot\Leftrightarrow \bot})\),
- \(\underline{\top\Rightarrow \top}\),
- \(\top\).
Czyli wartość całego wyrażenia jest równa \(\top\).
Zadanie 5.
Czy równość \(P\vee Q\equiv (P\wedge Q)\vee (P\wedge \lnot Q)\) jest prawdziwa?
Zadanie 6.
Czy równość \(P\wedge Q\equiv (P\vee Q)\wedge (P\vee \lnot Q)\wedge (\lnot P\vee Q)\) jest prawdziwa?
- \(P\equiv Q\equiv \top\): Lewa strona równa \(\top\). Po prawej stronie każdy z nawiasów równy \(\top\), więc w sumie prawa strona równa \(\top\). Czyli równość.
- \(P\equiv Q\equiv \bot\): Lewa strona równa \(\bot\). Po prawej stronie nawias \((P\vee Q)\), równy \(\bot\), więc prawa strona równa \(\bot\). Czyli równość.
- \(P\equiv\top, Q\equiv\bot\): Lewa strona równa \(\bot\). Po prawej stronie nawias \((\lnot P\vee Q)\), równy \(\bot\), więc prawa strona równa \(\bot\) Czyli równość.
- \(P\equiv\bot, Q\equiv\top\): Lewa strona równa \(\bot\). Po prawej stronie nawias \((P\vee \lnot Q)\), równy \(\bot\), więc prawa strona równa \(\bot\) Czyli równość.
Czyli (kosztem pewnego wysiłku), wykazaliśmy szukaną równość. Możemy spróbować zrobić to sprytniej.
Najpierw przypomnijmy sobie o dualności: jeśli w danej równości zamienimy wszystkie znaki \(\vee\) na \(\wedge\) i odwrotnie, oraz wszystkie znaki \(\top\), na \(\bot\) i odwrotnie, to dostaniemy równość równoważną. Zróbmy to. Otrzymujemy:
- \(P\vee Q\equiv (P\wedge Q)\vee (P\wedge \lnot Q)\vee (\lnot P\wedge Q)\)
Z definicji operacji \(\vee\), są dokładnie trzy przypadki w których prawdą jest lewa strona równości:
- \(P\wedge Q\equiv\top\),
- \(P\wedge\lnot Q\equiv\top\),
- \(\lnot P\wedge Q\equiv\top\).
Przypadki te odpowiadają dokładnie trzem możliwościom po prawej stronie. Czyli lewa strona jest prawdą, wtedy i tylko wtedy gdy któryś z czynników po prawej stronie jest prawdą. Ale to zachodzi dokładnie wtedy gdy prawa strona jest prawdą, bo czynniki po prawej stronie są połączone operacją \(\vee\).
Zadanie 7.
Sprawdź, czy tautologią jest \(\left((A\vee B)\wedge (A\Rightarrow C)\wedge (B\Rightarrow C)\right)\Rightarrow C\).
Aby pokazać, że tautologią jest zdanie postaci \(P\Rightarrow Q\), możemy pokazać, że prawdą musi być Q, ilekroć prawdą jest P. W tym przypadku sprowadza się to do wykazania, że \(C\equiv \top\), jeśli \((A\vee B)\wedge (A\Rightarrow C)\wedge (B\Rightarrow C)\equiv\top\).
- Załóżmy, że \((A\vee B)\wedge (A\Rightarrow C)\wedge (B\Rightarrow C)\equiv\top\).
- Wtedy w szczególności \(A\vee B\equiv\top\).
- Rozpatrzmy dwa możliwe przypadki:
- \(A\equiv \top\). Wtedy skoro \(A\Rightarrow C\equiv\top\), to musi też być \(C\equiv\top\).
- \(B\equiv \top\). Wtedy skoro \(B\Rightarrow C\equiv\top\), to musi też być \(C\equiv\top\).
- W obu przypadkach pokazaliśmy, że \(C\equiv\top\). To kończy dowód.
Zadanie 8.
Zapisz następujące wyrażenie w równoważnej postaci, tak by negacje występowały tylko bezpośrednio przed zmiennymi:
- \(\lnot((P\wedge Q)\Rightarrow \lnot Q))\Leftrightarrow (\lnot P\vee (Q\wedge P)\).
- \( \lnot(P\wedge Q)\equiv (\lnot P\vee \lnot Q)\),
- \( \lnot(P\vee Q)\equiv (\lnot P\wedge \lnot Q)\).
Uprośćmy nieco otrzymane zdanie korzystając z praw de'Morgana, kasowania podwójnej negacji i łączenia działań. Upraszczamy podkreślone działanie:
- \(\underline{\lnot (\lnot (P\wedge Q)\vee \lnot Q)}\Leftrightarrow (\lnot P\vee (Q\wedge P)\),
- \(\underline{\lnot\lnot}(P\wedge Q)\wedge \lnot\lnot Q\Leftrightarrow (\lnot P\vee (Q\wedge P)\),
- \((P\wedge Q)\wedge \underline{\lnot\lnot} Q\Leftrightarrow (\lnot P\vee (Q\wedge P))\),
- \(\underline{(P\wedge Q)\wedge Q}\Leftrightarrow (\lnot P\vee (Q\wedge P))\),
- \(P\wedge \underline{Q\wedge Q}\Leftrightarrow (\lnot P\vee (Q\wedge P))\),
- \(P\wedge Q\Leftrightarrow (\lnot P\vee (Q\wedge P))\).
Teraz pozbędziemy się implikacji \(\Leftrightarrow\). Skorzystamy z reguły \(A\Leftrightarrow B\equiv (A\wedge B)\vee (\lnot A\wedge\lnot B)\). Otrzymujemy wtedy:
- \(\left[(P\wedge Q)\wedge (\lnot P\vee (Q\wedge P))\right]\vee\left[\lnot(P\wedge Q)\wedge \lnot(\lnot P\vee (Q\wedge P))\right]\).
Znowu przystępujemy do upraszczania:
- \(\left[(P\wedge Q)\wedge (\lnot P\vee (Q\wedge P))\right]\vee\left[\underline{\lnot(P\wedge Q)}\wedge \lnot(\lnot P\vee(Q\wedge P))\right]\),
- \(\left[(P\wedge Q)\wedge (\lnot P\vee (Q\wedge P))\right]\vee\left[(\lnot P\vee \lnot Q)\wedge \underline{\lnot(\lnot P\vee (Q\wedge P))}\right]\),
- \(\left[(P\wedge Q)\wedge (\lnot P\vee (Q\wedge P))\right]\vee\left[(\lnot P\vee \lnot Q)\wedge \underline{\lnot\lnot} P\wedge \lnot(Q\wedge P))\right]\),
- \(\left[(P\wedge Q)\wedge (\lnot P\vee (Q\wedge P))\right]\vee\left[(\lnot P\vee \lnot Q)\wedge P\wedge \underline{\lnot(Q\wedge P))}\right]\),
- \(\left[(P\wedge Q)\wedge (\lnot P\vee (Q\wedge P))\right]\vee\left[(\lnot P\vee \lnot Q)\wedge P\wedge (\lnot Q\vee \lnot P))\right]\).
Otrzymaliśmy zdanie w którym negacje występują już tylko tuż przed zmiennymi. Czyli stanowi ono rozwiązanie zadania.
Można je jednak uprościć bardziej.
Najpierw zmieńmy kolejność wyrażeń w nawiasie kwadratowym po prawej stronie:
- \(\left[(P\wedge Q)\wedge (\lnot P\vee (Q\wedge P))\right]\vee\left[\underline{(\lnot P\vee \lnot Q)\wedge (\lnot P\vee \lnot Q)}\wedge P)\right]\).
Podkreślone wyrażenie jest postacji \(A\wedge A\), więc możemy je uprościć do:
- \(\left[(P\wedge Q)\wedge (\lnot P\vee (Q\wedge P))\right]\vee\left[(\lnot P\vee \lnot Q)\wedge P)\right]\).
Skożystajmy teraz z prawa rozdzielności dla prawego nawiasu kwadratowego:
- \(\left[(P\wedge Q)\wedge (\lnot P\vee (Q\wedge P))\right]\vee\left[\underline{(\lnot P\wedge P)}\vee (\lnot Q\wedge P)\right]\).
Podkreślony nawias jest zawsze fałszywy, więc możemy podstawić:
- \(\left[(P\wedge Q)\wedge (\lnot P\vee (Q\wedge P))\right]\vee\left[\bot\vee (\lnot Q\wedge P)\right]\)
i uprościć:
- \(\left[(P\wedge Q)\wedge (\lnot P\vee (Q\wedge P))\right]\vee(\lnot Q\wedge P)\).
Teraz będziemy upraszczać dalej:
- \(\left[(P\wedge Q)\wedge (\underline{\lnot P\vee (Q\wedge P)})\right]\vee(\lnot Q\wedge P)\),
- \(\left[(P\wedge Q)\wedge (\lnot P\vee Q)\wedge \underline{(\lnot P\vee P)}\right]\vee(\lnot Q\wedge P)\),
- \(\left[(P\wedge Q)\wedge \underline{(\lnot P\vee Q)\wedge \top}\right]\vee(\lnot Q\wedge P)\),
- \(\left[\underline{(P\wedge Q)\wedge (\lnot P\vee Q)}\right]\vee(\lnot Q\wedge P)\),
- \(\left[Q\wedge \underline{P\wedge (\lnot P\vee Q)}\right]\vee(\lnot Q\wedge P)\),
- \(\left[Q\wedge (\underline{(P\wedge \lnot P)}\vee (P\wedge Q))\right]\vee(\lnot Q\wedge P)\),
- \(\left[Q\wedge (\underline{\bot\vee (P\wedge Q)})\right]\vee(\lnot Q\wedge P)\),
- \(\left[\underline{Q\wedge P\wedge Q}\right]\vee(\lnot Q\wedge P)\),
- \((P\wedge Q)\vee(\lnot Q\wedge P)\).
Jeśli powyższe wyrażenie jest równe \(\top\), to między innymi \(P\equiv\top\). Z drugiej strony, jeśli \(P\equiv\top\), to powyższe wyrażenie też jest równe \(\top\), niezależnie od Q. Czyli pokazaliśmy, że
- \((P\wedge Q)\vee(\lnot Q\wedge P)\equiv P\).
Wniosek z tego jest taki, że całe zdanie z tego zadania jest równoważne P.