Logické rovnosti a ekvivalence

Řešení příkladu 1:

Pro ověření ekvivalence výrazu \( p \wedge q \) a \( \neg p \vee \neg q \) sestavíme pravdivostní tabulku:

Porovnáním sloupců \( p \wedge q \) a \( \neg p \vee \neg q \) vidíme, že nejsou stejné (např. řádek poslední, kde \( p \wedge q = 1 \), ale \( \neg p \vee \neg q = 0 \)). Výrazy tedy nejsou ekvivalentní.

Navíc, pomocí De Morganových zákonů známe vztah: \( \neg (p \wedge q) = \neg p \vee \neg q \), což je negace prvního výrazu. To potvrzuje, že \( p \wedge q \not\equiv \neg p \vee \neg q \), ale platí \( \neg (p \wedge q) \equiv \neg p \vee \neg q \).

Řešení příkladu 2:

Nejprve definujme implikaci: \( p \Rightarrow q \) je nepravdivá pouze v případě, že \( p=1 \) a \( q=0 \), jinak je pravdivá.

Sloupce \( p \Rightarrow q \) a \( \neg p \vee q \) jsou shodné, tedy platí ekvivalence \( p \Rightarrow q \equiv \neg p \vee q \).

Řešení příkladu 3:

Využijeme definici implikace a negace:

Sloupce \( \neg (p \Rightarrow q) \) a \( p \wedge \neg q \) jsou stejné, tedy platí \( \neg (p \Rightarrow q) \equiv p \wedge \neg q \).

Řešení příkladu 4:

Provedeme pravdivostní tabulku:

Porovnáním sloupců \( (p \vee q) \Rightarrow r \) a \( (p \Rightarrow r) \wedge (q \Rightarrow r) \) vidíme, že nejsou stejné (např. řádek 3: první je 0, druhý je 0, ale řádek 5: první 0, druhý 0, ale řádek 7: první 0, druhý 0). Všechny odpovídají stejně, proto jsou tyto výrazy ekvivalentní.

Řešení příkladu 5:

Pravdivostní tabulka:

Porovnáním sloupců \( p \wedge (q \vee r) \) a \( (p \wedge q) \vee (p \wedge r) \) vidíme, že jsou shodné, tedy platí distributivní zákon.

Řešení příkladu:

Sestavíme pravdivostní tabulku pro oba výrazy:

\[ \begin{array}{c|c|c|c|c} p & q & p \wedge q & \neg (p \wedge q) & \neg p \vee \neg q \\ \hline 0 & 0 & 0 & 1 & 1 \\ 0 & 1 & 0 & 1 & 1 \\ 1 & 0 & 0 & 1 & 1 \\ 1 & 1 & 1 & 0 & 0 \\ \end{array} \]

Porovnáním sloupců \(\neg (p \wedge q)\) a \(\neg p \vee \neg q\) vidíme, že jsou shodné pro všechny možné hodnoty \(p\) a \(q\), tedy výrazy jsou ekvivalentní.

Řešení příkladu:

Sestavíme pravdivostní tabulku:

\[ \begin{array}{c|c|c|c|c} p & q & p \vee q & \neg (p \vee q) & \neg p \wedge \neg q \\ \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 (p \vee q)\) a \(\neg p \wedge \neg q\) jsou shodné pro všechny řádky, takže jsou ekvivalentní.

Řešení příkladu:

Sestavíme pravdivostní tabulku:

\[ \begin{array}{c|c|c|c|c|c|c} p & q & r & q \vee r & p \wedge (q \vee r) & p \wedge q & p \wedge r & (p \wedge q) \vee (p \wedge r) \\ \hline 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 1 & 1 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 1 & 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 & 1 & 1 & 0 & 1 \\ 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ \end{array} \]

Sloupce \(p \wedge (q \vee r)\) a \((p \wedge q) \vee (p \wedge r)\) jsou shodné, takže výrazy jsou ekvivalentní.

Řešení příkladu:

Sestavíme pravdivostní tabulku:

\[ \begin{array}{c|c|c|c|c|c|c|c} p & q & r & q \wedge r & p \vee (q \wedge r) & p \vee q & p \vee r & (p \vee q) \wedge (p \vee r) \\ \hline 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 1 & 0 & 1 & 0 & 1 & 1 & 1 & 1 \\ 1 & 1 & 0 & 0 & 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ \end{array} \]

Vidíme, že ve 2. a 3. řádku se hodnoty liší, proto výrazy nejsou ekvivalentní.

Řešení příkladu:

Pravdivostní tabulka:

\[ \begin{array}{c|c|c|c} p & q & p \vee q & p \wedge (p \vee q) \\ \hline 0 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 \\ 1 & 0 & 1 & 1 \\ 1 & 1 & 1 & 1 \\ \end{array} \]

Sloupec \(p \wedge (p \vee q)\) se shoduje se sloupcem \(p\), výrazy jsou tedy ekvivalentní.

Řešení příkladu:

Pravdivostní tabulka:

\[ \begin{array}{c|c|c|c} p & q & p \wedge q & p \vee (p \wedge q) \\ \hline 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 1 \\ 1 & 1 & 1 & 1 \\ \end{array} \]

Sloupec \(p \vee (p \wedge q)\) se shoduje se sloupcem \(p\), proto jsou výrazy ekvivalentní.

Řešení příkladu:

Pravdivostní tabulka:

\[ \begin{array}{c|c|c|c|c} p & q & p \rightarrow q & \neg p & \neg p \vee q \\ \hline 0 & 0 & 1 & 1 & 1 \\ 0 & 1 & 1 & 1 & 1 \\ 1 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 0 & 1 \\ \end{array} \]

