Distributivgesetze für Implikationen Absorptionsgesetze
Die Absorptionsgesetze besagen, dass eine Teilaussage einer zusammengesetzten Aussage absorbiert wird, d.h. die Belegung mit Wahrheitswerten für diese Aussage hat in der komplexen Aussage keine Auswirkung. Die Teilaussage ist in diesem Zusammenhang also überflüssig.
Absorptionsgesetze:
Für die Formeln \(\alpha\) und \(\beta\) gelten die folgenden Tautologien:
- \((\alpha \lor (\alpha \land \beta)) \iff \alpha\enspace\) ist eine Tautologie
- \((\alpha \land (\alpha \lor \beta)) \iff \alpha\enspace\) ist eine Tautologie
Beweise
Beweis des 1. Absorptionsgesetzes:
Wir beweisen:
\(\qquad\) | \((\alpha \lor (\alpha \land \beta)) \iff \alpha\enspace\) ist eine Tautologie |
Wir bilden die Wahrheitstabelle:
\(\qquad\) | \(\begin{array}{|c|c|c|c|c|c|c|c|} \hline \alpha & \beta & \hspace{-0.8em} & \alpha \land \beta & \alpha \lor (\alpha \land \beta) & (\alpha \lor (\alpha \land \beta)) \iff \alpha\ \\ \hline \mathrm{w} & \mathrm{w} & \hspace{-0.8em} & \mathrm{w} & \mathrm{w} & \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{f} & \mathrm{w}\ \\ \hline \mathrm{f} & \mathrm{f} & \hspace{-0.8em} & \mathrm{f} & \mathrm{f} & \mathrm{w}\ \\ \hline\end{array}\) |
Die Aussage ist eine Tautologie.
Beweis des 2. Absorptionsgesetzes:
Wir beweisen:
\(\qquad\) | \((\alpha \land (\alpha \lor \beta)) \iff \alpha\enspace\) ist eine Tautologie |
Wir bilden die Wahrheitstabelle:
\(\qquad\) | \(\begin{array}{|c|c|c|c|c|c|c|c|} \hline \alpha & \beta & \hspace{-0.8em} & \alpha \lor \beta & \alpha \land (\alpha \lor \beta) & (\alpha \land (\alpha \lor \beta)) \iff \alpha\ \\ \hline \mathrm{w} & \mathrm{w} & \hspace{-0.8em} & \mathrm{w} & \mathrm{w} & \mathrm{w}\ \\ \hline \mathrm{w} & \mathrm{f} & \hspace{-0.8em} & \mathrm{w} & \mathrm{w} & \mathrm{w}\ \\ \hline \mathrm{f} & \mathrm{w} & \hspace{-0.8em} & \mathrm{w} & \mathrm{f} & \mathrm{w}\ \\ \hline \mathrm{f} & \mathrm{f} & \hspace{-0.8em} & \mathrm{f} & \mathrm{f} & \mathrm{w}\ \\ \hline\end{array}\) |
Die Aussage ist eine Tautologie.
Beispiel:
Wir beweisen in diesem Beispiel das 1. Absorptionsgesetz
\(\qquad\) | \((\alpha \lor (\alpha \land \beta)) \iff \alpha\enspace\) ist eine Tautologie |
auf eine alternative Art durch Anwendung logischer Gesetze.
Wir beginnen mit der linken Seite und bilden die folgende Kette an logischen Äquivalenzen
\(\qquad\) | \((\alpha \lor (\alpha \land \beta))\) | \(\enspace \iff \enspace\) | \(((\alpha \land \mathrm{w})\lor (\alpha \land \beta))\) | \(\qquad\) | |
\(\enspace \iff \enspace\) | \(((\mathrm{w} \land \alpha)\lor (\beta \land \alpha ))\) | Kommutativgesetz \((\mu\land \nu)\iff(\nu \land \mu)\) einmal mit \(\mu=\alpha\), \(\nu=\mathrm{w}\) einmal mit \(\mu=\alpha\), \(\nu=\beta\) | |||
\(\enspace \iff \enspace\) | \(((\mathrm{w} \lor \beta)\land \alpha)\) | Distributivgesetz \(((\mu\lor \nu)\land \gamma)\iff ((\mu \land \gamma)\lor (\nu \land \gamma))\) mit \(\mu=\mathrm{w}\), \(\nu=\beta\), \(\gamma=\alpha\) | |||
\(\enspace \iff \enspace\) | \(((\beta \lor \mathrm{w} )\land \alpha)\) | ||||
\(\enspace \iff \enspace\) | \((\mathrm{w} \land \alpha)\) | ||||
\(\enspace \iff \enspace\) | \((\alpha \land \mathrm{w} )\) | ||||
\(\enspace \iff \enspace\) | \(\alpha\) |
Wir haben also gezeigt, dass man das 1. Absorptionsgesetz aus anderen Gesetzen herleiten kann.
Erklärung Lösung: Die Vereinfachung von \(\left((A\implies B)\land \lnot B \right)\lor \left(A\implies B\right)\) lautet \(A\implies B\). Erläuterung: Betrachten wir die gegebene komplexe Aussage
genauer, so sehen wir, dass sie von der Form
mit den Formeln \(\alpha= (A\implies B)\) und \(\beta =\lnot B\) ist. Für Formeln dieser Art besagt das Absorptionsgesetz, dass
eine Tautologie ist. Ersetzen wir nun wieder die Formeln \(\alpha\) und \(\beta\) durch \((A\implies B)\) bzw. \(\lnot B\), so erhalten wir:
Nun lässt sich die rechte Seite \(A\implies B\) nicht weiter vereinfachen, sodass es sich dabei um die vollständige Vereinfachung von \(\left((A\implies B)\land \lnot B \right)\lor \left(A\implies B\right)\) handelt. Dass die anderen Aussagen nicht äquivalent zu \(\left((A\implies B)\land \lnot B \right)\lor \left(A\implies B\right)\) sind, kann man leicht sehen, wenn man sich die Wahrheitstabellen der Aussagen anschaut. Nur die Aussage \(A \implies B\) führt zu den gleichen Wahrheitswertkombinationen wie die Aussage \(\left((A\implies B)\land \lnot B \right)\lor \left(A\implies B\right)\). Beide Aussagen sind also logisch äquivalent. Wahrheitstabelle zu \(\left((A\implies B)\land \lnot B \right)\lor \left(A\implies B\right)\) Wir erstellen die Wahrheitstabelle für die Aussage \(\left((A\implies B)\land \lnot B \right)\lor \left(A\implies B\right)\):
Wahrheitstabelle zu \(A \implies B\) Wir erstellen die Wahrheitstabelle für die Aussage \(A \implies B\):
Wahrheitstabelle zu \(A \land \lnot B\) Wir erstellen die Wahrheitstabelle für die Aussage \(A \land \lnot B\):
Wahrheitstabelle zu \(\lnot B \lor (A \implies B)\) Wir erstellen die Wahrheitstabelle für die Aussage \(\lnot B \lor (A \implies B)\):
Wahrheitstabelle zu \(\lnot B\) Wir erstellen die Wahrheitstabelle für die Aussage \(\lnot B\):
Wahrheitstabelle zu \((A \implies B) \land (\lnot B)\) Wir erstellen die Wahrheitstabelle für die Aussage \((A \implies B) \land (\lnot B)\):
|  |
\(\enspace\)