De Morgansche Gesetze - LinkFang.de





De Morgansche Gesetze


Die De Morganschen Gesetze (oft auch De Morgansche 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.

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:

[math]\begin{matrix} \neg {(a \wedge b)} = \neg{a} \vee \neg{b} \\ \neg {(a \vee b)} = \neg{a} \wedge \neg{b} \end{matrix}[/math] bzw. mit anderer Notation: [math]\begin{matrix} \overline{(a \wedge b)} = \overline{a} \vee \overline{b} \\ \overline{(a \vee b)} = \overline{a} \wedge \overline{b} \end{matrix}[/math]

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, [math]\cap[/math] das Symbol für den Schnitt zweier Mengen und [math]\cup[/math] das Symbol für die Vereinigung zweier Mengen):

[math]\overline{A \cap B} = \overline{A} \cup \overline{B}[/math]
[math]\overline{A \cup B} = \overline{A} \cap \overline{B}[/math]

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:

[math]\overline{\bigcap_{i \in I} A_i} = \bigcup_{i \in I} \overline{A_i}[/math] und [math]\overline{\bigcup_{i \in I} A_i} = \bigcap_{i \in I} \overline{A_i}[/math].

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:

[math]a \wedge b = \neg(\neg{a} \vee \neg{b})[/math]

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

[math] a \vee b = \neg(\neg{a} \wedge \neg{b})[/math]

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 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:

Wenn Milch oder Zucker enthalten ist, dann trinke ich den Kaffee nicht.

Umgewandelt nach de Morgan und Kontraposition:

Wenn ich den Kaffee trinke, dann ist keine Milch und kein Zucker enthalten.

Beide Aussagen sind wertgleich.

Beispiel in der Mengenlehre

Es soll anhand der Beziehung

[math] \overline{A} \cup \overline{B} = \overline{A \cap B} [/math]

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 [math]\overline{A} \cup \overline{B}[/math] gebildet wird. In der Grafik 3 wird das Komplement zu [math]A \cap B[/math] dargestellt, und man sieht, dass beide Mengen gleich sind.

Aufteilung der Obermenge in A und B [math]\overline{A}\cup\overline{B} [/math] [math]\overline{A\cap B} [/math]

Eine Interpretation wäre:
In einer Abnahmeprüfung werden hochwertige Kochmesser daraufhin ü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: [math]\overline{A} \cup \overline{B}[/math]. Das Messer wird angenommen, wenn es beide Anforderungen erfüllt, wenn es also zur Menge [math]A \cap B[/math] gehört, das heißt, es wird nicht angenommen, wenn es zu [math]\overline{A \cap B}[/math] gehört.

Siehe auch

Weblinks


Kategorien: Mathematische Logik

Quelle: Wikipedia - http://de.wikipedia.org/wiki/De Morgansche Gesetze (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.