Gesetze von De Morgan Beispiele
Beispiel:
Wir zeigen, dass der Satz vom Widerspruch gilt
\(\qquad\) | \(\lnot (\alpha \land \lnot \alpha)\iff \mathrm{w}\) |
Wir bilden die folgende Kette an logischen Äquivalenzen
\(\qquad\) | \((\lnot (\alpha \land \lnot \alpha))\) | \(\enspace \iff \enspace\) | \((\lnot \alpha \lor \lnot (\lnot \alpha))\) | \(\qquad\) | Gesetz von De Morgan \((\lnot(\mu\land \nu))\iff(\lnot\mu\lor \lnot \nu)\) mit \(\mu=\alpha\), \(\nu=\lnot \alpha\) |
\(\enspace \iff \enspace\) | \((\lnot \alpha \lor \alpha)\) | ||||
\(\enspace \iff \enspace\) | \((\alpha \lor \lnot \alpha)\) | ||||
\(\enspace \iff \enspace\) | \(\mathrm{w}\) |
Beispiel:
Wir zeigen, dass die folgende komplexe Aussage eine Tautologie ist
\(\qquad\) | \(((A \lor \lnot(B \land A)) \land (C \lor (D\lor C))) \iff (C\lor D)\) |
Wir bilden die folgende Kette an logischen Äquivalenzen
\(\qquad\) | \(((A \lor \underbrace{\lnot(B \land A)}_{\textsf{Gesetz von De Morgan}}) \land (C \lor \underbrace{(D\lor C)}_{\textsf{Kommutativgesetz}})) \iff\) |
\(\qquad\) | \(((A \lor \underbrace{(\lnot B \lor \lnot A)}_{\textsf{Kommutativgesetz}}) \land \underbrace{(C \lor (C\lor D)}_{\textsf{Assoziativgesetz}})) \iff \) |
\(\qquad\) | \((\underbrace{(A \lor (\lnot A \lor \lnot B))}_{\textsf{Assoziativgesetz}} \land (\underbrace{(C \lor C) }_{\textsf{Idempotenzgesetz}}\lor D)) \iff \) |
\(\qquad\) | \((\underbrace{(A \lor \lnot A) }_{\substack{\textsf{Satz vom ausge-}\\\textsf{schlossenen Dritten}}}\lor \lnot B)) \land (C\lor D)) \iff \) |
\(\qquad\) | \((\underbrace{(\mathrm{w} \lor \lnot B)}_{\textsf{Dominanzgesetz}} \land (C\lor D)) \iff \) |
\(\qquad\) | \(\underbrace{(\mathrm{w}\land (C\lor D)}_{\textsf{Neutralitätsgesetz}} ) \iff (C \lor D)\) |
Beweis mit Wahrheitstabellen
Wir zerlegen zuerst die komplexe Aussage in einzelne Formeln:
\(\qquad\) | \(\alpha = (A \lor \lnot(B \land A))\) |
\(\qquad\) | \(\beta = (C \lor (D \lor C))\) |
Nun bilden wir die Wahrheitstabelle für \(\alpha\):
\(\qquad\) | \(\begin{array}{|c|c|c|c|c|c|c|c|} \hline A & B & \hspace{-0.8em} & B \land A & \lnot (B \land A) & A \lor \lnot (B \land A)\ \\\hline \mathrm{w} & \mathrm{w} & \hspace{-0.8em} & \mathrm{w} & \mathrm{f} & \mathrm{w}\ \\\hline \mathrm{w} & \mathrm{f} & \hspace{-0.8em} & \mathrm{f} & \mathrm{w} & \mathrm{w}\ \\\hline \mathrm{f} & \mathrm{w} & \hspace{-0.8em} & \mathrm{f} & \mathrm{w} & \mathrm{w}\ \\\hline \mathrm{f} & \mathrm{f} & \hspace{-0.8em} & \mathrm{f} & \mathrm{w} & \mathrm{w}\ \\\hline\end{array}\) |
Wir bilden die Wahrheitstabelle für \(\beta\):
\(\qquad\) | \(\begin{array}{|c|c|c|c|c|c|c|c|} \hline C & D & \hspace{-0.8em} & D \lor C & C \lor (D \lor C)\ \\\hline \mathrm{w} & \mathrm{w} & \hspace{-0.8em} & \mathrm{w} & \mathrm{w} \ \\\hline \mathrm{w} & \mathrm{f} & \hspace{-0.8em} & \mathrm{w} & \mathrm{w} \ \\\hline \mathrm{f} & \mathrm{w} & \hspace{-0.8em} & \mathrm{w} & \mathrm{w} \ \\\hline \mathrm{f} & \mathrm{f} & \hspace{-0.8em} & \mathrm{f} & \mathrm{f} \ \\\hline\end{array}\) |
Nun bilden wir die Wahrheitstabelle für \(\alpha \land \beta\) und \(C \lor D\):
\(\qquad\) | \(\begin{array}{|c|c|c|c|c|c|c|c|} \hline A & B & C & D & \hspace{-0.8em} & \alpha & \beta & \alpha \land \beta & C \lor D\ \\\hline \mathrm{w} & \mathrm{w} & \mathrm{w}& \mathrm{w} & \hspace{-0.8em} & \mathrm{w} & \mathrm{w}& \mathrm{w}& \mathrm{w} \ \\\hline \mathrm{w} & \mathrm{w} & \mathrm{w}& \mathrm{f} & \hspace{-0.8em} & \mathrm{w} & \mathrm{w}& \mathrm{w} & \mathrm{w}\ \\\hline \mathrm{w} & \mathrm{w} & \mathrm{f}& \mathrm{w} & \hspace{-0.8em} & \mathrm{w} & \mathrm{w}& \mathrm{w}& \mathrm{w} \ \\\hline \mathrm{w} & \mathrm{w} & \mathrm{f}& \mathrm{f} & \hspace{-0.8em} & \mathrm{w} & \mathrm{w}& \mathrm{f} & \mathrm{f}\ \\\hline \mathrm{w} & \mathrm{f} & \mathrm{w}& \mathrm{w} & \hspace{-0.8em} & \mathrm{w} & \mathrm{w}& \mathrm{w} & \mathrm{w}\ \\\hline \mathrm{w} & \mathrm{f} & \mathrm{w}& \mathrm{f} & \hspace{-0.8em} & \mathrm{w} & \mathrm{w}& \mathrm{w} & \mathrm{w}\ \\\hline \mathrm{w} & \mathrm{f} & \mathrm{f}& \mathrm{w} & \hspace{-0.8em} & \mathrm{w} & \mathrm{w}& \mathrm{w} & \mathrm{w}\ \\\hline \mathrm{w} & \mathrm{f} & \mathrm{f}& \mathrm{f} & \hspace{-0.8em} & \mathrm{w} & \mathrm{w}& \mathrm{f} & \mathrm{f}\ \\\hline \mathrm{f} & \mathrm{w} & \mathrm{w}& \mathrm{w} & \hspace{-0.8em} & \mathrm{w} & \mathrm{w}& \mathrm{w} & \mathrm{w}\ \\\hline \mathrm{f} & \mathrm{w} & \mathrm{w}& \mathrm{f} & \hspace{-0.8em} & \mathrm{w} & \mathrm{w}& \mathrm{w} & \mathrm{w}\ \\\hline \mathrm{f} & \mathrm{w} & \mathrm{f}& \mathrm{w} & \hspace{-0.8em} & \mathrm{w} & \mathrm{w}& \mathrm{w} & \mathrm{w}\ \\\hline \mathrm{f} & \mathrm{w} & \mathrm{f}& \mathrm{f} & \hspace{-0.8em} & \mathrm{w} & \mathrm{w}& \mathrm{f} & \mathrm{f}\ \\\hline \mathrm{f} & \mathrm{f} & \mathrm{w}& \mathrm{w} & \hspace{-0.8em} & \mathrm{w} & \mathrm{w}& \mathrm{w} & \mathrm{w}\ \\\hline \mathrm{f} & \mathrm{f} & \mathrm{w}& \mathrm{f} & \hspace{-0.8em} & \mathrm{w} & \mathrm{w}& \mathrm{w} & \mathrm{w}\ \\\hline \mathrm{f} & \mathrm{f} & \mathrm{f}& \mathrm{w} & \hspace{-0.8em} & \mathrm{w} & \mathrm{w}& \mathrm{w} & \mathrm{w}\ \\\hline \mathrm{f} & \mathrm{f} & \mathrm{f}& \mathrm{f} & \hspace{-0.8em} & \mathrm{w} & \mathrm{w}& \mathrm{f} & \mathrm{f}\ \\\hline\end{array}\) |
Wir sehen, dass die letzten beiden Spalten die gleichen Wahrheitswerte aufweisen, d.h. dass die linke Seite und die rechte Seite unserer komplexen Aussage logisch äquivalent sind. Die Aussage ist also eine Tautologie.
Erklärung Lösung:
Erläuterung: Die Lösung dieser Aufgabe ergibt sich durch Anwendung der Regeln von De Morgan. Diese besagen, dass für zwei Formeln \(\alpha\) und \(\beta\) die folgenden Äquivalenzen Tautologien sind:
Wir formen nun mit Hilfe dieser Regeln die gegebenen Formeln auf der rechten Seite um.
|  |
\(\enspace\)