Příklady pravdivostních tabulek

Řešení příkladu:

Nejprve si připomeneme definici logické operace \(AND\) (konjunkce). Výsledek je pravdivý \((1)\) pouze tehdy, jsou-li oba vstupy pravdivé \((1)\). Jinak je výsledek nepravdivý \((0)\).

Tabulka pravdivosti:

\( \begin{array}{c|c|c} A & B & A \wedge B \\ \hline 0 & 0 & 0 \\ 0 & 1 & 0 \\ 1 & 0 & 0 \\ 1 & 1 & 1 \\ \end{array} \)

Vysvětlení: Pro každý řádek ověříme, zda jsou oba vstupy \(1\). Pouze v posledním řádku je to pravda, proto je výstup \(1\).

Řešení příkladu:

Logická operace OR (disjunkce) je pravdivá, pokud alespoň jeden z vstupů je pravdivý \((1)\). Výsledek je nepravdivý pouze tehdy, když jsou oba vstupy \(0\).

Tabulka pravdivosti:

\( \begin{array}{c|c|c} A & B & A \lor B \\ \hline 0 & 0 & 0 \\ 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 1 \\ \end{array} \)

Každý řádek jsme zkontrolovali podle definice \(OR\), proto jsou výsledky správné.

Řešení příkladu:

Operace \(NOT\) (negace) převrací hodnotu vstupu: z \(0\) udělá \(1\), z \(1\) udělá \(0\).

Tabulka pravdivosti:

\( \begin{array}{c|c} A & \neg A \\ \hline 0 & 1 \\ 1 & 0 \\ \end{array} \)

Výsledek jsme jednoduše získali převrácením hodnot vstupů.

Řešení příkladu:

Nejprve si rozdělíme výraz na části: \(A \wedge B\) a \(\neg C\), pak výsledky spojíme operací \(OR\).

Tabulka pro všechny kombinace (\A, B, C\):

\( \begin{array}{c|c|c|c|c|c} A & B & C & A \wedge B & \neg C & (A \wedge B) \lor (\neg C) \\ \hline 0 & 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 1 & 1 \\ 0 & 1 & 1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 1 & 1 \\ 1 & 0 & 1 & 0 & 0 & 0 \\ 1 & 1 & 0 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 & 0 & 1 \\ \end{array} \)

Každý řádek vypočteme postupně: nejprve \(A \wedge B\), potom \(\neg C\), a nakonec jejich \(OR\). Výsledky jsme zapsali ve sloupci posledním.

Řešení příkladu:

Operace XOR je pravdivá, pokud jsou vstupy různé, nepravdivá pokud jsou stejné.

Tabulka pravdivosti:

\( \begin{array}{c|c|c} A & B & A \oplus B \\ \hline 0 & 0 & 0 \\ 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \\ \end{array} \)

Výsledek byl získán kontrolou rovnosti vstupů v každém řádku.

Řešení příkladu:

Podle De Morganových zákonů platí \( \neg (A \lor B) = \neg A \wedge \neg B \). Ověříme to tabulkou pravdivosti.

\( \begin{array}{c|c|c|c|c} A & B & A \lor B & \neg (A \lor B) & \neg A \wedge \neg B \\ \hline 0 & 0 & 0 & 1 & 1 \\ 0 & 1 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 & 0 \\ 1 & 1 & 1 & 0 & 0 \\ \end{array} \)

Vidíme, že sloupce \( \neg (A \lor B) \) a \( \neg A \wedge \neg B \) jsou shodné, což potvrzuje platnost De Morganova zákona.

Řešení příkladu:

Nejdříve vypočítáme \( A \oplus B \), pak tento výsledek vynásobíme logickou operací \(AND\) s \(C\).

\( \begin{array}{c|c|c|c|c} A & B & C & A \oplus B & (A \oplus B) \wedge C \\ \hline 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 \\ 0 & 1 & 1 & 1 & 1 \\ 1 & 0 & 0 & 1 & 0 \\ 1 & 0 & 1 & 1 & 1 \\ 1 & 1 & 0 & 0 & 0 \\ 1 & 1 & 1 & 0 & 0 \\ \end{array} \)

Výsledek posledního sloupce je pravdivý jen tam, kde je \( A \oplus B = 1 \) a zároveň \( C = 1 \).

Řešení příkladu:

Definice implikace: \( A \Rightarrow B \) je nepravdivá pouze pokud \( A=1 \) a \( B=0 \), jinak je pravdivá.

Tabulka pravdivosti:

\( \begin{array}{c|c|c} A & B & A \Rightarrow B \\ \hline 0 & 0 & 1 \\ 0 & 1 & 1 \\ 1 & 0 & 0 \\ 1 & 1 & 1 \\ \end{array} \)

Tato tabulka odpovídá klasické logické definici implikace.

Řešení příkladu:

Analyzujeme jednotlivé části:

Nejdříve spočítáme \( A \Rightarrow B \), \( B \Rightarrow C \), pak jejich konjunkci a nakonec implikaci na \( A \Rightarrow C \).

Tabulka pravdivosti:

\( \begin{array}{c|c|c|c|c|c|c|c} A & B & C & A \Rightarrow B & B \Rightarrow C & (A \Rightarrow B) \wedge (B \Rightarrow C) & A \Rightarrow C & \big((A \Rightarrow B) \wedge (B \Rightarrow C)\big) \Rightarrow (A \Rightarrow C) \\ \hline 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 \\ 0 & 0 & 1 & 1 & 1 & 1 & 1 & 1 \\ 0 & 1 & 0 & 1 & 0 & 0 & 1 & 1 \\ 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 0 & 0 & 0 & 1 & 0 & 0 & 1 \\ 1 & 0 & 1 & 0 & 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 & 0 & 0 & 0 & 1 \\ 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ \end{array} \)

Poslední sloupec je vždy \(1\), což potvrzuje platnost této logické tautologie.

Řešení příkladu:

Vyhodnotíme postupně části výrazu:

Nejprve \( A \wedge \neg B \), pak jeho negaci, dále \( A \wedge C \), a nakonec \(OR\) obou výsledků.

Tabulka pravdivosti:

\( \begin{array}{c|c|c|c|c|c|c} A & B & C & \neg B & A \wedge \neg B & A \wedge C & \neg (A \wedge \neg B) \lor (A \wedge C) \\ \hline 0 & 0 & 0 & 1 & 0 & 0 & 1 \\ 0 & 0 & 1 & 1 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 & 0 & 0 & 1 \\ 0 & 1 & 1 & 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 1 & 1 & 0 & 0 \\ 1 & 0 & 1 & 1 & 1 & 1 & 1 \\ 1 & 1 & 0 & 0 & 0 & 0 & 1 \\ 1 & 1 & 1 & 0 & 0 & 1 & 1 \\ \end{array} \)

V posledním sloupci je výsledek kompletního výrazu. Výpočet jsme provedli postupně podle definic logických operací.

Řešení příkladu:

Nejprve vytvoříme tabulku se všemi kombinacemi hodnot \(P, Q, R\) a spočítáme jednotlivé části výrazu.

\( \begin{array}{c|c|c|c|c|c} P & Q & R & P \wedge Q & P \vee R & (P \wedge Q) \Rightarrow (P \vee R) \\ \hline 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 & 1 & 1 \\ 0 & 1 & 0 & 0 & 0 & 1 \\ 0 & 1 & 1 & 0 & 1 & 1 \\ 1 & 0 & 0 & 0 & 1 & 1 \\ 1 & 0 & 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 & 1 & 1 \\ \end{array} \)

Protože implikace je nepravdivá pouze pokud je antecedent pravdivý a konsekvent nepravdivý, zde je poslední sloupec vždy \(1\), což znamená, že výraz je tautologie.

Řešení příkladu:

Analyzujeme výraz podle definice De Morganových zákonů a ověříme pravdivostní hodnoty.

\( \begin{array}{c|c|c|c|c|c} X & Y & X \wedge Y & \neg (X \wedge Y) & \neg X & \neg Y & \neg X \vee \neg Y & \neg (X \wedge Y) \Leftrightarrow (\neg X \vee \neg Y) \\ \hline 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 \\ 0 & 1 & 0 & 1 & 1 & 0 & 1 & 1 \\ 1 & 0 & 0 & 1 & 0 & 1 & 1 & 1 \\ 1 & 1 & 1 & 0 & 0 & 0 & 0 & 1 \\ \end{array} \)

Poslední sloupec ukazuje, že výraz je vždy pravdivý, potvrzuje De Morganův zákon.

Řešení příkladu:

Sestavíme tabulku pravdivosti pro oba výrazy a porovnáme je.

\( \begin{array}{c|c|c|c|c|c} M & N & M \Rightarrow N & N \Rightarrow M & (M \Rightarrow N) \wedge (N \Rightarrow M) & M \Leftrightarrow N \\ \hline 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 1 & 0 & 0 \\ 1 & 1 & 1 & 1 & 1 & 1 \\ \end{array} \)

Oba výrazy mají stejné hodnoty ve všech případech, proto jsou ekvivalentní.

Řešení příkladu:

Analyzujeme výraz, který reprezentuje exkluzivní nebo \( (XOR) \), a spočítáme hodnoty.

\( \begin{array}{c|c|c|c|c} A & B & A \vee B & A \wedge B & (A \vee B) \wedge \neg (A \wedge B) \\ \hline 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 & 1 \\ 1 & 1 & 1 & 1 & 0 \\ \end{array} \)

Výraz je pravdivý právě tehdy, když právě jeden z operandů je pravdivý, což odpovídá \(XOR\).

Řešení příkladu:

Analyzujeme implikaci a její kontrapozici pomocí tabulky pravdivosti.

\( \begin{array}{c|c|c|c|c|c} P & Q & P \Rightarrow Q & \neg Q & \neg P & (\neg Q \Rightarrow \neg P) & (P \Rightarrow Q) \Rightarrow (\neg Q \Rightarrow \neg P) \\ \hline 0 & 0 & 1 & 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 0 & 1 & 1 & 1 \\ 1 & 0 & 0 & 1 & 0 & 0 & 1 \\ 1 & 1 & 1 & 0 & 0 & 1 & 1 \\ \end{array} \)

Poslední sloupec je vždy pravdivý, takže implikace je tautologie.

Řešení příkladu:

Vyhodnotíme jednotlivé části výrazu a ověříme platnost logické transitivnosti.

\( \begin{array}{c|c|c|c|c|c|c|c} X & Y & Z & X \Rightarrow Y & Y \Rightarrow Z & (X \Rightarrow Y) \wedge (Y \Rightarrow Z) & X \Rightarrow Z & \big((X \Rightarrow Y) \wedge (Y \Rightarrow Z)\big) \Rightarrow (X \Rightarrow Z) \\ \hline 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 \\ 0 & 0 & 1 & 1 & 1 & 1 & 1 & 1 \\ 0 & 1 & 0 & 1 & 0 & 0 & 1 & 1 \\ 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 0 & 0 & 0 & 1 & 0 & 0 & 1 \\ 1 & 0 & 1 & 0 & 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 & 0 & 0 & 0 & 1 \\ 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ \end{array} \)

