Příklady na výrokovou logiku

V článku si ukážeme několik formulí a jejich možná ohodnocení za pomocí tabulkové metody.

První příklad

Zkusíme zjistit, kdy je tato formule pravdivá: ϕ = (p ∧ q) ∨ ¬q. Zapíšeme si do tabulky výrokové symboly p a q:

$$\begin{array}{cc}p& q\\ 1& 1\\ 1& 0\\ 0& 1\\ 0& 0\end{array}$$

Dále si do tabulky dopíšeme první část formule: (p ∧ q), negaci ¬q a pak celou formuli:

$$\begin{array}{ccccc}p& q& p\wedge q& \mathrm{\neg }q& \varphi \\ 1& 1\\ 1& 0\\ 0& 1\\ 0& 0\end{array}$$

Nyní dopočítáme hodnoty pro třetí sloupec, to je jednoduchá konjunkce a zároveň i pro negaci — tam jen dosadíme obrácené hodnoty, než jaké jsou ve druhém sloupečku:

$$\begin{array}{ccccc}p& q& p\wedge q& \mathrm{\neg }q& \varphi \\ 1& 1& 1& 0\\ 1& 0& 0& 1\\ 0& 1& 0& 0\\ 0& 0& 0& 1\end{array}$$

Nakonec dopočítáme hodnoty v posledním sloupci. To je celá formule. Vzhledem k naší tabulce tak počítáme disjunkci „mezi třetím a čtvrtým sloupcem“. Výsledek:

$$\begin{array}{ccccc}p& q& p\wedge q& \mathrm{\neg }q& \varphi \\ 1& 1& 1& 0& 1\\ 1& 0& 0& 1& 1\\ 0& 1& 0& 0& 0\\ 0& 0& 0& 1& 1\end{array}$$

Druhý příklad

Stejné zadání, jiná formule: ϕ = (p ∧ ¬q) ⇔ (¬p ⇒ q). Vidíme, že ve formuli jsou výrokové symboly p a q a jejich negace. Jako první si tak vytvoříme tabulku se dvěma symboly a jejich negacemi:

$$\begin{array}{cccc}p& q& \mathrm{\neg }p& \mathrm{\neg }q\\ 1& 1& 0& 0\\ 1& 0& 0& 1\\ 0& 1& 1& 0\\ 0& 0& 1& 1\end{array}$$

Dále přidáme formule p ∧ ¬q a ¬p ⇒ q, které už umíme snadno vyhodnotit, protože máme v tabulce jak ohodnocení jednotlivých výroků, tak i jejich negací. Tabulka vypadá takto:

$$\begin{array}{cccccc}p& q& \mathrm{\neg }p& \mathrm{\neg }q& (p\wedge \mathrm{\neg }q)& (\mathrm{\neg }p\Rightarrow q)\\ 1& 1& 0& 0& 0& 1\\ 1& 0& 0& 1& 1& 1\\ 0& 1& 1& 0& 0& 1\\ 0& 0& 1& 1& 0& 0\end{array}$$

Jako poslední nám zbývá vyhodnotit celou formuli, což je ekvivalence mezi dvěma posledními sloupci:

$$\begin{array}{ccccccc}p& q& \mathrm{\neg }p& \mathrm{\neg }q& (p\wedge \mathrm{\neg }q)& (\mathrm{\neg }p\Rightarrow q)& \varphi \\ 1& 1& 0& 0& 0& 1& 0\\ 1& 0& 0& 1& 1& 1& 1\\ 0& 1& 1& 0& 0& 1& 0\\ 0& 0& 1& 1& 0& 0& 1\end{array}$$

Třetí příklad

Třetí příklad už bude trochu složitější, zkusíme tři výrokové symboly, čímž se výpočet tabulky zesložití. Formule bude vypadat takto: ϕ = (¬(p ⇒ q)) ∧ (r ⇔ (¬p ∨ q)).

Protože tam máme tři výrokové symboly, bude celkový počet variací ohodnocení rovný osmi:

$$\begin{array}{ccc}p& q& r\\ 1& 1& 1\\ 1& 1& 0\\ 1& 0& 1\\ 1& 0& 0\\ 0& 1& 1\\ 0& 1& 0\\ 0& 0& 1\\ 0& 0& 0\end{array}$$

Dále už budeme postupovat stejně jako v předchozím případě, každý sloupeček ohodnotíme ve všech osmi řádcích. Celá tabulka bude vypadat takto:

