Rachunek zdań - zadania

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

1. Załóżmy, że $(A\vee B)\wedge (A\Rightarrow C)\wedge (B\Rightarrow C)\equiv\top$.
2. Wtedy w szczególności $A\vee B\equiv\top$.
3. Rozpatrzmy dwa możliwe przypadki:
   1. $A\equiv \top$. Wtedy skoro $A\Rightarrow C\equiv\top$, to musi też być $C\equiv\top$.
   2. $B\equiv \top$. Wtedy skoro $B\Rightarrow C\equiv\top$, to musi też być $C\equiv\top$.
4. 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)$.

1. $\lnot(P\wedge Q)\equiv (\lnot P\vee \lnot Q)$,
2. $\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.