Poslední sloupec je vždy \(1\), což potvrzuje platnost této tautologie.

Řešení příkladu:

Ověříme De Morganův zákon pro negaci disjunkce.

\( \begin{array}{c|c|c|c|c|c|c} A & B & A \vee B & \neg (A \vee B) & \neg A & \neg B & \neg A \wedge \neg B & \neg (A \vee B) \Leftrightarrow (\neg A \wedge \neg B) \\ \hline 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 0 & 1 & 0 & 0 & 1 \\ 1 & 0 & 1 & 0 & 0 & 1 & 0 & 1 \\ 1 & 1 & 1 & 0 & 0 & 0 & 0 & 1 \\ \end{array} \)

Výraz je vždy pravdivý, což potvrzuje platnost De Morganova zákona.

Řešení příkladu:

Vyhodnotíme pravdivostní hodnoty pro daný výraz.

\( \begin{array}{c|c|c|c|c} P & Q & P \vee Q & Q \vee P & (P \vee Q) \Rightarrow (Q \vee P) \\ \hline 0 & 0 & 0 & 0 & 1 \\ 0 & 1 & 1 & 1 & 1 \\ 1 & 0 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 & 1 \\ \end{array} \)

Výraz je vždy pravdivý, tedy tautologie.

Řešení příkladu:

Ověříme ekvivalenci negace implikace a konjunkce.

\( \begin{array}{c|c|c|c|c|c} X & Y & X \Rightarrow Y & \neg (X \Rightarrow Y) & \neg Y & X \wedge \neg Y & \neg (X \Rightarrow Y) \Leftrightarrow (X \wedge \neg Y) \\ \hline 0 & 0 & 1 & 0 & 1 & 0 & 1 \\ 0 & 1 & 1 & 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 0 & 0 & 0 & 1 \\ \end{array} \)

Poslední sloupec je vždy \(1\), výraz je tautologie.

Řešení příkladu:

Provedeme vyhodnocení pravdivostních hodnot složeného výrazu.

\( \begin{array}{c|c|c|c|c|c|c|c|c} A & B & C & A \wedge B & (A \wedge B) \Rightarrow C & B \Rightarrow C & A \Rightarrow (B \Rightarrow C) & ((A \wedge B) \Rightarrow C) \Rightarrow (A \Rightarrow (B \Rightarrow C)) \\ \hline 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 0 & 1 & 0 & 1 & 1 & 1 & 1 \\ 0 & 1 & 0 & 0 & 1 & 0 & 1 & 1 \\ 0 & 1 & 1 & 0 & 1 & 1 & 1 & 1 \\ 1 & 0 & 0 & 0 & 1 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 & 1 & 1 & 1 & 1 \\ 1 & 1 & 0 & 1 & 0 & 0 & 0 & 1 \\ 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ \end{array} \)

Poslední sloupec je vždy pravdivý, což potvrzuje platnost implikace.

Řešení příkladu:

Nejdříve vypočítáme hodnoty \( A \wedge B \) a \( B \vee C \), pak implikaci \( (A \wedge B) \Rightarrow (B \vee C) \).

Tabulka pravdivosti:

\( \begin{array}{c|c|c|c|c|c} A & B & C & A \wedge B & B \vee C & (A \wedge B) \Rightarrow (B \vee C) \\ \hline 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 & 1 & 1 \\ 0 & 1 & 0 & 0 & 1 & 1 \\ 0 & 1 & 1 & 0 & 1 & 1 \\ 1 & 0 & 0 & 0 & 0 & 1 \\ 1 & 0 & 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 & 1 & 1 \\ \end{array} \)

Implikace je pravdivá ve všech případech kromě těch, kdy by předpoklad byl pravdivý a důsledek nepravdivý, což zde nenastává.

Řešení příkladu:

Nejdříve spočítáme hodnoty \( A \vee B \), pak negaci \( \neg (A \vee B) \), zároveň \( \neg A \) a \( \neg B \) a jejich konjunkci \( \neg A \wedge \neg B \). Nakonec porovnáme rovnost výrazů.

Tabulka pravdivosti:

\( \begin{array}{c|c|c|c|c|c|c} A & B & A \vee B & \neg (A \vee B) & \neg A & \neg B & \neg A \wedge \neg B \\ \hline 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 0 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 & 0 & 1 & 0 \\ 1 & 1 & 1 & 0 & 0 & 0 & 0 \\ \end{array} \)

Výrazy \( \neg (A \vee B) \) a \( \neg A \wedge \neg B \) mají shodné hodnoty ve všech řádcích, tedy jsou ekvivalentní.

Řešení příkladu:

Nejdříve spočítáme \( A \Rightarrow B \) a \( B \Rightarrow A \), pak jejich konjunkci.

Tabulka pravdivosti:

\( \begin{array}{c|c|c|c|c} A & B & A \Rightarrow B & B \Rightarrow A & (A \Rightarrow B) \wedge (B \Rightarrow A) \\ \hline 0 & 0 & 1 & 1 & 1 \\ 0 & 1 & 1 & 0 & 0 \\ 1 & 0 & 0 & 1 & 0 \\ 1 & 1 & 1 & 1 & 1 \\ \end{array} \)

Tento výraz odpovídá logické ekvivalenci \( A \Leftrightarrow B \), která je pravdivá právě pokud mají \( A \) a \( B \) stejnou hodnotu.

Řešení příkladu:

Nejdříve spočítáme \( A \vee B \), \( A \wedge B \) a jeho negaci \( \neg (A \wedge B) \). Nakonec vypočítáme konjunkci těchto dvou hodnot.

Tabulka pravdivosti:

\( \begin{array}{c|c|c|c|c} A & B & A \vee B & A \wedge B & (A \vee B) \wedge \neg (A \wedge B) \\ \hline 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 & 1 \\ 1 & 1 & 1 & 1 & 0 \\ \end{array} \)

Výraz je pravdivý právě tehdy, když \( A \) nebo \( B \) platí, ale ne oba současně, což odpovídá výlučnému nebo \( (XOR) \).

Řešení příkladu:

Nejdříve spočítáme \( \neg A \), pak \( B \wedge \neg C \), a nakonec jejich disjunkci \( \neg A \vee (B \wedge \neg C) \).

Tabulka pravdivosti:

\( \begin{array}{c|c|c|c|c|c|c} A & B & C & \neg A & \neg C & B \wedge \neg C & \neg A \vee (B \wedge \neg C) \\ \hline 0 & 0 & 0 & 1 & 1 & 0 & 1 \\ 0 & 0 & 1 & 1 & 0 & 0 & 1 \\ 0 & 1 & 0 & 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 1 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 1 & 1 & 1 \\ 1 & 1 & 1 & 0 & 0 & 0 & 0 \\ \end{array} \)

Výraz je pravdivý, pokud neplatí \( A \) nebo platí současně \( B \) a neplatí \( C \).

Řešení příkladu:

Nejprve vypočítáme hodnoty \( \neg B \), pak konjunkci \( A \wedge \neg B \), následně disjunkci \( C \vee A \) a nakonec implikaci \( (A \wedge \neg B) \Rightarrow (C \vee A) \).

Tabulka pravdivosti:

\( \begin{array}{c|c|c|c|c|c|c} A & B & C & \neg B & A \wedge \neg B & C \vee A & (A \wedge \neg B) \Rightarrow (C \vee A) \\ \hline 0 & 0 & 0 & 1 & 0 & 0 & 1 \\ 0 & 0 & 1 & 1 & 0 & 1 & 1 \\ 0 & 1 & 0 & 0 & 0 & 0 & 1 \\ 0 & 1 & 1 & 0 & 0 & 1 & 1 \\ 1 & 0 & 0 & 1 & 1 & 1 & 1 \\ 1 & 0 & 1 & 1 & 1 & 1 & 1 \\ 1 & 1 & 0 & 0 & 0 & 1 & 1 \\ 1 & 1 & 1 & 0 & 0 & 1 & 1 \\ \end{array} \)

Implikace je nepravdivá pouze tehdy, když je předpoklad pravdivý a důsledek nepravdivý, což v tomto případě nenastává.

Řešení příkladu:

Vypočítáme hodnoty \( A \vee C \), jeho negaci \( \neg (A \vee C) \), pak implikaci \( B \Rightarrow A \) a nakonec konjunkci těchto dvou částí.

Tabulka pravdivosti:

\( \begin{array}{c|c|c|c|c|c|c} A & B & C & A \vee C & \neg (A \vee C) & B \Rightarrow A & \neg (A \vee C) \wedge (B \Rightarrow A) \\ \hline 0 & 0 & 0 & 0 & 1 & 1 & 1 \\ 0 & 0 & 1 & 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 & 1 & 0 & 0 \\ 0 & 1 & 1 & 1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 1 & 0 & 1 & 0 \\ 1 & 0 & 1 & 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 1 & 0 & 1 & 0 \\ 1 & 1 & 1 & 1 & 0 & 1 & 0 \\ \end{array} \)

Výraz je pravdivý pouze tehdy, když neplatí \( A \) ani \( C \) a zároveň platí \( B \Rightarrow A \), tedy pokud je \( B \) nepravdivé nebo \( A \) pravdivé.

Řešení příkladu:

Nejdříve spočítáme hodnoty ekvivalence \( A \Leftrightarrow B \), pak disjunkci \( A \vee C \), a nakonec implikaci z těchto hodnot.

Tabulka pravdivosti:

\( \begin{array}{c|c|c|c|c|c} A & B & C & A \Leftrightarrow B & A \vee C & (A \Leftrightarrow B) \Rightarrow (A \vee C) \\ \hline 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 1 & 0 & 0 & 0 & 1 \\ 0 & 1 & 1 & 0 & 1 & 1 \\ 1 & 0 & 0 & 0 & 1 & 1 \\ 1 & 0 & 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 & 1 & 1 \\ \end{array} \)

Implikace je nepravdivá pouze v případě, kdy platí \( A \Leftrightarrow B \) (poslední sloupec je \(1\)) a zároveň neplatí \( A \vee C \), což je první řádek.

Řešení příkladu:

Nejdříve vypočítáme hodnoty \( A \wedge B \), jeho negaci \( \neg (A \wedge B) \), hodnoty \( B \wedge C \) a nakonec disjunkci těchto dvou částí.

Tabulka pravdivosti:

\( \begin{array}{c|c|c|c|c|c|c} A & B & C & A \wedge B & \neg (A \wedge B) & B \wedge C & \neg (A \wedge B) \vee (B \wedge C) \\ \hline 0 & 0 & 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 & 1 & 0 & 1 \\ 0 & 1 & 0 & 0 & 1 & 0 & 1 \\ 0 & 1 & 1 & 0 & 1 & 1 & 1 \\ 1 & 0 & 0 & 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 & 1 & 0 & 1 \\ 1 & 1 & 0 & 1 & 0 & 0 & 0 \\ 1 & 1 & 1 & 1 & 0 & 1 & 1 \\ \end{array} \)