$$\begin{array}{ccccccccc}p& q& r& \mathrm{\neg }p& (p\Rightarrow q)& (\mathrm{\neg }p\vee q)& \mathrm{\neg }(p\Rightarrow q)& (r\iff (\mathrm{\neg }p\vee q))& \varphi \\ 1& 1& 1& 0& 1& 1& 0& 1& 0\\ 1& 1& 0& 0& 1& 1& 0& 0& 0\\ 1& 0& 1& 0& 0& 0& 1& 0& 0\\ 1& 0& 0& 0& 0& 0& 1& 1& 1\\ 0& 1& 1& 1& 1& 1& 0& 1& 0\\ 0& 1& 0& 1& 1& 1& 0& 0& 0\\ 0& 0& 1& 1& 1& 1& 0& 1& 0\\ 0& 0& 0& 1& 1& 1& 0& 0& 0\end{array}$$

Čtvrtý příklad

Tento příklad už nezadáme jako obyčejnou formuli, ale jako slovní úlohu. Tři kamarádi, kteří chtějí jít na divokou párty, kde budou modelky nahoře bez rozdávat občerstvení, se nemají tak úplně rádi a kladou si podmínky, za kterých na párty půjdou. Jejich jména jsou Martin, Jakub a Petr. Pravidla jsou následující:

1. Pokud půjde Martin, tak půjde i Jakub.
2. Na párty přijde Petr nebo, pokud tam přijde Martin, tak tam nepřijde Jakub.
3. Petr přijde právě tehdy, když nepřijde Martin nebo nepřijde Jakub.

Otázka zní, jestli můžou na párty přijít všichni? Pokud ne, kdo se na párty může podívat a neporušit žádná pravidla?

Jako první si musíme předchozí slovní výroky přepsat do výrokových symbolů a formulí. Takže označme si výrokové symboly M, J a P (Martin, Jakub, Petr) a bude to vždy značit výrok typu „Martin půjde na párty“. První pravidlo bychom mohli přepsat takto: M ⇒ J — „jestliže M, pak J“, neboli „jestliže Martin půjde na párty, pak Jakub půjde na párty“.

Druhé pravidlo bychom přepsali takto. Pravidlo začíná větou „Na párty přijde Petr nebo…“, takže evidentně budeme potřebovat disjunkci. Zatím zapíšeme toto: P ∨ … Další část věty říká: „pokud tam přijde Martin, tak tam nepřijde Jakub“. To je implikace, přičemž na pravé straně ještě musíme použít negaci. „nepřijde Jakub“ = ¬J. Celá implikace by vypadala takto: M ⇒ ¬J. To připojíme k předchozí disjunkci: P ∨ (M ⇒ ¬J).

Třetí pravidlo přepíšeme takto: začneme s „Petr přijde právě tehdy“. To znamená ekvivalenci: P ⇔ … Dále máme „nepřijde Martin nebo nepřijde Jakub“, což přepíšeme takto: ¬M ∨ ¬J. Složíme dohromady: (P ⇔ (¬M ∨ ¬J)).

Nyní všechny formule vložíme do tabulky a dopočítáme hodnoty:

$$\begin{array}{cccccc}M& J& P& (M\Rightarrow J)& (P\vee (M\Rightarrow \mathrm{\neg }J))& (P\iff (\mathrm{\neg }M\vee \mathrm{\neg }J))\\ 1& 1& 1& 1& 1& 0\\ 1& 1& 0& 1& 0& 1\\ 1& 0& 1& 0& 1& 1\\ 1& 0& 0& 0& 1& 0\\ 0& 1& 1& 1& 1& 1\\ 0& 1& 0& 1& 1& 0\\ 0& 0& 1& 1& 1& 1\\ 0& 0& 0& 1& 1& 0\end{array}$$

Otázka zněla, jestli mohou jít všichni tři chlapci na divoký mejdan. Odpověď nalezneme v prvním řádku. Ten nám odpovídá na případ, kdy všichni chlapci půjdou — to je signalizováno třemi jedničkami v prvních třech sloupcích. Jsou splněny všechny podmínky? První ano (čtvrtý sloupec), druhá také (pátý sloupec), ale poslední ne (poslední sloupec), tam je nula. Znamená to, že pokud půjdou všichni tři, tak nebude splněna třetí podmínka.

Hledáme tak ty řádky, ve kterých jsou na pozicích symbolizujících podmínky (tj. poslední tři sloupce) samé jedničky. Jednička znamená, že je podmínka splněna. Vidíme, že to nastane ve dvou případech. Když půjde Jakub a Petr, ale Martin ne a pak když půjde jen Petr.