Sloupce \(p \rightarrow q\) a \(\neg p \vee q\) jsou stejné, výrazy jsou ekvivalentní.

Řešení příkladu:

Pravdivostní tabulka:

\[ \begin{array}{c|c|c|c|c|c} p & q & p \leftrightarrow q & p \wedge q & \neg p & \neg p \wedge \neg q & (p \wedge q) \vee (\neg p \wedge \neg q) \\ \hline 0 & 0 & 1 & 0 & 1 & 1 & 1 \\ 0 & 1 & 0 & 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 1 & 0 & 0 & 1 \\ \end{array} \]

Sloupce \(p \leftrightarrow q\) a \((p \wedge q) \vee (\neg p \wedge \neg q)\) jsou stejné, tedy výrazy jsou ekvivalentní.

Řešení příkladu:

Pravdivostní tabulka:

\[ \begin{array}{c|c|c|c|c|c|c} p & q & p \leftrightarrow q & \neg (p \leftrightarrow q) & \neg q & p \wedge \neg q & \neg p & \neg p \wedge q & (p \wedge \neg q) \vee (\neg p \wedge q) \\ \hline 0 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 & 0 & 1 & 1 & 1 \\ 1 & 0 & 0 & 1 & 1 & 1 & 0 & 0 & 1 \\ 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ \end{array} \]

Sloupce \(\neg (p \leftrightarrow q)\) a \((p \wedge \neg q) \vee (\neg p \wedge q)\) jsou totožné, proto jsou výrazy ekvivalentní.

Řešení příkladu:

Pravdivostní tabulka pro všechny výrazy:

\[ \begin{array}{c|c|c|c|c|c|c} p & q & r & p \rightarrow q & q \rightarrow r & (p \rightarrow q) \wedge (q \rightarrow r) & p \rightarrow r \\ \hline 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 0 & 1 & 1 & 1 & 1 & 1 \\ 0 & 1 & 0 & 1 & 0 & 0 & 1 \\ 0 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 0 & 0 & 0 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 & 1 & 0 & 1 \\ 1 & 1 & 0 & 1 & 0 & 0 & 0 \\ 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ \end{array} \]

Vidíme, že vždy, když je výraz \((p \rightarrow q) \wedge (q \rightarrow r)\) pravdivý (tedy 1), je také \(p \rightarrow r\) pravdivý. Proto platí implikace \((p \rightarrow q) \wedge (q \rightarrow r) \Rightarrow (p \rightarrow r)\).

Řešení příkladu:

Pravdivostní tabulka pro oba výrazy:

\[ \begin{array}{c|c|c|c|c|c} p & q & p \wedge q & \neg (p \wedge q) & \neg p & \neg q & \neg p \vee \neg q \\ \hline 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 1 & 0 & 1 & 1 & 0 & 1 \\ 1 & 0 & 0 & 1 & 0 & 1 & 1 \\ 1 & 1 & 1 & 0 & 0 & 0 & 0 \\ \end{array} \]

Sloupce \(\neg (p \wedge q)\) a \(\neg p \vee \neg q\) jsou stejné, tedy platí ekvivalence.

Řešení příkladu:

Pravdivostní tabulka:

\[ \begin{array}{c|c|c|c|c|c} p & q & p \vee q & \neg (p \vee q) & \neg p & \neg q & \neg p \wedge \neg q \\ \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} \]

Sloupce \(\neg (p \vee q)\) a \(\neg p \wedge \neg q\) jsou stejné, proto platí ekvivalence.

Řešení příkladu:

Vytvoříme pravdivostní tabulku:

\[ \begin{array}{c|c|c|c|c} p & q & p \rightarrow q & p \wedge (p \rightarrow q) & q \\ \hline 0 & 0 & 1 & 0 & 0 \\ 0 & 1 & 1 & 0 & 1 \\ 1 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 1 & 1 \\ \end{array} \]

Vidíme, že vždy, když je \(p \wedge (p \rightarrow q)\) pravdivé, pak je i \(q\) pravdivé, proto platí implikace.

Řešení příkladu:

Pravdivostní tabulka:

\[ \begin{array}{c|c|c|c|c|c} p & q & p \vee q & \neg p & (p \vee q) \wedge \neg p & q \\ \hline 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 1 & 1 & 1 & 1 & 1 \\ 1 & 0 & 1 & 0 & 0 & 0 \\ 1 & 1 & 1 & 0 & 0 & 1 \\ \end{array} \]

Vidíme, že vždy, když je \((p \vee q) \wedge \neg p\) pravdivé, je \(q\) pravdivé, proto implikace platí.

Řešení příkladu:

Pravdivostní tabulka:

\[ \begin{array}{c|c|c|c|c|c} p & q & p \rightarrow q & \neg q & \neg p & \neg q \rightarrow \neg p \\ \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} \]

Sloupce \(p \rightarrow q\) a \(\neg q \rightarrow \neg p\) jsou shodné, proto jsou výrazy ekvivalentní.

Řešení příkladu:

Pravdivostní tabulka pro všechny výrazy:

\[ \begin{array}{c|c|c|c|c|c|c|c} p & q & r & q \wedge r & p \vee (q \wedge r) & p \vee q & p \vee r & (p \vee q) \wedge (p \vee r) \\ \hline 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 1 & 0 & 1 & 0 & 1 & 1 & 1 & 1 \\ 1 & 1 & 0 & 0 & 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ \end{array} \]

Sloupce \(p \vee (q \wedge r)\) a \((p \vee q) \wedge (p \vee r)\) jsou totožné, tedy výrazy jsou ekvivalentní.