Výraz je pravdivý, pokud neplatí současně \( A \) a \( B \), nebo platí současně \( B \) a \( C \).

Řešení příkladu:

Nejdříve spočítáme hodnoty \( B \wedge C \), implikaci \( A \Rightarrow (B \wedge C) \), negace \( \neg B \), \( \neg C \) a jejich disjunkci, a nakonec konjunkci obou hlavních částí.

Tabulka pravdivosti:

\( \begin{array}{c|c|c|c|c|c|c|c} A & B & C & B \wedge C & A \Rightarrow (B \wedge C) & \neg B & \neg C & \neg B \vee \neg C & (A \Rightarrow (B \wedge C)) \wedge (\neg B \vee \neg C) \\ \hline 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 \\ 0 & 0 & 1 & 0 & 1 & 1 & 0 & 1 & 1 \\ 0 & 1 & 0 & 0 & 1 & 0 & 1 & 1 & 1 \\ 0 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 0 \\ 1 & 0 & 1 & 0 & 0 & 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 0 & 0 & 0 & 1 & 1 & 0 \\ 1 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 \\ \end{array} \)

Výraz je pravdivý pouze tehdy, když platí \( A \Rightarrow (B \wedge C) \) a zároveň alespoň jedna z hodnot \( B \), \( C \) je nepravdivá.

Řešení příkladu:

Nejdříve vypočítáme hodnoty \( A \vee B \), \( \neg A \), \( \neg A \vee C \), pak konjunkci \( (A \vee B) \wedge (\neg A \vee C) \), hodnoty \( B \vee C \) a nakonec implikaci celé levé části na pravou.

Tabulka pravdivosti:

\( \begin{array}{c|c|c|c|c|c|c|c|c} A & B & C & A \vee B & \neg A & \neg A \vee C & (A \vee B) \wedge (\neg A \vee C) & B \vee C & \big((A \vee B) \wedge (\neg A \vee C)\big) \Rightarrow (B \vee C) \\ \hline 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 & 1 & 1 & 0 & 1 & 1 \\ 0 & 1 & 0 & 1 & 1 & 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 \\ 1 & 0 & 1 & 1 & 0 & 1 & 1 & 1 & 1 \\ 1 & 1 & 0 & 1 & 0 & 0 & 0 & 1 & 1 \\ 1 & 1 & 1 & 1 & 0 & 1 & 1 & 1 & 1 \\ \end{array} \)

Implikace je nepravdivá pouze pokud je levá část pravdivá a pravá nepravdivá. Ve výše uvedené tabulce tato situace nenastává, proto je výraz vždy pravdivý.

Řešení příkladu:

Nejdříve spočítáme implikace \( A \Rightarrow B \), \( C \Rightarrow \neg B \), pak jejich konjunkci, negaci \( \neg (A \wedge C) \) a nakonec implikaci celé levé části na pravou.

Tabulka pravdivosti:

\( \begin{array}{c|c|c|c|c|c|c|c} A & B & C & A \Rightarrow B & C \Rightarrow \neg B & (A \Rightarrow B) \wedge (C \Rightarrow \neg B) & A \wedge C & \neg (A \wedge C) & \text{Celá implikace} \\ \hline 0 & 0 & 0 & 1 & 1 & 1 & 0 & 1 & 1 \\ 0 & 0 & 1 & 1 & 1 & 1 & 0 & 1 & 1 \\ 0 & 1 & 0 & 1 & 1 & 1 & 0 & 1 & 1 \\ 0 & 1 & 1 & 1 & 0 & 0 & 0 & 1 & 1 \\ 1 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 1 \\ 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 0 \\ 1 & 1 & 0 & 1 & 1 & 1 & 0 & 1 & 1 \\ 1 & 1 & 1 & 1 & 0 & 0 & 1 & 0 & 0 \\ \end{array} \)

Výraz je nepravdivý pouze pokud je levá část pravdivá a zároveň pravá část nepravdivá, což se stává pro řádky, kde \( A=1 \) a \( C=1 \), ale implikace \( C \Rightarrow \neg B \) je nepravdivá.

Řešení příkladu:

Nejdříve vypočítáme hodnoty \( A \wedge B \), jeho negaci \( \neg (A \wedge B) \), dále hodnoty \( \neg A \), \( \neg B \), jejich disjunkci \( \neg A \vee \neg B \) a nakonec implikaci.

Tabulka pravdivosti:

\( \begin{array}{c|c|c|c|c|c|c|c} A & B & \neg (A \wedge B) & \neg A & \neg B & \neg A \vee \neg B & \neg (A \wedge B) \Rightarrow (\neg A \vee \neg B) \\ \hline 0 & 0 & 1 & 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 1 & 0 & 1 & 1 \\ 1 & 0 & 1 & 0 & 1 & 1 & 1 \\ 1 & 1 & 0 & 0 & 0 & 0 & 1 \\ \end{array} \)

Tento výraz je logickou tautologií, protože vždy, když je levá část pravdivá, je i pravá část pravdivá, jak lze vidět z tabulky.

Řešení příkladu:

Nejdříve spočítáme hodnoty \( A \wedge B \), \( A \vee C \) a nakonec implikaci těchto dvou výrazů.

Tabulka pravdivosti:

\( \begin{array}{c|c|c|c|c|c} A & B & C & A \wedge B & A \vee C & (A \wedge B) \Rightarrow (A \vee C) \\ \hline 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 & 1 & 1 \\ 0 & 1 & 0 & 0 & 0 & 1 \\ 0 & 1 & 1 & 0 & 1 & 1 \\ 1 & 0 & 0 & 0 & 1 & 1 \\ 1 & 0 & 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 & 1 & 1 \\ \end{array} \)

Výraz je vždy pravdivý, protože kdykoliv je předpoklad \( A \wedge B \) pravdivý, pak musí být pravdivá i disjunkce \( A \vee C \).

Řešení příkladu:

Vyjádříme jednotlivé části:

Nejprve spočítáme \( A \wedge B \), poté negaci \( \neg (A \wedge B) \). Samostatně vyhodnotíme \( \neg A \), \( \neg B \) a jejich disjunkci \( \neg A \vee \neg B \). Nakonec vše spojíme pomocí implikace.

Tabulka pravdivosti:

\( \begin{array}{c|c|c|c|c|c|c|c} A & B & A \wedge B & \neg (A \wedge B) & \neg A & \neg B & \neg A \vee \neg B & \neg (A \wedge B) \Rightarrow (\neg A \vee \neg B) \\ \hline 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 \\ 0 & 1 & 0 & 1 & 1 & 0 & 1 & 1 \\ 1 & 0 & 0 & 1 & 0 & 1 & 1 & 1 \\ 1 & 1 & 1 & 0 & 0 & 0 & 0 & 1 \\ \end{array} \)

Vidíme, že poslední sloupec obsahuje samé jedničky, což znamená, že výraz je tautologie. To je v souladu s De Morganovým zákonem, který říká, že \( \neg (A \wedge B) \Leftrightarrow (\neg A \vee \neg B) \).

Řešení příkladu:

Postupujeme následovně:

Nejprve vyhodnotíme \( A \vee B \), následně \( (A \vee B) \wedge C \). Poté spočítáme \( B \wedge C \), následně \( A \vee (B \wedge C) \). Nakonec sestavíme implikaci celého výrazu.

Tabulka pravdivosti:

\( \begin{array}{c|c|c|c|c|c|c|c} A & B & C & A \vee B & (A \vee B) \wedge C & B \wedge C & A \vee (B \wedge C) & \text{Celý výraz} \\ \hline 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 \\ 0 & 1 & 0 & 1 & 0 & 0 & 0 & 1 \\ 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 0 & 0 & 1 & 0 & 0 & 1 & 1 \\ 1 & 0 & 1 & 1 & 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 & 0 & 0 & 1 & 1 \\ 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ \end{array} \)

Ve všech řádcích je výraz pravdivý. Výraz je tedy tautologie.

Řešení příkladu:

Určíme pravdivostní hodnoty jednotlivých částí:

Nejprve spočítáme \( A \Rightarrow B \), \( B \Rightarrow A \), následně disjunkci. Pak spočítáme \( A \Leftrightarrow B \). Nakonec sestavíme implikaci.

Tabulka pravdivosti:

\( \begin{array}{c|c|c|c|c|c|c} A & B & A \Rightarrow B & B \Rightarrow A & (A \Rightarrow B) \vee (B \Rightarrow A) & A \Leftrightarrow B & \text{Celý výraz} \\ \hline 0 & 0 & 1 & 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 1 & 1 & 0 & 0 \\ 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ \end{array} \)

Vidíme, že když \( A \Rightarrow B \) nebo \( B \Rightarrow A \) platí, ještě to neznamená, že \( A \Leftrightarrow B \). Výraz není tautologie.

Řešení příkladu:

Rozdělíme na dvě části:

Levá část: \( A \vee B \), \( \neg C \), pak \( (A \vee B) \Rightarrow \neg C \).

Pravá část: \( \neg A \), \( \neg B \), \( \neg A \wedge \neg B \), pak \( (\neg A \wedge \neg B) \vee \neg C \).

Porovnáme obě části pomocí ekvivalence.

Tabulka pravdivosti:

\( \begin{array}{c|c|c|c|c|c|c|c|c|c} A & B & C & A \vee B & \neg C & \text{Levá} & \neg A & \neg B & \text{Pravá} & \text{Celý výraz} \\ \hline 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 & 1 \\ 0 & 0 & 1 & 0 & 0 & 1 & 1 & 1 & 1 & 1 \\ 0 & 1 & 0 & 1 & 1 & 1 & 1 & 0 & 1 & 1 \\ 0 & 1 & 1 & 1 & 0 & 0 & 1 & 0 & 0 & 1 \\ 1 & 0 & 0 & 1 & 1 & 1 & 0 & 1 & 1 & 1 \\ 1 & 0 & 1 & 1 & 0 & 0 & 0 & 1 & 0 & 1 \\ 1 & 1 & 0 & 1 & 1 & 1 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 1 \\ \end{array} \)

Výraz není tautologie, protože ekvivalence není vždy pravdivá.

Řešení příkladu:

Levá část: \( \neg A \Rightarrow B \). Pravá část: \( A \vee C \Rightarrow B \).

Celkový výraz: implikace mezi těmito dvěma částmi.

Tabulka pravdivosti:

\( \begin{array}{c|c|c|c|c|c|c|c} A & B & C & \neg A & \neg A \Rightarrow B & A \vee C & (A \vee C) \Rightarrow B & \text{Celý výraz} \\ \hline 0 & 0 & 0 & 1 & 0 & 0 & 1 & 1 \\ 0 & 0 & 1 & 1 & 0 & 1 & 0 & 1 \\ 0 & 1 & 0 & 1 & 1 & 0 & 1 & 1 \\ 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 0 & 0 & 0 & 1 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 & 1 & 1 & 0 & 0 \\ 1 & 1 & 0 & 0 & 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 0 & 1 & 1 & 1 & 1 \\ \end{array} \)

