Nun gilt es, eine weitere Eigenschaft zu untersuchen, die häufig in der Aussagenlogik verwendet wird: die Beweise der DeMorgan-Gesetze und der Distributivgesetze für Konjunktion und Disjunktion. Die Anwendung dieser Gesetze ist in der Mengenlehre üblich und durchdringt darüber hinaus die gesamte Mathematik – von der Wahrscheinlichkeitsrechnung über die Topologie bis hin zu ihrer Präsenz in der Elektronik und Programmierung. Wie gewohnt werden wir die Beweise dieser Gesetze auf Grundlage der bisher erlernten Deduktionstechniken Schritt für Schritt erarbeiten.

DeMorgan-Gesetze

Die DeMorgan-Gesetze sind eine Reihe von Äquivalenzen, die die Verteilung von Negationen auf Konjunktion und Disjunktion formalisieren. Formal werden sie durch die folgenden Äquivalenzen ausgedrückt:

\neg(\alpha \wedge \beta) \dashv \vdash (\neg\alpha \vee \neg \beta)

\neg(\alpha \vee \beta) \dashv \vdash (\neg\alpha \wedge \neg \beta)

Diese bewiesenen Äquivalenzen lassen sich auch ohne eine formale Beweiskette im Stil der bisherigen Demonstrationen herleiten, indem man die Definitionen, die Konjunktionen mit Disjunktionen verknüpfen, sowie die Äquivalenz der doppelten Negation und einfache Substitutionen verwendet. Aus der Definition der Konjunktion folgt:

(A \wedge B):= \neg(\neg A \vee \neg B)

Wendet man auf beiden Seiten dieser Aussage eine Negation an, ergibt sich:

\neg(A \wedge B):= \neg\neg(\neg A \vee \neg B)

Durch Anwendung der Äquivalenz der doppelten Negation ergibt sich schließlich:

\neg(A \wedge B)\dashv \vdash (\neg A \vee \neg B)

Ersetzt man nun A=\alpha und B=\beta, erhält man die erste DeMorgan-Äquivalenz:

\boxed{\neg(\alpha \wedge \beta) \dashv \vdash (\neg\alpha \vee \neg \beta)}

Um die zweite Äquivalenz zu erhalten, kann man die vorherige Gleichung weiterverwenden und erneut auf beiden Seiten eine Negation anwenden, was zu folgendem führt:

\neg\neg(A \wedge B)\dashv \vdash \neg(\neg A \vee \neg B)

Und erneut durch doppelte Negation ergibt sich:

\neg(\neg A \vee \neg B) \dashv \vdash (A \wedge B)

Wenn wir in diesem letzten Ausdruck A=\neg\alpha und B=\neg\beta einsetzen, erhalten wir:

\neg(\neg \neg\alpha \vee \neg \neg\beta) \dashv \vdash (\neg\alpha \wedge \neg\beta)

Was aufgrund der Äquivalenz der doppelten Negation zur zweiten DeMorgan-Äquivalenz führt:

\boxed{\neg( \alpha \vee \beta) \dashv \vdash (\neg\alpha \wedge \neg\beta)}

Darüber hinaus lassen sich auf ganz analoge Weise zusätzliche Formen herleiten, die lediglich Varianten der bereits untersuchten Äquivalenzen darstellen:

\neg(\neg\alpha \wedge \beta) \dashv \vdash (\alpha \vee \neg \beta)

\neg(\neg\alpha \vee \beta) \dashv \vdash (\alpha \wedge \neg \beta)

\neg(\alpha \wedge \neg\beta) \dashv \vdash (\neg\alpha \vee \beta)

\neg(\alpha \vee \neg\beta) \dashv \vdash (\neg\alpha \wedge \beta)

Distributivgesetze zwischen Konjunktion und Disjunktion

Wie der Name schon andeutet, ermöglichen uns diese Regeln die Verteilung von Konjunktionen und Disjunktionen innerhalb eines Ausdrucks. Diese Gesetze lassen sich in den folgenden zwei Äquivalenzen zusammenfassen:

Wie schon bei früheren Themen handelt es sich zwar um bekannte Resultate, deren Beweise jedoch keineswegs trivial sind. Um diese Äquivalenzen vollständig zu beweisen, muss in beide Richtungen argumentiert werden. In diesem Abschnitt wird jedoch nur der Beweis in eine Richtung präsentiert; der Beweis in die Gegenrichtung bleibt als Übung dem Leser überlassen.

∧ – Distributivität

Um zu zeigen, dass gilt \{(\alpha \wedge(\beta \vee\gamma))\}\vdash((\alpha \wedge \beta)\vee(\alpha \wedge \gamma)), folgt die folgende Überlegung.

Damit ist bewiesen, dass \{(\alpha \wedge(\beta \vee\gamma))\}\vdash((\alpha \wedge \beta)\vee(\alpha \wedge \gamma)). Nun bist du an der Reihe, dein Wissen unter Beweis zu stellen und selbstständig zu zeigen, dass \{((\alpha \wedge \beta)\vee(\alpha \wedge \gamma))\}\vdash (\alpha \wedge(\beta \vee\gamma)).

∨ – Distributivität

Der Beweis von \{(\alpha \vee(\beta \wedge\gamma))\}\vdash((\alpha \vee \beta)\wedge(\alpha \vee \gamma)) ergibt sich aus folgender Überlegung:

Dies stellt die erste Hälfte des Beweises dar – der Rückweg bleibt dem Leser als Übung überlassen :3

Abschließende Überlegungen

Mit dieser Durchsicht der Beweise zu den de Morganschen Gesetzen zur Verteilung von Konjunktion und Disjunktion können wir unser Studium der Deduktionstechniken der Aussagenlogik abschließen – zumindest im Hinblick auf die wichtigsten Gesetze der klassischen Logik.

Es ist wichtig, alle vorgeschlagenen Beweise vollständig durchzuarbeiten, um das Verständnis dieser Techniken zu festigen. Um dies etwas leichter zu gestalten, ist es sehr hilfreich, die Beweise auf Gemeinsamkeiten hin zu vergleichen. Es ist nämlich gut möglich, dass die Strategie, die bei einem Beweis erfolgreich war, mit kleinen Anpassungen auch für andere funktioniert.

Ein letzter Punkt, den es sich zu beachten lohnt, ist die Reihenfolge, in der ich diese Beweise entwickelt habe. Du wirst bemerken, dass jeder Beweis auf den Ergebnissen vorheriger Beweise aufbaut. Ich habe diese Reihenfolge gewählt, weil sie mir persönlich am einfachsten erschien. Eine gute Übung zur Verbesserung deiner Fähigkeiten in diesem Bereich besteht darin, dir die Frage zu stellen: „Kann ich diese Beweise auch in einer anderen Reihenfolge aufbauen, wenn ich dieselbe Methodik anwende?“ Ich empfehle dir nachdrücklich, zu versuchen, die Beweise in einer anderen Reihenfolge herzuleiten und jeweils die vorherigen als Grundlage für die nächsten zu verwenden. Auch wenn es dir nicht vollständig gelingt, wirst du durch den Versuch ein besseres Verständnis für die Beweise und die in der Logik verwendeten Methoden erlangen.