Das Kefk Network Wiki befindet sich im Testbetrieb.

De Morgansche Gesetze

Aus Kefk.

Wechseln zu: Navigation, Suche

Die De Morganschen Gesetze (oft auch De Morgansche Regeln) sind zwei wichtige, nach dem Mathematiker Augustus De Morgan benannte Regeln, die aber bereits der mittelalterliche Logiker Wilhelm von Ockham aufstellte. Sie gelten in allen Booleschen Algebren. Insbesondere sind sie in der Aussagenlogik und der Mengenlehre bedeutsam.

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}

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

Ihre Entsprechung in der Mengenlehre lautet (dabei sind A das Komplement von A, \cap das Symbol für den Schnitt zweier Mengen und \cup das Symbol für die Vereinigung zweier Mengen):

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

Die Regeln lassen sich auch für Verknüpfungen beliebig vieler Elemente erweitern. So gilt für jede beliebige endliche, abzählbare oder auch nicht abzählbare Indexmenge I:

\overline{\bigcap_{i \in I} A_i} = \bigcup_{i \in I} \overline{A_i} und \overline{\bigcup_{i \in I} A_i} = \bigcap_{i \in I} \overline{A_i}.

Inhaltsverzeichnis

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, der Elektrotechnik, der Physik und der Informatik. Die De Morganschen Gesetze werden häufig in der Entwicklung digitaler Schaltkreise genutzt, um die Typen verwendeter logischer Schaltelemente gegeneinander auszutauschen, oder Bauteile einzusparen.

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.

Bild:DeMorgan1.jpg Bild:DeMorgan2.jpg Bild:DeMorgan3.jpg
Aufteilung der Obermenge in A und B A ∪ B A ∩ B


  • Eine Interpretation wäre:

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). 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.

Weblinks

Beweis für die Mengenlehre über beliebige Indexmengen (englisch)

Wikipedia
 Dieses Dokument entstammt in seiner ersten oder einer späteren Version der deutschsprachigen Wikipedia. Es ist dort zu finden unter dem Stichwort De_Morgansche_Gesetze, die Liste der bisherigen Autoren befindet sich in der Versionsliste; die Originalfassung kann dort auch bearbeitet werden. Alle Texte der Wikipedia und ihre Derivate stehen unter der GNU-Lizenz für freie Dokumentation.
Von „http://kefk.org/wiki/De_Morgansche_Gesetze“
Persönliche Werkzeuge