Vidíme, že poslední sloupec obsahuje jak jedničky, tak nuly. Výraz není tautologie.

Řešení příkladu:

Analyzujeme jednotlivé části:

Nejdříve spočítáme \( A \wedge B \), poté negaci \( \neg(A \wedge B) \), dále \( \neg A \) a \( \neg B \), z nichž vytvoříme disjunkci \( \neg A \vee \neg B \), a nakonec celou implikaci.

Tabulka pravdivosti:

\( \begin{array}{c|c|c|c|c|c|c|c} A & B & A \wedge B & \neg(A \wedge B) & \neg A & \neg B & \neg A \vee \neg B & \neg(A \wedge B) \Rightarrow (\neg A \vee \neg B) \\ \hline 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 \\ 0 & 1 & 0 & 1 & 1 & 0 & 1 & 1 \\ 1 & 0 & 0 & 1 & 0 & 1 & 1 & 1 \\ 1 & 1 & 1 & 0 & 0 & 0 & 0 & 1 \\ \end{array} \)

Poslední sloupec je vždy 1, což potvrzuje platnost této implikace jako tautologie.

Řešení příkladu:

Analyzujeme jednotlivé části:

Vypočítáme \( A \vee B \), \( \neg A \), pak \( \neg A \Rightarrow B \), a nakonec celou implikaci.

Tabulka pravdivosti:

\( \begin{array}{c|c|c|c|c|c|c} A & B & A \vee B & \neg A & \neg A \Rightarrow B & (A \vee B) \Rightarrow (\neg A \Rightarrow B) \\ \hline 0 & 0 & 0 & 1 & 0 & 1 \\ 0 & 1 & 1 & 1 & 1 & 1 \\ 1 & 0 & 1 & 0 & 1 & 1 \\ 1 & 1 & 1 & 0 & 1 & 1 \\ \end{array} \)

Jediná situace, kdy \( A \vee B \) je nepravda, je v první řádce, ale pak celá implikace také platí (\(1\)), takže celý výrok je tautologií.

Řešení příkladu:

Postupně spočítáme \( A \Rightarrow C \), \( B \Rightarrow C \), jejich disjunkci, dále \( A \wedge B \), pak \( (A \wedge B) \Rightarrow C \), a nakonec celou implikaci mezi nimi.

Tabulka pravdivosti:

\( \begin{array}{c|c|c|c|c|c|c|c|c} A & B & C & A \Rightarrow C & B \Rightarrow C & (A \Rightarrow C) \vee (B \Rightarrow C) & A \wedge B & (A \wedge B) \Rightarrow C & \text{Celý výraz} \\ \hline 0 & 0 & 0 & 1 & 1 & 1 & 0 & 1 & 1 \\ 0 & 0 & 1 & 1 & 1 & 1 & 0 & 1 & 1 \\ 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 1 \\ 0 & 1 & 1 & 1 & 1 & 1 & 0 & 1 & 1 \\ 1 & 0 & 0 & 0 & 1 & 1 & 0 & 1 & 1 \\ 1 & 0 & 1 & 1 & 1 & 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 1 \\ 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ \end{array} \)

Poslední sloupec je vždy \(1\), což znamená, že daný výrok je vždy pravdivý – jedná se o tautologii.

Řešení příkladu:

Postup: spočítáme \( A \Rightarrow B \), jeho negaci \( \neg(A \Rightarrow B) \), pak \( \neg B \), a konečně \( A \wedge \neg B \). Porovnáme oba výrazy pomocí ekvivalence.

\( \begin{array}{c|c|c|c|c|c|c} A & B & A \Rightarrow B & \neg(A \Rightarrow B) & \neg B & A \wedge \neg B & \neg(A \Rightarrow B) \Leftrightarrow (A \wedge \neg B) \\ \hline 0 & 0 & 1 & 0 & 1 & 0 & 1 \\ 0 & 1 & 1 & 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 0 & 0 & 0 & 1 \\ \end{array} \)

Poslední sloupec obsahuje pouze jedničky, což znamená, že obě strany výrazu jsou vždy ekvivalentní.

Řešení příkladu:

Postupně vypočítáme \( A \vee C \), \( \neg C \), \( B \vee \neg C \), a nakonec jejich konjunkci.

\( \begin{array}{c|c|c|c|c|c|c} A & B & C & A \vee C & \neg C & B \vee \neg C & (A \vee C) \wedge (B \vee \neg C) \\ \hline 0 & 0 & 0 & 0 & 1 & 1 & 0 \\ 0 & 0 & 1 & 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 1 & 1 & 0 \\ 0 & 1 & 1 & 1 & 0 & 1 & 1 \\ 1 & 0 & 0 & 1 & 1 & 1 & 1 \\ 1 & 0 & 1 & 1 & 0 & 0 & 0 \\ 1 & 1 & 0 & 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 & 0 & 1 & 1 \\ \end{array} \)

Výsledný sloupec ukazuje, kdy je výrok pravdivý na základě kombinace vstupních hodnot.

Řešení příkladu:

Vypočítáme \( A \vee B \), \( \neg A \), \( \neg A \Rightarrow B \), a jejich ekvivalenci.

\( \begin{array}{c|c|c|c|c|c} A & B & A \vee B & \neg A & \neg A \Rightarrow B & (A \vee B) \Leftrightarrow (\neg A \Rightarrow B) \\ \hline 0 & 0 & 0 & 1 & 0 & 1 \\ 0 & 1 & 1 & 1 & 1 & 1 \\ 1 & 0 & 1 & 0 & 1 & 1 \\ 1 & 1 & 1 & 0 & 1 & 1 \\ \end{array} \)

Výraz je vždy pravdivý, takže se jedná o logickou ekvivalenci.

Řešení příkladu:

Spočítáme \( A \vee B \), \( \neg(A \vee B) \), \( \neg A \), \( \neg B \), a jejich konjunkci, poté ověříme ekvivalenci.

\( \begin{array}{c|c|c|c|c|c|c} A & B & A \vee B & \neg(A \vee B) & \neg A & \neg B & \neg A \wedge \neg B \\ \hline 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 0 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 & 0 & 1 & 0 \\ 1 & 1 & 1 & 0 & 0 & 0 & 0 \\ \end{array} \)

Oba výrazy mají vždy stejné hodnoty, což potvrzuje, že jsou logicky ekvivalentní.

Řešení příkladu:

Vypočítáme \( A \Rightarrow B \), \( \neg B \), \( \neg B \Rightarrow A \), a jejich disjunkci.

\( \begin{array}{c|c|c|c|c|c} A & B & A \Rightarrow B & \neg B & \neg B \Rightarrow A & \text{Celý výraz} \\ \hline 0 & 0 & 1 & 1 & 0 & 1 \\ 0 & 1 & 1 & 0 & 1 & 1 \\ 1 & 0 & 0 & 1 & 1 & 1 \\ 1 & 1 & 1 & 0 & 1 & 1 \\ \end{array} \)

Výrok je pravdivý pro všechny kombinace, takže se jedná o tautologii.

Řešení příkladu:

Spočítáme \( A \vee B \), \( (A \vee B) \Rightarrow C \), \( A \Rightarrow C \), \( B \Rightarrow C \), jejich konjunkci a nakonec porovnáme ekvivalenci.

\( \begin{array}{c|c|c|c|c|c|c|c} A & B & C & A \vee B & (A \vee B) \Rightarrow C & A \Rightarrow C & B \Rightarrow C & \text{Celý výraz} \\ \hline 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 0 & 1 & 0 & 1 & 1 & 1 & 1 \\ 0 & 1 & 0 & 1 & 0 & 1 & 0 & 0 \\ 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 0 & 0 & 1 & 0 & 0 & 1 & 0 \\ 1 & 0 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 1 & 0 & 1 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ \end{array} \)

Výrok není tautologií, protože v některých řádcích výrazy nejsou ekvivalentní.

Řešení příkladu:

Spočítáme \( A \Leftrightarrow B \), \( A \vee B \), \( A \Rightarrow B \), jejich konjunkci a implikaci.

\( \begin{array}{c|c|c|c|c|c|c} A & B & A \Leftrightarrow B & A \vee B & A \Rightarrow B & (A \vee B) \wedge (A \Rightarrow B) & Celý výraz \\ \hline 0 & 0 & 1 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 1 & 1 & 1 & 1 \\ 1 & 0 & 0 & 1 & 0 & 0 & 1 \\ 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ \end{array} \)

Výrok není tautologií, protože v prvním řádku má hodnotu \(0\).

Řešení příkladu:

Postupně vyhodnotíme: \( \neg A \), poté \( \neg A \Rightarrow B \), pak \( A \vee B \), a nakonec celou implikaci.

Tabulka pravdivosti:

\( \begin{array}{c|c|c|c|c|c} A & B & \neg A & \neg A \Rightarrow B & A \vee B & (A \vee B) \Rightarrow (\neg A \Rightarrow B) \\ \hline 0 & 0 & 1 & 0 & 0 & 1 \\ 0 & 1 & 1 & 1 & 1 & 1 \\ 1 & 0 & 0 & 1 & 1 & 1 \\ 1 & 1 & 0 & 1 & 1 & 1 \\ \end{array} \)

Poslední sloupec obsahuje samé jedničky, což dokazuje platnost tohoto výroku jako tautologie.

Řešení příkladu:

Určíme \( \neg B \), \( A \wedge \neg B \), poté \( B \vee A \), a nakonec celou implikaci.

Tabulka pravdivosti:

\( \begin{array}{c|c|c|c|c|c} A & B & \neg B & A \wedge \neg B & B \vee A & (A \wedge \neg B) \Rightarrow (B \vee A) \\ \hline 0 & 0 & 1 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 & 1 & 1 \\ 1 & 0 & 1 & 1 & 1 & 1 \\ 1 & 1 & 0 & 0 & 1 & 1 \\ \end{array} \)

Výraz je vždy pravdivý, tedy je tautologií.

Řešení příkladu:

Spočítáme jednotlivé části: \( \neg B \), \( A \vee \neg B \), pak negaci celku, dále \( \neg A \), a nakonec konjunkci \( \neg A \wedge B \) a ekvivalenci.

Tabulka pravdivosti:

\( \begin{array}{c|c|c|c|c|c|c|c} A & B & \neg B & A \vee \neg B & \neg(A \vee \neg B) & \neg A & \neg A \wedge B & \neg(A \vee \neg B) \Leftrightarrow (\neg A \wedge B) \\ \hline 0 & 0 & 1 & 1 & 0 & 1 & 0 & 1 \\ 0 & 1 & 0 & 0 & 1 & 1 & 1 & 1 \\ 1 & 0 & 1 & 1 & 0 & 0 & 0 & 1 \\ 1 & 1 & 0 & 1 & 0 & 0 & 0 & 1 \\ \end{array} \)

Výsledná ekvivalence je vždy pravdivá, výraz je tedy tautologií.

Řešení příkladu:

Vypočítáme \( A \Rightarrow B \), \( B \Rightarrow A \) a jejich disjunkci.