Můžete to také vypočítat tak, že do tabulky přidáte formuli ϕ, která bude konjunkcí všech tří podmínek. Takže bude vypadat takto: ϕ = ((M ⇒ J) ∧ (P ∨ (M ⇒ ¬J)) ∧ (P ⇔ (¬M ∨ ¬J))). To znázorňuje to, co chceme — aby byly všechny formule (všechny podmínky) splněné. Tabulka by pak vypadala takto:

$$\begin{array}{ccccccc}M& J& P& (M\Rightarrow J)& (P\vee (M\Rightarrow \mathrm{\neg }J))& (P\iff (\mathrm{\neg }M\vee \mathrm{\neg }J))& \varphi \\ 1& 1& 1& 1& 1& 0& 0\\ 1& 1& 0& 1& 0& 1& 0\\ 1& 0& 1& 0& 1& 1& 0\\ 1& 0& 0& 0& 1& 0& 0\\ 0& 1& 1& 1& 1& 1& 1\\ 0& 1& 0& 1& 1& 0& 0\\ 0& 0& 1& 1& 1& 1& 1\\ 0& 0& 0& 1& 1& 0& 0\end{array}$$

Pár příkladů na tabulkovou metodu

Protože jsem si napsal program, který umí z dané formule automaticky sestavit celou tabulku, tak ho musím řádně využít a proto následuje ještě pár vyřešených formulí:

Formule: ((a ∧ ¬b) ∨ (b ∧ (b ⇒ a))). Tabulka:

$$\begin{array}{ccccc}a& b& (a\wedge \mathrm{\neg }b)& (b\wedge (b\Rightarrow a))& ((a\wedge \mathrm{\neg }b)\vee (b\wedge (b\Rightarrow a)))\\ 1& 1& 0& 1& 1\\ 1& 0& 1& 0& 1\\ 0& 1& 0& 0& 0\\ 0& 0& 0& 0& 0\end{array}$$

Formule: (a ∨ ¬a) ⇔ (b ∧ ¬b). Tabulka:

$$\begin{array}{ccccc}a& b& (a\vee \mathrm{\neg }a)& (b\wedge \mathrm{\neg }b)& ((a\vee \mathrm{\neg }a)\iff (b\wedge \mathrm{\neg }b))\\ 1& 1& 1& 0& 0\\ 1& 0& 1& 0& 0\\ 0& 1& 1& 0& 0\\ 0& 0& 1& 0& 0\end{array}$$

Formule: ¬(a ∨ b) ⇔ (¬b ∧ ¬a). Tabulka:

$$\begin{array}{ccccc}a& b& \mathrm{\neg }(a\vee b)& (\mathrm{\neg }b\wedge \mathrm{\neg }a)& (\mathrm{\neg }(a\vee b)\iff (\mathrm{\neg }b\wedge \mathrm{\neg }a))\\ 1& 1& 0& 0& 1\\ 1& 0& 0& 0& 1\\ 0& 1& 0& 0& 1\\ 0& 0& 1& 1& 1\end{array}$$

Formule: ϕ = (¬p ⇔ (q ∧ r)) ⇒ (p ∨ ¬(p ∧ q)). Tabulka:

$$\begin{array}{cccccccc}p& q& r& (q\wedge r)& \mathrm{\neg }(p\wedge q)& (\mathrm{\neg }p\iff (q\wedge r))& (p\vee \mathrm{\neg }(p\wedge q))& \varphi \\ 1& 1& 1& 1& 0& 0& 1& 1\\ 1& 1& 0& 0& 0& 1& 1& 1\\ 1& 0& 1& 0& 1& 1& 1& 1\\ 1& 0& 0& 0& 1& 1& 1& 1\\ 0& 1& 1& 1& 1& 1& 1& 1\\ 0& 1& 0& 0& 1& 0& 1& 1\\ 0& 0& 1& 0& 1& 0& 1& 1\\ 0& 0& 0& 0& 1& 0& 1& 1\end{array}$$

Formule: ϕ = ¬(p ⇔ ¬q) ∧ (r ⇒ ¬p) ∧ (p ∨ r). Tabulka:

$$\begin{array}{ccccccc}p& q& r& \mathrm{\neg }(p\iff \mathrm{\neg }q)& (r\Rightarrow \mathrm{\neg }p)& (p\vee r)& \varphi \\ 1& 1& 1& 1& 0& 1& 0\\ 1& 1& 0& 1& 1& 1& 1\\ 1& 0& 1& 0& 0& 1& 0\\ 1& 0& 0& 0& 1& 1& 0\\ 0& 1& 1& 0& 1& 1& 0\\ 0& 1& 0& 0& 1& 0& 0\\ 0& 0& 1& 1& 1& 1& 1\\ 0& 0& 0& 1& 1& 0& 0\end{array}$$