De Morgan’sche Gesetze

De Morgan’sche Gesetze
De Morgan’sches Gesetz mit Logikgattern dargestellt

Die De Morgan’schen Gesetze (oft auch De Morgan’sche Regeln) sind zwei grundlegende Regeln für logische Aussagen. Sie wurden nach dem Mathematiker Augustus De Morgan benannt, obwohl sie bereits dem mittelalterlichen Logiker Wilhelm von Ockham bekannt waren. Sie gelten in allen Booleschen Algebren. Insbesondere sind sie in der Aussagenlogik und der Mengenlehre bedeutsam. In der Technik sind sie bedeutsam für die Erstellung von Verriegelungen und Programmen.

Inhaltsverzeichnis

Gesetze

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} bzw. mit anderer Notation: \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}.

Folgerungen

Eine Konjunktion (UND-Verknüpfung) lässt sich mithilfe des De Morganschen Gesetzes durch drei Negationen und einer 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.

Beispiele

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.

DeMorgan1.jpg DeMorgan2.jpg DeMorgan3.jpg
Aufteilung der Obermenge in A und B \overline{A}\cup\overline{B} \overline{A\cap B}


  • Eine Interpretation wäre:

In einer Abnahmeprüfung werden hochwertige Kochmesser darauf hin ü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.

Beispiel aus dem Alltag

Angenommen, eine Person trinkt gerne Kaffee: Um nun auszudrücken, dass sie diesen immer nur schwarz und ohne Zucker trinkt, kann sie folgende Aussagen formulieren:

Keine Milch und kein Zucker (im Kaffee), genau dann trinke ich den Kaffee.

Umgewandelt nach de Morgan:

Milch oder Zucker (im Kaffee), genau dann trinke ich den Kaffee nicht.

Beide Aussagen sind wertgleich.

Weblinks


Wikimedia Foundation.

Игры ⚽ Поможем написать курсовую

Schlagen Sie auch in anderen Wörterbüchern nach:

  • De Morgansche Gesetze — De Morgan sches Gesetz mit Logikgattern dargestellt Die De Morgan schen Gesetze (oft auch De Morgan sche Regeln) sind zwei grundlegende Regeln für logische Aussagen. Sie wurden nach dem Mathematiker Augustus De Morgan benannt, obwohl sie bereits… …   Deutsch Wikipedia

  • Morgansche Gesetze — De Morgan sches Gesetz mit Logikgattern dargestellt Die De Morgan schen Gesetze (oft auch De Morgan sche Regeln) sind zwei grundlegende Regeln für logische Aussagen. Sie wurden nach dem Mathematiker Augustus De Morgan benannt, obwohl sie bereits… …   Deutsch Wikipedia

  • Tautologie (Logik) — Eine Tautologie (altgr. τὸ αὐτό tò autó „dasselbe“ und logie), auch Verum (lat. verum „wahr“) genannt, ist in der Logik eine allgemein gültige Aussage, das heißt eine Aussage, die aus logischen Gründen immer wahr ist. Beispiele für Tautologien… …   Deutsch Wikipedia

  • De Morgansche Regel — De Morgan sches Gesetz mit Logikgattern dargestellt Die De Morgan schen Gesetze (oft auch De Morgan sche Regeln) sind zwei grundlegende Regeln für logische Aussagen. Sie wurden nach dem Mathematiker Augustus De Morgan benannt, obwohl sie bereits… …   Deutsch Wikipedia

  • De Morgansche Regeln — De Morgan sches Gesetz mit Logikgattern dargestellt Die De Morgan schen Gesetze (oft auch De Morgan sche Regeln) sind zwei grundlegende Regeln für logische Aussagen. Sie wurden nach dem Mathematiker Augustus De Morgan benannt, obwohl sie bereits… …   Deutsch Wikipedia

  • De Morgansches Gesetz — De Morgan sches Gesetz mit Logikgattern dargestellt Die De Morgan schen Gesetze (oft auch De Morgan sche Regeln) sind zwei grundlegende Regeln für logische Aussagen. Sie wurden nach dem Mathematiker Augustus De Morgan benannt, obwohl sie bereits… …   Deutsch Wikipedia

  • Morgansche Regel — De Morgan sches Gesetz mit Logikgattern dargestellt Die De Morgan schen Gesetze (oft auch De Morgan sche Regeln) sind zwei grundlegende Regeln für logische Aussagen. Sie wurden nach dem Mathematiker Augustus De Morgan benannt, obwohl sie bereits… …   Deutsch Wikipedia

  • Nordamerikanische Freistaaten [2] — Nordamerikanische Freistaaten (Gesch.). In den frühsten Zeiten bewohnte die Länder der jetzigen N. F. ein Volksstamm, der jetzt ausgestorben ist, von dem man aber noch viele Alterthümer findet, welche beweisen, daß er mehr Cultur besaß, als die… …   Pierer's Universal-Lexikon

  • True Wert — Die Aussagenlogik (veraltet Urteilslogik) ist der Bereich der Logik, der sich mit Aussagen und deren Verknüpfung durch Junktoren befasst, ausgehend von strukturlosen Elementaraussagen (Atomen), denen semantisch ein Wahrheitswert zugeordnet wird.… …   Deutsch Wikipedia

  • Urteilslogik — Die Aussagenlogik (veraltet Urteilslogik) ist der Bereich der Logik, der sich mit Aussagen und deren Verknüpfung durch Junktoren befasst, ausgehend von strukturlosen Elementaraussagen (Atomen), denen semantisch ein Wahrheitswert zugeordnet wird.… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”