Tabulka pravdivosti:

\( \begin{array}{c|c|c|c|c} A & B & A \Rightarrow B & B \Rightarrow A & (A \Rightarrow B) \vee (B \Rightarrow A) \\ \hline 0 & 0 & 1 & 1 & 1 \\ 0 & 1 & 1 & 0 & 1 \\ 1 & 0 & 0 & 1 & 1 \\ 1 & 1 & 1 & 1 & 1 \\ \end{array} \)

Výraz je vždy pravdivý, tedy jde o tautologii.

Řešení příkladu:

Určíme \( A \Leftrightarrow B \), jeho negaci, pak \( A \oplus B \) (exkluzivní disjunkci) a jejich ekvivalenci.

Tabulka pravdivosti:

\( \begin{array}{c|c|c|c|c|c} A & B & A \Leftrightarrow B & \neg(A \Leftrightarrow B) & A \oplus B & \neg(A \Leftrightarrow B) \Leftrightarrow (A \oplus B) \\ \hline 0 & 0 & 1 & 0 & 0 & 1 \\ 0 & 1 & 0 & 1 & 1 & 1 \\ 1 & 0 & 0 & 1 & 1 & 1 \\ 1 & 1 & 1 & 0 & 0 & 1 \\ \end{array} \)

Výraz je vždy pravdivý – jde o tautologii vyjadřující, že negace ekvivalence je totéž jako exkluzivní disjunkce.

Řešení příkladu:

Výraz ilustruje distributivní zákony De Morganových pravidel. Postupně spočítáme levou i pravou stranu a jejich ekvivalenci.

Tabulka pravdivosti:

\( \begin{array}{c|c|c|c|c|c|c|c|c} A & B & C & B \vee C & A \wedge (B \vee C) & \neg(A \wedge (B \vee C)) & \neg A & \neg B \wedge \neg C & \neg A \vee (\neg B \wedge \neg C) \\ \hline 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 0 & 1 & 1 & 0 & 1 & 1 & 0 & 1 \\ 0 & 1 & 0 & 1 & 0 & 1 & 1 & 0 & 1 \\ 0 & 1 & 1 & 1 & 0 & 1 & 1 & 0 & 1 \\ 1 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 1 \\ 1 & 0 & 1 & 1 & 1 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 1 & 1 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 \\ \end{array} \)

Poslední sloupce ukazují, že výraz je tautologií dle De Morganových zákonů.

Řešení příkladu:

Nejprve spočítáme \( A \vee B \), dále \( A \wedge B \), pak implikaci \( (A \vee B) \Rightarrow (A \wedge B) \) a nakonec tuto implikaci zavedeme jako předpoklad pro další implikaci \( ((A \vee B) \Rightarrow (A \wedge B)) \Rightarrow A \).

Tabulka pravdivosti:

\( \begin{array}{c|c|c|c|c|c|c} A & B & A \vee B & A \wedge B & (A \vee B) \Rightarrow (A \wedge B) & ((A \vee B) \Rightarrow (A \wedge B)) \Rightarrow A \\ \hline 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 1 & 1 & 0 & 0 & 1 \\ 1 & 0 & 1 & 0 & 0 & 1 \\ 1 & 1 & 1 & 1 & 1 & 1 \\ \end{array} \)

Poslední sloupec není vždy \(1\), výraz tedy není tautologie.

Řešení příkladu:

Vypočteme \( A \wedge B \), \( \neg B \), \( A \wedge \neg B \), disjunkci těchto dvou výrazů a nakonec implikaci na \( A \).

Tabulka pravdivosti:

\( \begin{array}{c|c|c|c|c|c|c} A & B & A \wedge B & \neg B & A \wedge \neg B & (A \wedge B) \vee (A \wedge \neg B) & ((A \wedge B) \vee (A \wedge \neg B)) \Rightarrow A \\ \hline 0 & 0 & 0 & 1 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 0 & 0 & 1 & 1 \\ \end{array} \)

Poslední sloupec je vždy \(1\), jedná se tedy o tautologii.

Řešení příkladu:

Nejprve spočítáme \( A \vee B \), poté jeho negaci \( \neg (A \vee B) \), následně \( \neg A \), \( \neg B \) a jejich konjunkci \( \neg A \wedge \neg B \), nakonec implikaci.

Tabulka pravdivosti:

\( \begin{array}{c|c|c|c|c|c|c|c} A & B & A \vee B & \neg (A \vee B) & \neg A & \neg B & \neg A \wedge \neg B & \neg (A \vee B) \Rightarrow (\neg A \wedge \neg B) \\ \hline 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 0 & 1 & 0 & 0 & 1 \\ 1 & 0 & 1 & 0 & 0 & 1 & 0 & 1 \\ 1 & 1 & 1 & 0 & 0 & 0 & 0 & 1 \\ \end{array} \)

Poslední sloupec je vždy \(1\), výraz je tedy tautologie a odpovídá De Morganově zákonu.

Řešení příkladu:

Postupujeme výpočtem \( A \Rightarrow B \), \( \neg A \), \( \neg A \wedge B \) a nakonec disjunkcí těchto dvou částí.

Tabulka pravdivosti:

\( \begin{array}{c|c|c|c|c|c} A & B & A \Rightarrow B & \neg A & \neg A \wedge B & (A \Rightarrow B) \vee (\neg A \wedge B) \\ \hline 0 & 0 & 1 & 1 & 0 & 1 \\ 0 & 1 & 1 & 1 & 1 & 1 \\ 1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 0 & 0 & 1 \\ \end{array} \)

Výraz není vždy pravdivý, tudíž se nejedná o tautologii.

Řešení příkladu:

Nejprve spočítáme \( A \vee B \), poté \( \neg C \), jejich konjunkci, následně \( A \Rightarrow C \) a nakonec celkovou implikaci.

Tabulka pravdivosti:

\( \begin{array}{c|c|c|c|c|c|c|c} A & B & C & A \vee B & \neg C & (A \vee B) \wedge \neg C & A \Rightarrow C & ((A \vee B) \wedge \neg C) \Rightarrow (A \Rightarrow C) \\ \hline 0 & 0 & 0 & 0 & 1 & 0 & 1 & 1 \\ 0 & 0 & 1 & 0 & 0 & 0 & 1 & 1 \\ 0 & 1 & 0 & 1 & 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 1 & 0 & 0 & 1 & 1 \\ 1 & 0 & 0 & 1 & 1 & 1 & 0 & 0 \\ 1 & 0 & 1 & 1 & 0 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 & 1 & 1 & 0 & 0 \\ 1 & 1 & 1 & 1 & 0 & 0 & 1 & 1 \\ \end{array} \)

Poslední sloupec není vždy \(1\), výraz tedy není tautologie.

Řešení příkladu:

Nejprve vyhodnotíme disjunkci \( A \vee B \), poté konjunkci \( A \wedge B \), a nakonec implikaci mezi nimi.

Tabulka pravdivosti:

\( \begin{array}{c|c|c|c|c} A & B & A \vee B & A \wedge B & (A \vee B) \Rightarrow (A \wedge B) \\ \hline 0 & 0 & 0 & 0 & 1 \\ 0 & 1 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 & 0 \\ 1 & 1 & 1 & 1 & 1 \\ \end{array} \)

Výraz není tautologií, protože poslední sloupec obsahuje nuly.

Řešení příkladu:

Vyhodnotíme nejprve \( \neg B \), poté \( A \wedge \neg B \), pak jeho negaci, dále \( C \wedge A \) a nakonec disjunkci obou složek.

Tabulka pravdivosti:

\( \begin{array}{c|c|c|c|c|c|c} A & B & C & \neg B & A \wedge \neg B & \neg(A \wedge \neg B) & C \wedge A & \neg(A \wedge \neg B) \vee (C \wedge A) \\ \hline 0 & 0 & 0 & 1 & 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 1 & 0 & 1 & 0 & 1 \\ 0 & 1 & 0 & 0 & 0 & 1 & 0 & 1 \\ 0 & 1 & 1 & 0 & 0 & 1 & 0 & 1 \\ 1 & 0 & 0 & 1 & 1 & 0 & 0 & 0 \\ 1 & 0 & 1 & 1 & 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 0 & 0 & 1 & 0 & 1 \\ 1 & 1 & 1 & 0 & 0 & 1 & 1 & 1 \\ \end{array} \)

Výraz není tautologií – obsahuje v posledním sloupci nulu.

Řešení příkladu:

Spočítáme \( A \wedge B \), \( \neg A \), \( \neg A \vee C \) a nakonec implikaci mezi první a třetí složkou.

Tabulka pravdivosti:

\( \begin{array}{c|c|c|c|c|c|c|c} A & B & C & A \wedge B & \neg A & \neg A \vee C & (A \wedge B) \Rightarrow (\neg A \vee C) \\ \hline 0 & 0 & 0 & 0 & 1 & 1 & 1 \\ 0 & 0 & 1 & 0 & 1 & 1 & 1 \\ 0 & 1 & 0 & 0 & 1 & 1 & 1 \\ 0 & 1 & 1 & 0 & 1 & 1 & 1 \\ 1 & 0 & 0 & 0 & 0 & 0 & 1 \\ 1 & 0 & 1 & 0 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 & 0 & 0 & 0 \\ 1 & 1 & 1 & 1 & 0 & 1 & 1 \\ \end{array} \)

Výraz není tautologií – poslední sloupec obsahuje nulu.

Řešení příkladu:

Spočítáme \( A \Rightarrow B \), jeho negaci, potom \( \neg B \), \( A \wedge \neg B \), a ekvivalenci mezi oběma stranami.

Tabulka pravdivosti:

\( \begin{array}{c|c|c|c|c|c|c} A & B & A \Rightarrow B & \neg(A \Rightarrow B) & \neg B & A \wedge \neg B & \neg(A \Rightarrow B) \Leftrightarrow (A \wedge \neg B) \\ \hline 0 & 0 & 1 & 0 & 1 & 0 & 1 \\ 0 & 1 & 1 & 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 0 & 0 & 0 & 1 \\ \end{array} \)

Výraz je tautologií – poslední sloupec obsahuje pouze jedničky.

Řešení příkladu:

Vyhodnotíme disjunkci \( A \vee B \), negaci \( \neg C \), jejich konjunkci, poté \( \neg B \), disjunkci \( A \vee \neg B \), a nakonec implikaci.

Tabulka pravdivosti:

\( \begin{array}{c|c|c|c|c|c|c|c|c} A & B & C & A \vee B & \neg C & (A \vee B) \wedge \neg C & \neg B & A \vee \neg B & \Rightarrow \\ \hline 0 & 0 & 0 & 0 & 1 & 0 & 1 & 1 & 1 \\ 0 & 0 & 1 & 0 & 0 & 0 & 1 & 1 & 1 \\ 0 & 1 & 0 & 1 & 1 & 1 & 0 & 0 & 0 \\ 0 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 0 & 1 & 1 & 0 & 0 & 1 & 1 & 1 \\ 1 & 1 & 0 & 1 & 1 & 1 & 0 & 1 & 1 \\ 1 & 1 & 1 & 1 & 0 & 0 & 0 & 1 & 1 \\ \end{array} \)