Řešení příkladu:

Pravdivostní tabulka:

\[ \begin{array}{c|c|c|c|c|c|c|c} p & q & r & q \vee r & p \wedge (q \vee r) & p \wedge q & p \wedge r & (p \wedge q) \vee (p \wedge r) \\ \hline 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 1 & 1 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 1 & 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 & 1 & 1 & 0 & 1 \\ 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ \end{array} \]

Sloupce \(p \wedge (q \vee r)\) a \((p \wedge q) \vee (p \wedge r)\) jsou stejné, výrazy jsou ekvivalentní.

Řešení příkladu:

Pravdivostní tabulka:

\[ \begin{array}{c|c|c|c|c|c} p & q & p \rightarrow q & \neg (p \rightarrow q) & \neg q & p \wedge \neg q \\ \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} \]

Sloupce \(\neg (p \rightarrow q)\) a \(p \wedge \neg q\) jsou stejné, proto platí ekvivalence.

Řešení příkladu:

Pravdivostní tabulka:

\[ \begin{array}{c|c|c|c|c} p & q & p \leftrightarrow q & p \rightarrow q & (p \leftrightarrow q) \Rightarrow (p \rightarrow q) \\ \hline 0 & 0 & 1 & 1 & 1 \\ 0 & 1 & 0 & 1 & 1 \\ 1 & 0 & 0 & 0 & 1 \\ 1 & 1 & 1 & 1 & 1 \\ \end{array} \]

Ve všech řádcích, kde je \(p \leftrightarrow q\) pravdivé, je i \(p \rightarrow q\) pravdivé, proto implikace platí.

Řešení příkladu:

Pro ověření ekvivalence těchto výrazů vytvoříme pravdivostní tabulku pro proměnné \(p\), \(q\), a \(r\). Výrazy jsou:

\(A = p \land (q \lor r)\)

\(B = (p \land q) \lor (p \land r)\)

Tabulka:

Sloupce pro \(A\) i \(B\) se shodují pro všechny kombinace hodnot \(p, q, r\), tedy:

\(p \land (q \lor r) \equiv (p \land q) \lor (p \land r)\)

Řešení příkladu:

Tento vztah je známý jako De Morganův zákon. Vytvoříme pravdivostní tabulku pro \(p\) a \(q\):

Vidíme, že sloupce \(¬(p ∧ q)\) a \(¬p ∨ ¬q\) jsou totožné, proto:

\(\neg (p \land q) \equiv \neg p \lor \neg q\)

Řešení příkladu:

Logický výraz \( (p \lor q) \Rightarrow (q \lor p) \) je implikace. Zjistíme, zda je tato implikace tautologií (pravdivá ve všech případech):

Implikace je ve všech případech pravdivá (logická rovnost), protože disjunkce je komutativní:

\((p \lor q) \Rightarrow (q \lor p)\) je tautologie.

Řešení příkladu:

Vytvoříme pravdivostní tabulku pro proměnné \(p, q\):

Sloupce \(p ⇒ q\) a \(¬q ⇒ ¬p\) jsou shodné, proto platí:

\(p \Rightarrow q \equiv \neg q \Rightarrow \neg p\)

Řešení příkladu:

Vytvoříme pravdivostní tabulku:

Výsledný sloupec \( (p ∧ q) ∨ (p ∧ ¬q) \) se rovná hodnotám \(p\), tedy platí ekvivalence:

\((p \land q) \lor (p \land \neg q) \equiv p\)

Řešení příkladu:

Porovnáme oba výrazy pomocí pravdivostní tabulky:

Vidíme, že pro \(p=0, q=0, r=1\) je \(p ∨ (q ∧ r) = 0\), ale \((p ∨ q) ∧ (p ∨ r) = 0\). Pro \(p=0, q=1, r=0\) také hodnoty nejsou stejné.

Tedy neplatí ekvivalence:

\(p \lor (q \land r) \not\equiv (p \lor q) \land (p \lor r)\)

Řešení příkladu:

Vyjdeme z pravdivostních hodnot výrazů a porovnáme je:

\(A, B\) – pravdivostní hodnoty:

\[ \begin{array}{c|c|c|c|c|c} A & B & A \land B & \neg A & \neg B & \neg A \land \neg B \\ \hline 0 & 0 & 0 & 1 & 1 & 1 \\ 0 & 1 & 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 & 1 & 0 \\ 1 & 1 & 1 & 0 & 0 & 0 \\ \end{array} \]

Vypočítáme \((A \land B) \lor (\neg A \land \neg B)\):

\[ \begin{array}{c|c|c|c} A & B & (A \land B) \lor (\neg A \land \neg B) & A \leftrightarrow B \\ \hline 0 & 0 & 1 & 1 \\ 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 \\ 1 & 1 & 1 & 1 \\ \end{array} \]

Vidíme, že obě strany mají stejné pravdivostní hodnoty pro všechny možné kombinace \(A, B\), tedy:

\((A \land B) \lor (\neg A \land \neg B) \equiv A \leftrightarrow B\) je pravdivá ekvivalence.

Řešení příkladu:

Pro ověření použijeme De Morganovy zákony a pravdivostní tabulku:

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

Vypočítáme \(\neg A \land \neg B\):

\[ \begin{array}{c|c|c} A & B & \neg A \land \neg B \\ \hline 0 & 0 & 1 \\ 0 & 1 & 0 \\ 1 & 0 & 0 \\ 1 & 1 & 0 \\ \end{array} \]

