Absorptionsgesetze Gesetze von De Morgan
Die Gesetze von De Morgan besagen, dass sich die Negation einer Oder-Verknüpfung durch die Und-Verknüpfung der negierten Ausdrücke ausdrücken lässt und dass man die Negation einer Und-Verknüpfung durch die Oder-Verknüpfung der negierten Aussagen ausdrücken kann.
Gesetze von De Morgan:
Für die Formeln \(\alpha\) und \(\beta\) gelten die folgenden Tautologien:
- \((\lnot(\alpha \lor \beta)) \iff (\lnot \alpha \land \lnot \beta)\enspace\) ist eine Tautologie
- \((\lnot(\alpha \land \beta)) \iff (\lnot \alpha \lor \lnot \beta)\enspace\) ist eine Tautologie
Beweise
Beweis des 1. Gesetzes von De Morgan:
Wir beweisen:
\(\qquad\) | \((\lnot(\alpha \lor \beta)) \iff (\lnot \alpha \land \lnot \beta)\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 & \lnot (\alpha \lor \beta) &\lnot \alpha & \lnot \beta & \lnot \alpha \land \lnot \beta & (\lnot(\alpha\lor \beta))\\ & & \hspace{-0.8em} & & & & & & \iff(\lnot \alpha \land \lnot \beta)\ \\\hline \mathrm{w} & \mathrm{w} & \hspace{-0.8em} & \mathrm{w} & \mathrm{f} & \mathrm{f}& \mathrm{f}& \mathrm{f}& \mathrm{w}\ \\\hline \mathrm{w} & \mathrm{f} & \hspace{-0.8em} & \mathrm{w} & \mathrm{f} & \mathrm{f}& \mathrm{w}& \mathrm{f}& \mathrm{w}\ \\\hline \mathrm{f} & \mathrm{w} & \hspace{-0.8em} & \mathrm{w} & \mathrm{f} & \mathrm{w}& \mathrm{f}& \mathrm{f}& \mathrm{w}\ \\\hline \mathrm{f} & \mathrm{f} & \hspace{-0.8em} & \mathrm{f} & \mathrm{w} & \mathrm{w}& \mathrm{w}& \mathrm{w}& \mathrm{w}\ \\ \hline\end{array}\) |
Die Aussage ist eine Tautologie.
Beweis des 2. Gesetzes von De Morgan:
Wir beweisen:
\(\qquad\) | \((\lnot(\alpha \land \beta)) \iff (\lnot \alpha \lor \lnot \beta)\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 & \lnot (\alpha \land \beta) &\lnot \alpha & \lnot \beta & \lnot \alpha \lor \lnot \beta & (\lnot(\alpha\land \beta))\\ & & \hspace{-0.8em} & & & & & &\iff(\lnot \alpha \lor \lnot \beta)\ \\\hline \mathrm{w} & \mathrm{w} & \hspace{-0.8em} & \mathrm{w} & \mathrm{f} & \mathrm{f}& \mathrm{f}& \mathrm{f}& \mathrm{w}\ \\\hline \mathrm{w} & \mathrm{f} & \hspace{-0.8em} & \mathrm{f} & \mathrm{w} & \mathrm{f}& \mathrm{w}& \mathrm{w}& \mathrm{w}\ \\\hline \mathrm{f} & \mathrm{w} & \hspace{-0.8em} & \mathrm{f} & \mathrm{w} & \mathrm{w}& \mathrm{f}& \mathrm{w}& \mathrm{w}\ \\\hline \mathrm{f} & \mathrm{f} & \hspace{-0.8em} & \mathrm{f} & \mathrm{w} & \mathrm{w}& \mathrm{w}& \mathrm{w}& \mathrm{w}\ \\ \hline\end{array}\) |
Die Aussage ist eine Tautologie.
Die Gesetze von De Morgan finden ihre Anwendung in anderen Teilgebieten der Mathematik, in der Elektrotechnik, der Physik und der Informatik. Sie werden z.B. beim Entwurf digitaler Schaltungen verwendet, um Schaltelemente gegeneinander auszutauschen oder Bauteile einzusparen.
Folgerungen:
Die Konjunktion lässt sich mit den Gesetzen von De Morgan durch mehrere Negationen und einer Disjunktion darstellen:
\(\qquad\) | \((\alpha \land \beta) \iff (\lnot (\lnot \alpha \lor \lnot \beta))\) |
Die Disjunktion lässt sich mit den Gesetzen von De Morgan durch mehrere Negationen und einer Konjunktion darstellen:
\(\qquad\) | \((\alpha \lor \beta) \iff (\lnot (\lnot \alpha \land \lnot \beta))\) |
\(\enspace\)