Výraz není tautologií – v tabulce je jedna nula.

Řešení příkladu:

Nejprve určíme \( A \vee B \) a \( A \wedge B \), poté jejich implikaci.

Tabulka pravdivosti:

\( \begin{array}{c|c|c|c|c} A & B & A \vee B & A \wedge B & (A \vee B) \Rightarrow (A \wedge B) \\ \hline 0 & 0 & 0 & 0 & 1 \\ 0 & 1 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 & 0 \\ 1 & 1 & 1 & 1 & 1 \\ \end{array} \)

Výraz není tautologií, protože obsahuje hodnoty 0.

Řešení příkladu:

Nejprve zjistíme \( A \Rightarrow B \), poté jeho negaci a výraz \( A \wedge \neg B \), nakonec jejich ekvivalenci.

Tabulka pravdivosti:

\( \begin{array}{c|c|c|c|c|c|c} A & B & A \Rightarrow B & \neg(A \Rightarrow B) & \neg B & A \wedge \neg B & \neg(A \Rightarrow B) \Leftrightarrow (A \wedge \neg B) \\ \hline 0 & 0 & 1 & 0 & 1 & 0 & 1 \\ 0 & 1 & 1 & 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 0 & 0 & 0 & 1 \\ \end{array} \)

Poslední sloupec je samé \(1\), takže se jedná o tautologii.

Řešení příkladu:

Spočítáme \( A \wedge B \), poté \( \neg A \), následně disjunkci \( \neg A \vee B \), a nakonec implikaci.

Tabulka pravdivosti:

\( \begin{array}{c|c|c|c|c|c} A & B & A \wedge B & \neg A & \neg A \vee B & (A \wedge B) \Rightarrow (\neg A \vee B) \\ \hline 0 & 0 & 0 & 1 & 1 & 1 \\ 0 & 1 & 0 & 1 & 1 & 1 \\ 1 & 0 & 0 & 0 & 0 & 1 \\ 1 & 1 & 1 & 0 & 1 & 1 \\ \end{array} \)

Výraz je tautologií, protože poslední sloupec obsahuje samé \(1\).

Řešení příkladu:

Nejprve spočítáme \( \neg B \), \( A \vee \neg B \), \( \neg A \), pak \( \neg A \Rightarrow B \), a nakonec ekvivalenci.

Tabulka pravdivosti:

\( \begin{array}{c|c|c|c|c|c|c} A & B & \neg B & A \vee \neg B & \neg A & \neg A \Rightarrow B & (A \vee \neg B) \Leftrightarrow (\neg A \Rightarrow B) \\ \hline 0 & 0 & 1 & 1 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 & 1 & 1 & 0 \\ 1 & 0 & 1 & 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 & 0 & 1 & 1 \\ \end{array} \)

Výraz není tautologií, protože obsahuje nuly v posledním sloupci.

Řešení příkladu:

Postupně spočítáme \( A \Leftrightarrow B \), disjunkce \( A \vee C \) a \( B \vee C \), jejich ekvivalenci, a nakonec celou implikaci.

Tabulka pravdivosti:

\( \begin{array}{c|c|c|c|c|c|c|c} A & B & C & A \Leftrightarrow B & A \vee C & B \vee C & (A \vee C) \Leftrightarrow (B \vee C) & \text{Celý výraz} \\ \hline 0 & 0 & 0 & 1 & 0 & 0 & 1 & 1 \\ 0 & 0 & 1 & 1 & 1 & 1 & 1 & 1 \\ 0 & 1 & 0 & 0 & 0 & 1 & 0 & 1 \\ 0 & 1 & 1 & 0 & 1 & 1 & 1 & 1 \\ 1 & 0 & 0 & 0 & 1 & 0 & 0 & 1 \\ 1 & 0 & 1 & 0 & 1 & 1 & 1 & 1 \\ 1 & 1 & 0 & 1 & 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ \end{array} \)

Poslední sloupec je vždy \(1\), což potvrzuje platnost této logické tautologie.

Řešení příkladu:

Nejprve určíme hodnoty výrazů \( \neg B \), \( A \wedge \neg B \) a \( B \vee C \), poté spočítáme implikaci.

Tabulka pravdivosti:

\( \begin{array}{c|c|c|c|c|c} A & B & C & \neg B & A \wedge \neg B & (A \wedge \neg B) \Rightarrow (B \vee C) \\ \hline 0 & 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 1 & 0 & 1 \\ 0 & 1 & 0 & 0 & 0 & 1 \\ 0 & 1 & 1 & 0 & 0 & 1 \\ 1 & 0 & 0 & 1 & 1 & 0 \\ 1 & 0 & 1 & 1 & 1 & 1 \\ 1 & 1 & 0 & 0 & 0 & 1 \\ 1 & 1 & 1 & 0 & 0 & 1 \\ \end{array} \)

Výraz není tautologií, protože v řádku \(5\) je hodnota \(0\).

Řešení příkladu:

Nejprve spočítáme \( A \vee B \), poté negaci \( \neg(A \vee B) \), následně \( \neg A \) a \( \neg B \) a jejich konjunkci, a nakonec ekvivalenci.

Tabulka pravdivosti:

\( \begin{array}{c|c|c|c|c|c|c} A & B & A \vee B & \neg(A \vee B) & \neg A & \neg B & (\neg A \wedge \neg B) \\ \hline 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 0 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 & 0 & 1 & 0 \\ 1 & 1 & 1 & 0 & 0 & 0 & 0 \\ \end{array} \)

Poslední dva sloupce jsou shodné, proto je výraz tautologií podle De Morganových zákonů.

Řešení příkladu:

Spočítáme hodnoty \( B \wedge C \), poté implikace \( A \Rightarrow (B \wedge C) \) a \( (B \wedge C) \Rightarrow A \), a nakonec jejich konjunkci.

Tabulka pravdivosti:

\( \begin{array}{c|c|c|c|c|c} A & B & C & B \wedge C & A \Rightarrow (B \wedge C) & (B \wedge C) \Rightarrow A & \text{Celý výraz} \\ \hline 0 & 0 & 0 & 0 & 1 & 1 & 1 \\ 0 & 0 & 1 & 0 & 1 & 1 & 1 \\ 0 & 1 & 0 & 0 & 1 & 1 & 1 \\ 0 & 1 & 1 & 1 & 0 & 1 & 0 \\ 1 & 0 & 0 & 0 & 0 & 1 & 0 \\ 1 & 0 & 1 & 0 & 0 & 1 & 0 \\ 1 & 1 & 0 & 0 & 0 & 1 & 0 \\ 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ \end{array} \)

Výraz není tautologií, protože jsou tam nuly v řádku \(4\) a v řádcích \(5–7\).

Řešení příkladu:

Spočítáme \( A \vee B \), \( \neg A \), \( \neg A \vee C \), jejich konjunkci a nakonec implikaci na \( B \vee C \).

Tabulka pravdivosti:

\( \begin{array}{c|c|c|c|c|c|c|c} A & B & C & A \vee B & \neg A & \neg A \vee C & (A \vee B) \wedge (\neg A \vee C) & B \vee C & \text{Celý výraz} \\ \hline 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 & 1 & 1 & 0 & 1 & 1 \\ 0 & 1 & 0 & 1 & 1 & 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 \\ 1 & 0 & 1 & 1 & 0 & 1 & 1 & 1 & 1 \\ 1 & 1 & 0 & 1 & 0 & 0 & 0 & 1 & 1 \\ 1 & 1 & 1 & 1 & 0 & 1 & 1 & 1 & 1 \\ \end{array} \)

Výraz je tautologií, protože implikace je vždy pravdivá.

Řešení příkladu:

Spočítáme \( B \Rightarrow C \), pak \( A \wedge (B \Rightarrow C) \), dále \( A \wedge B \), pak implikaci \( (A \wedge B) \Rightarrow C \), a nakonec ekvivalenci.

Tabulka pravdivosti:

\( \begin{array}{c|c|c|c|c|c|c|c} A & B & C & B \Rightarrow C & A \wedge (B \Rightarrow C) & A \wedge B & (A \wedge B) \Rightarrow C & \text{Celý výraz} \\ \hline 0 & 0 & 0 & 1 & 0 & 0 & 1 & 1 \\ 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 \\ 0 & 1 & 0 & 0 & 0 & 0 & 1 & 1 \\ 0 & 1 & 1 & 1 & 0 & 0 & 1 & 1 \\ 1 & 0 & 0 & 1 & 1 & 0 & 1 & 1 \\ 1 & 0 & 1 & 1 & 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 0 & 0 & 1 & 0 & 0 \\ 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ \end{array} \)

Výraz není tautologií, protože v řádku \(7\) má hodnotu \(0\).

Řešení příkladu:

Nejprve spočítáme hodnoty \( A \wedge B \), \( \neg A \), \( C \vee \neg A \), a nakonec implikaci \( (A \wedge B) \Rightarrow (C \vee \neg A) \).

Tabulka pravdivosti:

\( \begin{array}{c|c|c|c|c|c|c} A & B & C & A \wedge B & \neg A & C \vee \neg A & (A \wedge B) \Rightarrow (C \vee \neg A) \\ \hline 0 & 0 & 0 & 0 & 1 & 1 & 1 \\ 0 & 0 & 1 & 0 & 1 & 1 & 1 \\ 0 & 1 & 0 & 0 & 1 & 1 & 1 \\ 0 & 1 & 1 & 0 & 1 & 1 & 1 \\ 1 & 0 & 0 & 0 & 0 & 0 & 1 \\ 1 & 0 & 1 & 0 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 & 0 & 0 & 0 \\ 1 & 1 & 1 & 1 & 0 & 1 & 1 \\ \end{array} \)

Výraz není tautologií, protože v řádku \(7\) je hodnota \(0\) implikace.

Řešení příkladu:

Nejdříve spočítáme \( A \vee C \), pak jeho negaci \( \neg (A \vee C) \), dále \( \neg A \) a \( \neg C \), jejich konjunkci a porovnáme pravdivostní hodnoty.

Tabulka pravdivosti:

\( \begin{array}{c|c|c|c|c|c|c} A & B & C & A \vee C & \neg (A \vee C) & \neg A & \neg C & (\neg A \wedge \neg C) \\ \hline 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 1 & 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 0 & 1 & 1 & 0 & 1 & 0 & 0 \\ 0 & 1 & 1 & 1 & 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 1 & 0 & 0 & 1 & 0 \\ 1 & 1 & 0 & 1 & 0 & 0 & 1 & 0 \\ 1 & 0 & 1 & 1 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 \\ \end{array} \)

Poslední dva sloupce jsou shodné, proto výraz je tautologií podle De Morganova zákona.

Řešení příkladu:

Spočítáme jednotlivé implikace \( A \Rightarrow B \), \( C \Rightarrow A \), pak jejich konjunkci a nakonec implikaci na \( C \Rightarrow B \).