Vidíme, že \(\neg (A \lor B)\) i \(\neg A \land \neg B\) mají stejné pravdivostní hodnoty pro všechny případy, tedy platí rovnost:

\(\neg (A \lor B) \equiv \neg A \land \neg B\).

Řešení příkladu:

Opět využijeme De Morganovy zákony a pravdivostní tabulku:

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

Vypočítáme \(\neg A \lor \neg B\):

\[ \begin{array}{c|c|c} A & B & \neg A \lor \neg B \\ \hline 0 & 0 & 1 \\ 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \\ \end{array} \]

Tabulka ukazuje, že \(\neg (A \land B)\) a \(\neg A \lor \neg B\) mají shodné hodnoty pro všechny kombinace, tedy rovnost platí:

\(\neg (A \land B) \equiv \neg A \lor \neg B\).

Řešení příkladu:

Vypočítáme obě strany pro všechny hodnoty \(A, B\):

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

\[ \begin{array}{c|c|c} A & B & A \land \neg B \\ \hline 0 & 0 & 0 \\ 0 & 1 & 0 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \\ \end{array} \]

Vidíme, že obě strany mají stejné pravdivostní hodnoty, tedy platí:

\((A \lor B) \land \neg B \equiv A \land \neg B\).

Řešení příkladu:

Pro všechny kombinace \(A, B\) spočítáme hodnoty výrazů:

\[ \begin{array}{c|c|c|c|c|c} A & B & \neg A & \neg B & A \leftrightarrow B & \neg A \leftrightarrow \neg B \\ \hline 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 1 & 0 & 0 \\ 1 & 1 & 0 & 0 & 1 & 1 \\ \end{array} \]

Protože hodnoty jsou shodné pro všechny případy, platí rovnost:

\((A \leftrightarrow B) \equiv (\neg A \leftrightarrow \neg B)\).

Řešení příkladu:

Připomeňme, že implikace \(X \to Y\) je ekvivalentní \(\neg X \lor Y\). Spočítáme hodnoty:

\[ \begin{array}{c|c|c|c|c} A & B & A \to B & \neg B & \neg B \to \neg A \\ \hline 0 & 0 & 1 & 1 & 1 \\ 0 & 1 & 1 & 0 & 1 \\ 1 & 0 & 0 & 1 & 0 \\ 1 & 1 & 1 & 0 & 1 \\ \end{array} \]

Vidíme, že \(A \to B\) i \(\neg B \to \neg A\) mají shodné pravdivostní hodnoty, tedy:

\((A \to B) \equiv (\neg B \to \neg A)\).

Řešení příkladu:

Pomocí pravdivostní tabulky zkontrolujeme všechny možné kombinace \(A, B, C\):

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

Hodnoty obou výrazů jsou vždy shodné, tedy platí:

\((A \lor (B \land C)) \equiv ((A \lor B) \land (A \lor C))\).

Řešení příkladu:

Sestavíme tabulku hodnot:

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

Hodnoty sloupce \(\neg (A \leftrightarrow B)\) a \(A \leftrightarrow \neg B\) jsou shodné, tudíž platí:

\(\neg (A \leftrightarrow B) \equiv A \leftrightarrow \neg B\).

Řešení příkladu:

Sestavíme pravdivostní tabulku:

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

Obě strany mají stejné pravdivostní hodnoty, tedy platí:

\((A \land (B \lor C)) \equiv ((A \land B) \lor (A \land C))\).

Řešení příkladu:

Sestavíme pravdivostní tabulku:

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

Obě strany mají stejné pravdivostní hodnoty, tedy platí De Morganův zákon:

\((\neg (A \land B)) \equiv (\neg A \lor \neg B)\).

Řešení příkladu:

Sestavíme pravdivostní tabulku:

\[ \begin{array}{c|c|c|c|c} A & B & A \lor B & \neg (A \lor B) & \neg A \land \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} \]

Obě strany mají stejné pravdivostní hodnoty, tedy platí druhý De Morganův zákon:

\((\neg (A \lor B)) \equiv (\neg A \land \neg B)\).

Řešení příkladu:

Sestavíme pravdivostní tabulku implikace a její ekvivalence:

\[ \begin{array}{c|c|c|c} A & B & A \Rightarrow B & \neg A \lor B \\ \hline 0 & 0 & 1 & 1 \\ 0 & 1 & 1 & 1 \\ 1 & 0 & 0 & 0 \\ 1 & 1 & 1 & 1 \\ \end{array} \]

Obě strany mají stejné pravdivostní hodnoty, tedy platí:

\((A \Rightarrow B) \equiv (\neg A \lor B)\).

Řešení příkladu:

Sestavíme pravdivostní tabulku:

\[ \begin{array}{c|c|c|c} A & \neg A & A \land \neg A & \text{false} \\ \hline 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 \\ \end{array} \]

Výraz \(A \land \neg A\) je vždy nepravdivý, což odpovídá hodnotě \text{false}.

Tedy platí:

\((A \land \neg A) \equiv \text{false}\).

Řešení příkladu:

Sestavíme pravdivostní tabulku:

\[ \begin{array}{c|c|c|c} A & \neg A & A \lor \neg A & \text{true} \\ \hline 0 & 1 & 1 & 1 \\ 1 & 0 & 1 & 1 \\ \end{array} \]

Výraz \(A \lor \neg A\) je vždy pravdivý, což odpovídá hodnotě \text{true}.

Tedy platí:

\((A \lor \neg A) \equiv \text{true}\).

Řešení příkladu:

Sestavíme pravdivostní tabulku pro složený výraz:

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

