De Morgansche Gesetze

Die De Morganschen Gesetze sind zwei wichtige Regeln der Logik und der Mengenlehre. Sie sind benannt nach dem Mathematiker Augustus De Morgan, der im 19. Jahrhundert lebte, und gelten in allen Booleschen Algebren.

Sie lauten in der Logik:

nicht (a und b) = (nicht a) oder (nicht b)
nicht (a oder b) = (nicht a) und (nicht b)

In der Mathematik findet man zahlreiche unterschiedliche Darstellungen der De Morganschen Gesetze der Aussagenlogik:

\begin{matrix} \neg {(a \wedge b)} = \neg{a} \vee \neg{b} \\ \neg {(a \vee b)} = \neg{a} \wedge \neg{b} \end{matrix} oder \begin{matrix} \overline{(a \wedge b)} = \overline{a} \vee \overline{b} \\ \overline{(a \vee b)} = \overline{a} \wedge \overline{b} \end{matrix}

Ihre Entsprechung in der Mengenlehre lautet (dabei ist A das Komplement von A):

\overline{A \cap B} = \overline{A} \cup \overline{B}
\overline{A \cup B} = \overline{A} \cap \overline{B}


Die Gültigkeit der De Morganschen Gesetze kann mithilfe von Wahrheitstabellen bewiesen werden.

Folgerungen

Eine Konjunktion (UND-Verknüpfung) lässt sich mithilfe des De Morganschen Gesetzes durch drei Negationen und eine Disjunktion (NICHT- beziehungsweise ODER-Verknüpfungen) darstellen:

a \wedge b = \neg(\neg{a} \vee \neg{b})

Entsprechend lässt sich eine Disjunktion durch drei Negationen und eine Konjunktion darstellen::

a \vee b = \neg(\neg{a} \wedge \neg{b})

Anwendung

Die De Morganschen Gesetze haben wichtige Anwendungen in der diskreten Mathematik und in der Elektrotechnik. Die De Morganschen Gesetze werden häufig in der Entwicklung digitaler Schaltkreise genutzt, um die Typen verwendeter logischer Schaltelemente gegeneinander auszutauschen.

Beispiel in der Mengenlehre

Es soll anhand der Beziehung

\overline{A} \cup \overline{B} = \overline{A \cap B}

die Gültigkeit der De Morganschen Regeln illustriert werden. Es sind zwei Mengen A und B gegeben, die Teilmengen einer Obermenge Ω sind. Die Grafik 1 zeigt die Lage der Mengen und ihrer Gegenmengen A und B.

In der Grafik 2 wird gezeigt, wie \overline{A} \cup \overline{B} gebildet wird. In der Grafik 3 wird das Komplement zu A \cap B dargestellt und man sieht, dass beide Mengen gleich sind.

thumb|Grafik 1: Aufteilung der Obermenge in A und B thumb|Grafik 2: A ∪ Bl thumb|Grafik 3: A ∩ Bl


In einer Abnahmeprüfung werden hochwertige Kochmesser überprüft, ob die Schneide fehlerfrei ist (Menge A) und ob die Schneide ordnungsgemäß im Griff verankert ist (Menge B). Es ist dann A die Menge der Messer, deren Schneide beanstandet wird, entsprechend B. Ein Messer wird nicht angenommen, wenn es zur Menge A oder zur Menge B oder zu beiden gehört, also wenn mindestens eine Beanstandung vorliegt: \overline{A} \cup \overline{B}. Das Messer wird angenommen, wenn es beide Anforderungen erfüllt, wenn es also zur Menge A \cap B gehört, das heißt, es wird nicht angenommen, wenn es zu \overline{A \cap B} gehört.

See also: De Morgansche Gesetze, Augustus De Morgan, Aussagenlogik, Boolesche Algebra, Digital, Disjunktion, Diskrete Mathematik, Elektrotechnik, Gatter (Elektronik), Komplement (Mengenlehre)