Tabulka pravdivosti:

\( \begin{array}{c|c|c|c|c|c|c|c} A & B & C & A \Rightarrow B & C \Rightarrow A & (A \Rightarrow B) \wedge (C \Rightarrow A) & C \Rightarrow B & \text{Celý výraz} \\ \hline 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 \\ 0 & 0 & 1 & 1 & 0 & 0 & 0 & 1 \\ 0 & 1 & 0 & 1 & 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 1 & 0 & 0 & 1 & 1 \\ 1 & 0 & 0 & 0 & 1 & 0 & 1 & 1 \\ 1 & 0 & 1 & 0 & 1 & 0 & 0 & 1 \\ 1 & 1 & 0 & 1 & 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ \end{array} \)

Výraz je tautologií, protože poslední sloupec je vždy \(1\).

Řešení příkladu:

Nejprve spočítáme hodnoty \( \neg B \), \( \neg C \), \( A \wedge \neg B \), \( B \wedge \neg C \), jejich disjunkci a nakonec implikaci na \( A \vee C \).

Tabulka pravdivosti:

\( \begin{array}{c|c|c|c|c|c|c|c|c} A & B & C & \neg B & \neg C & A \wedge \neg B & B \wedge \neg C & (A \wedge \neg B) \vee (B \wedge \neg C) & A \vee C & \text{Celý výraz} \\ \hline 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 1 & 1 \\ 0 & 1 & 0 & 0 & 1 & 0 & 1 & 1 & 0 & 0 \\ 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 1 \\ 1 & 0 & 0 & 1 & 1 & 1 & 0 & 1 & 1 & 1 \\ 1 & 0 & 1 & 1 & 0 & 1 & 0 & 1 & 1 & 1 \\ 1 & 1 & 0 & 0 & 1 & 0 & 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 1 \\ \end{array} \)

Výraz není tautologií, protože v řádku \(3\) má hodnotu \(0\).

Řešení příkladu:

Nejdříve spočítáme \( A \Rightarrow B \), jeho negaci \( \neg (A \Rightarrow B) \), dále \( \neg B \), a nakonec konjunkci \( A \wedge \neg B \).

Tabulka pravdivosti:

\( \begin{array}{c|c|c|c|c|c} A & B & A \Rightarrow B & \neg (A \Rightarrow B) & \neg B & A \wedge \neg B \\ \hline 0 & 0 & 1 & 0 & 1 & 0 \\ 0 & 1 & 1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 1 & 1 & 1 \\ 1 & 1 & 1 & 0 & 0 & 0 \\ \end{array} \)

Poslední dva sloupce jsou shodné, proto výraz je tautologií.

Řešení příkladu:

Nejprve spočítáme hodnoty \( A \wedge B \) a \( A \vee C \), poté vyhodnotíme implikaci.

Tabulka pravdivosti:

\( \begin{array}{c|c|c|c|c|c} A & B & C & A \wedge B & A \vee C & (A \wedge B) \Rightarrow (A \vee C) \\ \hline 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 & 1 & 1 \\ 0 & 1 & 0 & 0 & 0 & 1 \\ 0 & 1 & 1 & 0 & 1 & 1 \\ 1 & 0 & 0 & 0 & 1 & 1 \\ 1 & 0 & 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 & 1 & 1 \\ \end{array} \)

Výraz je tautologií, protože implikace je pravdivá ve všech řádcích.

Řešení příkladu:

Nejdříve spočítáme \( A \vee B \), \( \neg C \), konjunkci \( (A \vee B) \wedge \neg C \), pak hodnoty \( B \wedge \neg C \) a nakonec disjunkci \( A \vee (B \wedge \neg C) \). Nakonec ověříme implikaci.

Tabulka pravdivosti:

\( \begin{array}{c|c|c|c|c|c|c|c} A & B & C & A \vee B & \neg C & (A \vee B) \wedge \neg C & B \wedge \neg C & A \vee (B \wedge \neg C) \\ \hline 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 & 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 1 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 1 & 1 & 1 & 0 & 1 \\ 1 & 0 & 1 & 1 & 0 & 0 & 0 & 1 \\ 1 & 1 & 0 & 1 & 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 & 0 & 0 & 0 & 1 \\ \end{array} \)

Poslední sloupec implikace (viz níže) je vždy \(1\), proto výraz je tautologií.

Pro úplnost spočítáme implikaci:

\( \begin{array}{c|c} \text{Antecedent} & \text{Konsekvent} & \text{Implikace} \\ \hline 0 & 0 & 1 \\ 0 & 0 & 1 \\ 1 & 1 & 1 \\ 0 & 0 & 1 \\ 1 & 1 & 1 \\ 0 & 1 & 1 \\ 1 & 1 & 1 \\ 0 & 1 & 1 \\ \end{array} \)

Řešení příkladu:

Nejdříve spočítáme \( A \wedge B \), jeho negaci \( \neg (A \wedge B) \), hodnotu implikace \( B \Rightarrow C \) a nakonec disjunkci těchto dvou výrazů.

Tabulka pravdivosti:

\( \begin{array}{c|c|c|c|c|c|c} A & B & C & A \wedge B & \neg (A \wedge B) & B \Rightarrow C & \neg (A \wedge B) \vee (B \Rightarrow C) \\ \hline 0 & 0 & 0 & 0 & 1 & 1 & 1 \\ 0 & 0 & 1 & 0 & 1 & 1 & 1 \\ 0 & 1 & 0 & 0 & 1 & 0 & 1 \\ 0 & 1 & 1 & 0 & 1 & 1 & 1 \\ 1 & 0 & 0 & 0 & 1 & 1 & 1 \\ 1 & 0 & 1 & 0 & 1 & 1 & 1 \\ 1 & 1 & 0 & 1 & 0 & 0 & 0 \\ 1 & 1 & 1 & 1 & 0 & 1 & 1 \\ \end{array} \)

Výraz není tautologií, protože v řádku \(7\) má hodnotu \(0\).

Řešení příkladu:

Nejprve spočítáme \( \neg B \), disjunkci \( A \vee \neg B \), implikaci \( B \Rightarrow A \) a nakonec jejich konjunkci.

Tabulka pravdivosti:

\( \begin{array}{c|c|c|c|c|c|c} A & B & C & \neg B & A \vee \neg B & B \Rightarrow A & (A \vee \neg B) \wedge (B \Rightarrow A) \\ \hline 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 0 & 1 & 1 & 1 & 1 & 1 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 1 & 1 & 1 & 1 \\ 1 & 0 & 1 & 1 & 1 & 1 & 1 \\ 1 & 1 & 0 & 0 & 1 & 1 & 1 \\ 1 & 1 & 1 & 0 & 1 & 1 & 1 \\ \end{array} \)

Výraz není tautologií, protože v řádcích \(3\) a \(4\) je hodnota \(0\).

Řešení příkladu:

Nejprve spočítáme implikaci \( A \Rightarrow (B \wedge C) \), poté \( A \Rightarrow B \) a \( A \Rightarrow C \), jejich konjunkci a nakonec celkovou implikaci.

Tabulka pravdivosti:

\( \begin{array}{c|c|c|c|c|c|c|c|c} A & B & C & B \wedge C & A \Rightarrow (B \wedge C) & A \Rightarrow B & A \Rightarrow C & (A \Rightarrow B) \wedge (A \Rightarrow C) & \text{Celkový výraz} \\ \hline 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 \\ 0 & 0 & 1 & 0 & 1 & 1 & 1 & 1 & 1 \\ 0 & 1 & 0 & 0 & 1 & 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 1 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 1 \\ 1 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 1 \\ 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ \end{array} \)

Výraz je tautologií, protože ve všech případech je hodnota \(1\).

Řešení příkladu:

Nejdříve spočítáme \( \neg A \) a \( \neg B \), poté jednotlivé konjunkce \( A \wedge \neg B \) a \( B \wedge \neg A \), nakonec jejich disjunkci.

Tabulka pravdivosti:

\( \begin{array}{c|c|c|c|c|c|c|c} A & B & C & \neg A & \neg B & A \wedge \neg B & B \wedge \neg A & (A \wedge \neg B) \vee (B \wedge \neg A) \\ \hline 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 & 0 & 1 & 1 \\ 1 & 0 & 0 & 0 & 1 & 1 & 0 & 1 \\ 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 1 & 1 & 0 & 0 & 0 \\ 0 & 1 & 1 & 1 & 0 & 0 & 1 & 1 \\ 1 & 0 & 1 & 0 & 1 & 1 & 0 & 1 \\ 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 \\ \end{array} \)

Výraz reprezentuje exkluzivní nebo (\(XOR\)), hodnota je \(1\) právě tehdy, když jsou \( A \) a \( B \) rozdílné.

Řešení příkladu:

Nejprve spočítáme implikace \( A \Rightarrow B \) a \( B \Rightarrow C \), pak jejich disjunkci.

Tabulka pravdivosti:

\( \begin{array}{c|c|c|c|c|c} A & B & C & A \Rightarrow B & B \Rightarrow C & (A \Rightarrow B) \vee (B \Rightarrow C) \\ \hline 0 & 0 & 0 & 1 & 1 & 1 \\ 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 1 & 0 & 1 & 0 & 1 \\ 0 & 1 & 1 & 1 & 1 & 1 \\ 1 & 0 & 0 & 0 & 1 & 1 \\ 1 & 0 & 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 & 0 & 1 \\ 1 & 1 & 1 & 1 & 1 & 1 \\ \end{array} \)

Výraz není tautologií, protože je pravdivý ve všech případech kromě řádku \(5\) a \(7\), kde jedna z implikací je nepravdivá, ale jejich disjunkce je stále pravdivá.

Řešení příkladu:

Nejdříve spočítáme disjunkci \( A \vee B \), její negaci \( \neg (A \vee B) \), negace \( \neg A \) a \( \neg B \), jejich konjunkci a nakonec implikaci.

Tabulka pravdivosti:

\( \begin{array}{c|c|c|c|c|c|c|c|c} A & B & C & A \vee B & \neg (A \vee B) & \neg A & \neg B & \neg A \wedge \neg B & \neg (A \vee B) \Rightarrow (\neg A \wedge \neg B) \\ \hline 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 \\ 0 & 0 & 1 & 0 & 1 & 1 & 1 & 1 & 1 \\ 0 & 1 & 0 & 1 & 0 & 1 & 0 & 0 & 1 \\ 0 & 1 & 1 & 1 & 0 & 1 & 0 & 0 & 1 \\ 1 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 1 & 0 & 0 & 1 & 0 & 1 \\ 1 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 1 \\ 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 1 \\ \end{array} \)

Výraz je tautologií, protože implikace je pravdivá ve všech řádcích.

Řešení příkladu:

Nejdříve spočítáme konjunkce \( A \wedge B \) a \( C \wedge \neg B \), poté jejich disjunkci.

Tabulka pravdivosti:

\( \begin{array}{c|c|c|c|c|c|c} A & B & C & \neg B & A \wedge B & C \wedge \neg B & (A \wedge B) \vee (C \wedge \neg B) \\ \hline 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 1 & 0 & 1 & 1 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 1 & 0 & 0 & 0 \\ 1 & 0 & 1 & 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 0 & 1 & 0 & 1 \\ 1 & 1 & 1 & 0 & 1 & 0 & 1 \\ \end{array} \)

Řešení příkladu:

Nejprve spočítáme disjunkce \( A \vee B \), \( B \vee C \), jejich konjunkci a nakonec implikaci na \( A \vee C \).

Tabulka pravdivosti:

\( \begin{array}{c|c|c|c|c|c|c|c} A & B & C & A \vee B & B \vee C & (A \vee B) \wedge (B \vee C) & A \vee C & \big((A \vee B) \wedge (B \vee C)\big) \Rightarrow (A \vee C) \\ \hline 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 & 1 & 0 & 1 & 1 \\ 0 & 1 & 0 & 1 & 1 & 1 & 0 & 0 \\ 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 0 & 0 & 1 & 0 & 0 & 1 & 1 \\ 1 & 0 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 1 & 0 & 1 & 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ \end{array} \)

Výraz není tautologií, protože v řádku \(3\) implikace neplatí.

Řešení příkladu:

Nejdříve spočítáme jednotlivé části \( B \Rightarrow C \), potom konjunkci \( A \wedge (B \Rightarrow C) \) a nakonec implikaci na \( A \wedge C \).

Tabulka pravdivosti:

\( \begin{array}{c|c|c|c|c|c|c} A & B & C & B \Rightarrow C & A \wedge (B \Rightarrow C) & A \wedge C & \big(A \wedge (B \Rightarrow C)\big) \Rightarrow (A \wedge C) \\ \hline 0 & 0 & 0 & 1 & 0 & 0 & 1 \\ 0 & 0 & 1 & 1 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 & 0 & 0 & 1 \\ 0 & 1 & 1 & 1 & 0 & 0 & 1 \\ 1 & 0 & 0 & 1 & 1 & 0 & 0 \\ 1 & 0 & 1 & 1 & 1 & 1 & 1 \\ 1 & 1 & 0 & 0 & 0 & 0 & 1 \\ 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ \end{array} \)

Vidíme, že poslední sloupec není vždy \(1\), což znamená, že výraz není tautologií. Konkrétně řádek \(5\) vyjadřuje situaci, kdy implikace neplatí.

Řešení příkladu:

Nejprve spočítáme \( A \Rightarrow C \), \( B \Rightarrow C \), jejich konjunkci a také disjunkci \( A \vee B \), nakonec implikaci \( (A \vee B) \Rightarrow ((A \Rightarrow C) \wedge (B \Rightarrow C)) \).

Tabulka pravdivosti:

\( \begin{array}{c|c|c|c|c|c|c|c} A & B & C & A \Rightarrow C & B \Rightarrow C & (A \Rightarrow C) \wedge (B \Rightarrow C) & A \vee B & (A \vee B) \Rightarrow ((A \Rightarrow C) \wedge (B \Rightarrow C)) \\ \hline 0 & 0 & 0 & 1 & 1 & 1 & 0 & 1 \\ 0 & 0 & 1 & 1 & 1 & 1 & 0 & 1 \\ 0 & 1 & 0 & 1 & 0 & 0 & 1 & 0 \\ 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 0 & 0 & 0 & 1 & 0 & 1 & 0 \\ 1 & 0 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 1 & 0 & 0 & 0 & 0 & 1 & 0 \\ 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ \end{array} \)

Výraz není tautologií, protože v řádcích \(3 , 5\) a \(7\) je implikace nepravdivá.

Řešení příkladu:

Nejdříve spočítáme \( A \wedge B \), pak negaci \( \neg (A \wedge B) \), dále \( \neg A \) a \( \neg B \), jejich disjunkci a nakonec zkoumáme ekvivalenci.

Tabulka pravdivosti:

\( \begin{array}{c|c|c|c|c|c|c|c} A & B & A \wedge B & \neg (A \wedge B) & \neg A & \neg B & \neg A \vee \neg B & \neg (A \wedge B) \Leftrightarrow (\neg A \vee \neg B) \\ \hline 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 \\ 0 & 1 & 0 & 1 & 1 & 0 & 1 & 1 \\ 1 & 0 & 0 & 1 & 0 & 1 & 1 & 1 \\ 1 & 1 & 1 & 0 & 0 & 0 & 0 & 1 \\ \end{array} \)

Tento výraz je tautologií, známý jako De Morganův zákon.

Řešení příkladu:

Nejdříve vypočítáme \( A \Rightarrow B \), \( \neg B \Rightarrow \neg A \) a poté celkovou implikaci.

Tabulka pravdivosti:

\( \begin{array}{c|c|c|c|c|c} A & B & A \Rightarrow B & \neg B & \neg A & \neg B \Rightarrow \neg A \\ \hline 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 0 & 1 & 1 \\ 1 & 0 & 0 & 1 & 0 & 0 \\ 1 & 1 & 1 & 0 & 0 & 1 \\ \end{array} \)

Doplňme poslední sloupec:

\( \begin{array}{c|c|c|c|c|c|c} A & B & A \Rightarrow B & \neg B \Rightarrow \neg A & (A \Rightarrow B) \Rightarrow (\neg B \Rightarrow \neg A) \\ \hline 0 & 0 & 1 & 1 & 1 \\ 0 & 1 & 1 & 1 & 1 \\ 1 & 0 & 0 & 0 & 1 \\ 1 & 1 & 1 & 1 & 1 \\ \end{array} \)

Výraz je tautologií, což potvrzuje zákon kontrapozice.

Řešení příkladu:

Nejdříve spočítáme \( A \vee B \), \( A \wedge B \), pak negaci \( \neg (A \wedge B) \) a nakonec jejich konjunkci.

Tabulka pravdivosti:

\( \begin{array}{c|c|c|c|c|c} A & B & A \vee B & A \wedge B & \neg (A \wedge B) & (A \vee B) \wedge \neg (A \wedge B) \\ \hline 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 1 & 1 & 0 & 1 & 1 \\ 1 & 0 & 1 & 0 & 1 & 1 \\ 1 & 1 & 1 & 1 & 0 & 0 \\ \end{array} \)

Tento výraz je tzv. exkluzivní disjunkce (\(XOR\)) mezi \( A \) a \( B \).

Řešení příkladu:

Nejdříve spočítáme \( B \wedge C \), pak \( A \Rightarrow (B \wedge C) \), dále \( A \Rightarrow B \), \( A \Rightarrow C \) a jejich konjunkci, nakonec ekvivalenci.

Tabulka pravdivosti:

\( \begin{array}{c|c|c|c|c|c|c|c|c} A & B & C & B \wedge C & A \Rightarrow (B \wedge C) & A \Rightarrow B & A \Rightarrow C & (A \Rightarrow B) \wedge (A \Rightarrow C) & \Leftrightarrow \\ \hline 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 \\ 0 & 0 & 1 & 0 & 1 & 1 & 1 & 1 & 1 \\ 0 & 1 & 0 & 0 & 1 & 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 1 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ \end{array} \)

Výraz není tautologií, protože v některých řádcích (\(5, 6, 7\)) ekvivalence neplatí.

Řešení příkladu:

Nejdříve spočítáme \( A \vee B \), pak negaci \( \neg (A \vee B) \), dále negace \( \neg A \), \( \neg B \), jejich konjunkci a nakonec ekvivalenci.

Tabulka pravdivosti:

\( \begin{array}{c|c|c|c|c|c|c|c} A & B & A \vee B & \neg (A \vee B) & \neg A & \neg B & \neg A \wedge \neg B & \neg (A \vee B) \Leftrightarrow (\neg A \wedge \neg B) \\ \hline 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 0 & 1 & 0 & 0 & 1 \\ 1 & 0 & 1 & 0 & 0 & 1 & 0 & 1 \\ 1 & 1 & 1 & 0 & 0 & 0 & 0 & 1 \\ \end{array} \)

Výraz je tautologií, což je druhý De Morganův zákon.

Řešení příkladu:

Nejprve spočítáme \( A \Rightarrow B \), \( B \Rightarrow A \), jejich konjunkci a nakonec ekvivalenci s \( A \Leftrightarrow B \).

Tabulka pravdivosti:

\( \begin{array}{c|c|c|c|c|c|c} A & B & A \Rightarrow B & B \Rightarrow A & (A \Rightarrow B) \wedge (B \Rightarrow A) & A \Leftrightarrow B & \Leftrightarrow \\ \hline 0 & 0 & 1 & 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 1 & 0 & 0 & 1 \\ 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ \end{array} \)

Výraz je tautologií, protože obě strany vyjadřují totéž.

Řešení příkladu:

Nejprve spočítáme \( A \wedge B \), \( A \vee B \) a nakonec implikaci.

Tabulka pravdivosti:

\( \begin{array}{c|c|c|c|c} A & B & A \wedge B & A \vee B & (A \wedge B) \Rightarrow (A \vee B) \\ \hline 0 & 0 & 0 & 0 & 1 \\ 0 & 1 & 0 & 1 & 1 \\ 1 & 0 & 0 & 1 & 1 \\ 1 & 1 & 1 & 1 & 1 \\ \end{array} \)

Výraz je tautologií, protože pokud platí \( A \wedge B \), pak jistě platí i \( A \vee B \).

Řešení příkladu:

Nejprve rozebereme jednotlivé části výrazu:

\( A \wedge \neg B \) je pravda pouze tehdy, když \( A = 1 \) a \( B = 0 \).

Poté spočítáme implikaci \( (A \wedge \neg B) \Rightarrow C \), která je nepravdivá jen pokud je \( A \wedge \neg B = 1 \) a \( C = 0 \), jinak je pravdivá.

Dále spočítáme pravdivost výrazu \( B \vee C \), tedy disjunkce \( B \) a \( C \).

Nakonec spočítáme implikaci \( A \Rightarrow (B \vee C) \), která je nepravdivá pouze, když \( A = 1 \) a \( B \vee C = 0 \).

Tabulka pravdivosti:

\( \begin{array}{c|c|c|c|c|c|c|c|c} A & B & C & \neg B & A \wedge \neg B & (A \wedge \neg B) \Rightarrow C & B \vee C & A \Rightarrow (B \vee C) & \big((A \wedge \neg B) \Rightarrow C\big) \Rightarrow \big(A \Rightarrow (B \vee C)\big) \\ \hline 0 & 0 & 0 & 1 & 0 & 1 & 0 & 1 & 1 \\ 0 & 0 & 1 & 1 & 0 & 1 & 1 & 1 & 1 \\ 0 & 1 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 0 & 0 & 1 & 1 & 1 & 1 \\ 1 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 1 \\ 1 & 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 1 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 0 & 0 & 1 & 1 & 1 & 1 \\ \end{array} \)

Poslední sloupec ukazuje pravdivost celého složeného výroku. Vidíme, že výraz je tautologie (vždy pravdivý).