Hodnoty výrazu \(((A \Rightarrow B) \land (B \Rightarrow C)) \Rightarrow (A \Rightarrow C)\) jsou ve všech případech 1 (pravda), tedy tato implikace je tautologie.

Řešení příkladu:

Sestavíme pravdivostní tabulku:

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

Obě strany nejsou shodné (např. řádek 2), tudíž neplatí:

\((A \lor (B \land C)) \not\equiv ((A \lor B) \land (A \lor C))\).

Řešení příkladu:

Sestavíme pravdivostní tabulku:

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

Obě strany mají stejné pravdivostní hodnoty, tedy platí distributivní zákon:

\((A \land (B \lor C)) \equiv ((A \land B) \lor (A \land C))\).

Řešení příkladu:

Ověříme asociativitu operace \(\lor\) pravdivostní tabulkou:

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

Obě strany jsou shodné, platí asociativita disjunkce:

\((A \lor (B \lor C)) \equiv ((A \lor B) \lor C)\).

Řešení příkladu:

Ověříme asociativitu operace \(\land\) pravdivostní tabulkou:

\[ \begin{array}{c|c|c|c|c|c} A & B & C & B \land C & A \land (B \land C) & (A \land B) \land C \\ \hline 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 1 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 1 & 1 & 1 \\ \end{array} \]

Obě strany mají stejné pravdivostní hodnoty, platí tedy asociativita konjunkce:

\((A \land (B \land C)) \equiv ((A \land B) \land C)\).

Řešení příkladu:

Sestavíme pravdivostní tabulku podle definic negace, disjunkce a konjunkce:

\[ \begin{array}{c|c|c|c|c|c} A & B & A \lor B & \neg (A \lor B) & \neg A & \neg B & \neg A \land \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} \]

Porovnáním sloupců \(\neg (A \lor B)\) a \(\neg A \land \neg B\) vidíme, že jsou stejné, tedy platí:

\((\neg (A \lor B)) \equiv (\neg A \land \neg B)\).

Řešení příkladu:

Sestavíme pravdivostní tabulku:

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

Sloupce \(\neg (A \land B)\) a \(\neg A \lor \neg B\) jsou shodné, tedy rovnost platí:

\((\neg (A \land B)) \equiv (\neg A \lor \neg B)\).

Řešení příkladu:

Sestavíme pravdivostní tabulku:

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

Sloupce \(A \lor (B \land C)\) a \((A \lor B) \land (A \lor C)\) jsou stejné, takže rovnost platí:

\((A \lor (B \land C)) \equiv ((A \lor B) \land (A \lor C))\).

Řešení příkladu:

Sestavíme pravdivostní tabulku implikace a její ekvivalence:

\[ \begin{array}{c|c|c|c|c} A & B & A \Rightarrow B & \neg A & \neg A \lor B \\ \hline 0 & 0 & 1 & 1 & 1 \\ 0 & 1 & 1 & 1 & 1 \\ 1 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 0 & 1 \\ \end{array} \]

Sloupce \(A \Rightarrow B\) a \(\neg A \lor B\) jsou shodné, tedy platí:

\((A \Rightarrow B) \equiv (\neg A \lor B)\).

Řešení příkladu:

Sestavíme pravdivostní tabulku:

\[ \begin{array}{c|c|c|c|c|c|c|c} A & B & A \Rightarrow B & B \Rightarrow A & (A \Rightarrow B) \land (B \Rightarrow A) & A \Leftrightarrow B \\ \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} \]

Sloupce \((A \Rightarrow B) \land (B \Rightarrow A)\) a \(A \Leftrightarrow B\) jsou totožné, rovnost tedy platí.

Řešení příkladu:

Pro \(A=0\) i \(A=1\) je výraz \(A \lor \neg A\) pravdivý:

\[ \begin{array}{c|c|c|c} A & \neg A & A \lor \neg A & \top \\ \hline 0 & 1 & 1 & 1 \\ 1 & 0 & 1 & 1 \\ \end{array} \]

Tedy platí tautologie \((A \lor \neg A) \equiv \top\).

Řešení příkladu:

Pro všechny hodnoty \(A\) platí, že \(A \land \neg A\) je nepravdivý:

\[ \begin{array}{c|c|c|c} A & \neg A & A \land \neg A & \bot \\ \hline 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 \\ \end{array} \]

Tedy výraz je vždy nepravdivý, tedy \((A \land \neg A) \equiv \bot\).

Řešení příkladu:

Sestavíme pravdivostní tabulku:

\[ \begin{array}{c|c|c} A & \neg A & \neg \neg A \\ \hline 0 & 1 & 0 \\ 1 & 0 & 1 \\ \end{array} \]

Sloupce \(A\) a \(\neg \neg A\) jsou shodné, tedy platí:

\((\neg \neg A) \equiv A\).

Řešení příkladu:

Sestavíme pravdivostní tabulku:

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

Sloupce \((A \lor B)\) a \(\neg (\neg A \land \neg B)\) jsou stejné, tedy rovnost platí.

Řešení příkladu:

Prověříme De Morganův zákon pomocí pravdivostní tabulky:

Vidíme, že sloupce \(\neg (p \lor q)\) a \(\neg p \land \neg q\) jsou shodné ve všech řádcích, tedy platí:

\((\neg (p \lor q)) \equiv (\neg p \land \neg q)\).

Řešení příkladu:

Sestavíme pravdivostní tabulku:

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

Porovnáním hodnot vidíme, že obě strany mají stejné pravdivostní hodnoty pro všechny kombinace proměnných, tedy platí:

\((A \lor (B \land C)) \equiv ((A \lor B) \land (A \lor C))\).

Řešení příkladu:

Sestavíme pravdivostní tabulku podle De Morganova zákona:

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

Vidíme, že sloupce \(\neg (A \land B)\) a \(\neg A \lor \neg B\) jsou shodné, což potvrzuje platnost rovnosti:

\((\neg (A \land B)) \equiv (\neg A \lor \neg B)\).

Řešení příkladu:

Sestavíme pravdivostní tabulku podle druhého De Morganova zákona:

\[ \begin{array}{c|c|c|c|c} A & B & A \lor B & \neg (A \lor B) & \neg A \land \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} \]

Sloupce \(\neg (A \lor B)\) a \(\neg A \land \neg B\) jsou shodné, tudíž platí:

\((\neg (A \lor B)) \equiv (\neg A \land \neg B)\).

Řešení příkladu:

Nejprve připomeneme, že implikaci \(X \Rightarrow Y\) lze vyjádřit jako \(\neg X \lor Y\). Sestavíme pravdivostní tabulku:

\[ \begin{array}{c|c|c|c|c|c|c|c} A & B & C & A \Rightarrow B & B \Rightarrow C & (A \Rightarrow B) \land (B \Rightarrow C) & A \Rightarrow C & ((A \Rightarrow B) \land (B \Rightarrow C)) \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} \]

V posledním sloupci je hodnota vždy 1, tedy daná rovnost (implikace) platí pro všechny vstupy.

Řešení příkladu:

Sestavíme pravdivostní tabulku:

\[ \begin{array}{c|c|c|c} A & \neg A & A \land \neg A & 0 \\ \hline 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 \\ \end{array} \]

Vidíme, že výraz \(A \land \neg A\) je vždy 0 (nepravda), což je rovno 0. Rovnost tedy platí.

Řešení příkladu:

Sestavíme pravdivostní tabulku:

\[ \begin{array}{c|c|c|c} A & \neg A & A \lor \neg A & 1 \\ \hline 0 & 1 & 1 & 1 \\ 1 & 0 & 1 & 1 \\ \end{array} \]

Výraz \(A \lor \neg A\) je vždy pravda, tedy rovný 1. Rovnost tedy platí.

Řešení příkladu:

Sestavíme pravdivostní tabulku pro implikaci a pro její ekvivalentní výraz:

\[ \begin{array}{c|c|c|c|c} A & B & A \Rightarrow B & \neg A & \neg A \lor B \\ \hline 0 & 0 & 1 & 1 & 1 \\ 0 & 1 & 1 & 1 & 1 \\ 1 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 0 & 1 \\ \end{array} \]

Sloupce \(A \Rightarrow B\) a \(\neg A \lor B\) jsou shodné, rovnost tedy platí.

Řešení příkladu:

Sestavíme pravdivostní tabulku:

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

Sloupec \(A \land (A \lor B)\) je shodný se sloupcem \(A\), rovnost tedy platí.

Řešení příkladu:

Sestavíme pravdivostní tabulku:

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

Sloupec \(A \lor (A \land B)\) odpovídá sloupci \(A\), rovnost tedy platí.

Řešení příkladu:

Sestavíme pravdivostní tabulku podle distributivního zákona:

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

Obě strany mají stejné pravdivostní hodnoty, tedy rovnost platí.

Řešení příkladu:

Nejprve si připravíme pravdivostní tabulku pro jednotlivé výrazy.

Nechť \(p\) a \(q\) jsou logické proměnné, pak:

\[ \begin{array}{c|c|c|c|c|c} p & q & p \Rightarrow q & \neg q & \neg p & \neg q \Rightarrow \neg p \\ \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} \]

Porovnáním sloupců \(p \Rightarrow q\) a \(\neg q \Rightarrow \neg p\) vidíme, že hodnoty jsou ve všech řádcích shodné. Tedy platí:

\[ (p \Rightarrow q) \equiv (\neg q \Rightarrow \neg p) \]

Tuto logickou rovnost nazýváme kontrapozice, která je vždy pravdivá.

Řešení příkladu:

Nejprve připravíme pravdivostní tabulku s proměnnými \(p, q\).

\[ \begin{array}{c|c|c|c|c|c} p & q & p \Rightarrow q & p \wedge (p \Rightarrow q) & p \wedge q \\ \hline 0 & 0 & 1 & 0 & 0 \\ 0 & 1 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 1 & 1 \\ \end{array} \]

Porovnáním sloupců \(p \wedge (p \Rightarrow q)\) a \(p \wedge q\) vidíme, že odpovídají ve všech případech.

Tedy platí:

\[ (p \wedge (p \Rightarrow q)) \equiv (p \wedge q) \]

Což je logická rovnost potvrzující, že pokud platí \(p\) a zároveň \(p \Rightarrow q\), pak musí platit i \(q\).

Řešení příkladu:

Sestavme pravdivostní tabulku pro proměnné \(p, q, r\):

\[ \begin{array}{c|c|c|c|c|c|c|c} p & q & r & p \lor q & (p \lor q) \Rightarrow r & p \Rightarrow r & q \Rightarrow r & (p \Rightarrow r) \wedge (q \Rightarrow r) \\ \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} \]

Porovnáním sloupců \((p \lor q) \Rightarrow r\) a \((p \Rightarrow r) \wedge (q \Rightarrow r)\) vidíme, že jsou shodné ve všech řádcích.

Tedy platí:

\[ (p \lor q) \Rightarrow r \equiv (p \Rightarrow r) \wedge (q \Rightarrow r) \]

Tato rovnost vyjadřuje, že implikace z disjunkce je ekvivalentní spojení implikací.

Řešení příkladu:

Nejprve připravíme pravdivostní tabulku s proměnnými \(p, q\):

\[ \begin{array}{c|c|c|c|c} p & q & p \leftrightarrow q & \neg (p \leftrightarrow q) & p \oplus q \\ \hline 0 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 1 & 1 \\ 1 & 0 & 0 & 1 & 1 \\ 1 & 1 & 1 & 0 & 0 \\ \end{array} \]

Porovnáním sloupců \(\neg (p \leftrightarrow q)\) a \(p \oplus q\) vidíme, že odpovídají ve všech případech.

Tedy platí:

\[ \neg (p \leftrightarrow q) \equiv p \oplus q \]

Což znamená, že negace ekvivalence je exkluzivní OR.

Řešení příkladu:

Sestavme pravdivostní tabulku:

\[ \begin{array}{c|c|c|c|c|c} p & q & \neg q & \neg p & (p \wedge \neg q) & (\neg p \wedge q) \\ \hline 0 & 0 & 1 & 1 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 0 & 0 & 0 \\ \end{array} \]

Vyhodnotíme levý výraz \((p \wedge \neg q) \lor (\neg p \wedge q)\):

\[ \begin{array}{c|c} (p \wedge \neg q) & (\neg p \wedge q) \\ \hline 0 & 0 \\ 0 & 1 \\ 1 & 0 \\ 0 & 0 \\ \end{array} \quad \Rightarrow \quad \begin{array}{c} 0 \\ 1 \\ 1 \\ 0 \\ \end{array} \]

Porovnáním s hodnotami \(p \oplus q\) (0,1,1,0) vidíme shodu.

Tedy platí:

\[ (p \wedge \neg q) \lor (\neg p \wedge q) \equiv p \oplus q \]

Tento výraz je klasickou definicí exkluzivního OR.

Řešení příkladu:

Pravdivostní tabulka:

\[ \begin{array}{c|c|c|c|c} p & q & p \wedge q & \neg(p \wedge q) & \neg p \lor \neg q \\ \hline 0 & 0 & 0 & 1 & 1 \\ 0 & 1 & 0 & 1 & 1 \\ 1 & 0 & 0 & 1 & 1 \\ 1 & 1 & 1 & 0 & 0 \\ \end{array} \]

Sloupce \(\neg(p \wedge q)\) a \(\neg p \lor \neg q\) jsou shodné, tedy rovnost platí.

Tento zákon je jedním ze základních zákonů logiky.

Řešení příkladu:

Pravdivostní tabulka:

\[ \begin{array}{c|c|c|c|c} p & q & p \lor q & \neg(p \lor q) & \neg p \wedge \neg q \\ \hline 0 & 0 & 0 & 1 & 1 \\ 0 & 1 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 & 0 \\ 1 & 1 & 1 & 0 & 0 \\ \end{array} \]

Sloupce \(\neg(p \lor q)\) a \(\neg p \wedge \neg q\) jsou shodné, tedy rovnost platí.

Řešení příkladu:

Pravdivostní tabulka:

\[ \begin{array}{c|c|c|c|c} p & q & p \Rightarrow q & \neg p & \neg p \lor q \\ \hline 0 & 0 & 1 & 1 & 1 \\ 0 & 1 & 1 & 1 & 1 \\ 1 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 0 & 1 \\ \end{array} \]

Sloupce \(p \Rightarrow q\) a \(\neg p \lor q\) jsou shodné, tudíž rovnost platí.

Řešení příkladu:

Sestavme pravdivostní tabulku:

\[ \begin{array}{c|c|c|c|c|c} p & q & p \wedge q & \neg p & \neg q & \neg p \wedge \neg q \\ \hline 0 & 0 & 0 & 1 & 1 & 1 \\ 0 & 1 & 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 & 1 & 0 \\ 1 & 1 & 1 & 0 & 0 & 0 \\ \end{array} \]

Vyhodnotíme pravou stranu \((p \wedge q) \lor (\neg p \wedge \neg q)\):

\[ \begin{array}{c} 0 \lor 1 = 1 \\ 0 \lor 0 = 0 \\ 0 \lor 0 = 0 \\ 1 \lor 0 = 1 \\ \end{array} \]

Porovnáním se sloupcem \(p \leftrightarrow q\) (1,0,0,1) vidíme shodu, rovnost tedy platí.

Řešení příkladu:

Sestavíme pravdivostní tabulku:

\[ \begin{array}{c|c|c|c|c|c|c} p & q & p \lor q & \neg (p \lor q) & \neg p & \neg q & \neg p \land \neg q \\ \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} \]

Obě strany mají stejné pravdivostní hodnoty, tedy platí:

\((\neg (p \lor q)) \equiv (\neg p \land \neg q)\).

Řešení příkladu:

Sestavíme pravdivostní tabulku:

\[ \begin{array}{c|c|c|c|c|c|c} p & q & p \land q & \neg (p \land q) & \neg p & \neg q & \neg p \lor \neg q \\ \hline 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 1 & 0 & 1 & 1 & 0 & 1 \\ 1 & 0 & 0 & 1 & 0 & 1 & 1 \\ 1 & 1 & 1 & 0 & 0 & 0 & 0 \\ \end{array} \]

Obě strany mají stejné pravdivostní hodnoty, tedy platí:

\((\neg (p \land q)) \equiv (\neg p \lor \neg q)\).

Řešení příkladu:

Sestavíme pravdivostní tabulku:

\[ \begin{array}{c|c|c|c|c|c|c|c} p & q & r & q \land r & p \lor (q \land r) & p \lor q & p \lor r & (p \lor q) \land (p \lor r) \\ \hline 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 1 & 0 & 1 & 0 & 1 & 1 & 1 & 1 \\ 1 & 1 & 0 & 0 & 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ \end{array} \]

Obě strany mají stejné pravdivostní hodnoty, tedy platí:

\((p \lor (q \land r)) \equiv ((p \lor q) \land (p \lor r))\).

Řešení příkladu:

Sestavíme pravdivostní tabulku:

\[ \begin{array}{c|c|c|c|c|c|c|c} p & q & r & q \lor r & p \land (q \lor r) & p \land q & p \land r & (p \land q) \lor (p \land r) \\ \hline 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 1 & 1 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 1 & 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 & 1 & 1 & 0 & 1 \\ 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ \end{array} \]

Obě strany mají stejné pravdivostní hodnoty, tedy platí:

\((p \land (q \lor r)) \equiv ((p \land q) \lor (p \land r))\).

Řešení příkladu:

Sestavíme pravdivostní tabulku:

\[ \begin{array}{c|c|c|c|c|c} p & q & p \lor q & \neg p & (p \lor q) \land \neg p & q \land \neg p \\ \hline 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 1 & 1 & 1 & 1 & 1 \\ 1 & 0 & 1 & 0 & 0 & 0 \\ 1 & 1 & 1 & 0 & 0 & 0 \\ \end{array} \]

Obě strany mají stejné pravdivostní hodnoty, tedy platí:

\((p \lor q) \land \neg p \equiv q \land \neg p\).

Řešení příkladu:

Nejprve si připomeňme, že \(p \Rightarrow q \equiv \neg p \lor q\). Nyní sestavíme pravdivostní tabulku:

\[ \begin{array}{c|c|c|c|c} p & q & p \Rightarrow q & \neg (p \Rightarrow q) & p \land \neg q \\ \hline 0 & 0 & 1 & 0 & 0 \\ 0 & 1 & 1 & 0 & 0 \\ 1 & 0 & 0 & 1 & 1 \\ 1 & 1 & 1 & 0 & 0 \\ \end{array} \]

Obě strany mají stejné pravdivostní hodnoty, tedy platí:

\(\neg (p \Rightarrow q) \equiv p \land \neg q\).

Řešení příkladu:

Sestavíme pravdivostní tabulku:

\[ \begin{array}{c|c|c|c} p & q & \neg p & \neg p \lor q \\ \hline 0 & 0 & 1 & 1 \\ 0 & 1 & 1 & 1 \\ 1 & 0 & 0 & 0 \\ 1 & 1 & 0 & 1 \\ \end{array} \]

Protože implikace \(p \Rightarrow q\) je definována právě jako \(\neg p \lor q\), jsou obě strany ekvivalentní:

\((p \Rightarrow q) \equiv (\neg p \lor q)\).

Řešení příkladu:

Nejprve si připomeňme, že \(p \Leftrightarrow q\) znamená, že \(p\) a \(q\) mají stejnou pravdivostní hodnotu. Dále platí \(p \Rightarrow q \equiv \neg p \lor q\) a \(q \Rightarrow p \equiv \neg q \lor p\).

Sestavíme pravdivostní tabulku:

\[ \begin{array}{c|c|c|c|c|c|c|c} p & q & p \Rightarrow q & q \Rightarrow p & (p \Rightarrow q) \land (q \Rightarrow p) & p \Leftrightarrow q \\ \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} \]

Obě strany mají stejné pravdivostní hodnoty, tedy platí:

\((p \Leftrightarrow q) \equiv ((p \Rightarrow q) \land (q \Rightarrow p))\).

Řešení příkladu:

Připomeňme si, že \(p \oplus q\) je pravda, když \(p\) a \(q\) mají různé pravdivostní hodnoty, a \(p \Leftrightarrow q\) je pravda, když mají stejné pravdivostní hodnoty.

Sestavíme pravdivostní tabulku:

\[ \begin{array}{c|c|c|c} p & q & p \oplus q & \neg (p \oplus q) \\ \hline 0 & 0 & 0 & 1 \\ 0 & 1 & 1 & 0 \\ 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 1 \\ \end{array} \]

Tabulka pro \(p \Leftrightarrow q\):

\[ \begin{array}{c|c|c} p & q & p \Leftrightarrow q \\ \hline 0 & 0 & 1 \\ 0 & 1 & 0 \\ 1 & 0 & 0 \\ 1 & 1 & 1 \\ \end{array} \]

Proto platí:

\(\neg (p \oplus q) \equiv (p \Leftrightarrow q)\).

Řešení příkladu:

Výraz \(p \land \neg p\) je pravdivý pouze pokud je současně pravdivé \(p\) i jeho negace \(\neg p\), což není možné.

Sestavíme pravdivostní tabulku:

\[ \begin{array}{c|c|c} p & \neg p & p \land \neg p \\ \hline 0 & 1 & 0 \\ 1 & 0 & 0 \\ \end{array} \]

Proto vždy platí \(p \land \neg p = 0\), tedy výraz je nepravdivý (false).

Tedy:

\((p \land \neg p) \equiv \text{false}\).

Řešení příkladu:

Výraz \(p \lor \neg p\) je pravdivý vždy, protože alespoň jedna z hodnot \(p\) nebo \(\neg p\) musí být pravdivá.

Sestavíme pravdivostní tabulku:

\[ \begin{array}{c|c|c} p & \neg p & p \lor \neg p \\ \hline 0 & 1 & 1 \\ 1 & 0 & 1 \\ \end{array} \]

Výraz je tedy vždy pravdivý (true), tedy platí:

\((p \lor \neg p) \equiv \text{true}\).