Quelltext der Seite De-morgansche Gesetze

[[Datei:DeMorgan Logic Circuit diagram DIN.svg|mini|De Morgansches Gesetz mit Logikgattern dargestellt]]
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 [[Boolesche Algebra|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]]:

:[[Negation|nicht]] (a [[Konjunktion (Logik)|und]] b) ist äquivalent zu ((nicht a) [[Disjunktion|oder]] (nicht b)), sowie
:nicht (a oder b) ist äquivalent zu ((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)} \iff \neg{a} \vee \neg{b} \\
\neg {(a \vee b)} \iff \neg{a} \wedge \neg{b}
\end{matrix}</math> bzw. mit anderer Notation: <math>\begin{matrix}
\overline{(a \wedge b)} \iff \overline{a} \vee \overline{b} \\
\overline{(a \vee b)} \iff \overline{a} \wedge \overline{b} \;.
\end{matrix}</math>

Ihre Entsprechung in der [[Mengenlehre]] lautet (dabei sind ''<span style="text-decoration:overline">A</span>'' das [[Komplement (Mengenlehre)|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>.

== Beweis ==

Ein formaler Beweis des De-morganschen Gesetzes ¬(a ∧ b) ⇔ ¬a ∨ ¬b im [[Fitch-Kalkül]] könnte etwa wie folgt aussehen:

{|class="wikitable"
|
{|class="hintergrundfarbe1" style="border:none; text-align:left; margin-left:2em"
|style="width:20em"|1 ¬(a ∧ b)||[Prämisse]
|-
|2 ¬(¬a ∨ ¬b)||[Annahme des Gegenteils des Ziels; beginnt einen Unterbeweis]
|-
|3 ¬a||[Unterannahme, beginnt einen Unter-Unterbeweis]
|-
|4 ¬a ∨ ¬b||[Disjunktionseinführung aus Zeile 3]
|-
|5 ⊥||[Widerspruch zwischen Zeilen 2 und 4]
|-
|6 a||[Negationseinführung aus Zeilen 3–5, beendet den ersten Unter-Unterbeweis]
|-
|7 ¬b||[Unterannahme, beginnt einen zweiten Unter-Unterbeweis]
|-
|8 ¬a ∨ ¬b||[Disjunktionseinführung aus Zeile 7]
|-
|9 ⊥||[Widerspruch zwischen Zeilen 2 und 8]
|-
|10 b||[Negationseinführung aus Zeilen 7–9, beendet den zweiten Unter-Unterbeweis]
|-
|11 a ∧ b||[Konjunktionseinführung aus Zeilen 6 und 10]
|-
|12 ⊥||[Widerspruch zwischen Zeilen 1 und 11]
|-
|13 ¬¬(¬a ∨ ¬b)||[Negationseinführung aus Zeilen 2–12, beendet den Unterbeweis]
|-
|14 ¬a ∨ ¬b||[Negationsbeseitigung aus Zeile 13; Beweis abgeschlossen]
|}
|}

Damit ist bewiesen, dass ¬(a ∧ b) → ¬a ∨ ¬b. Für den vollständigen Beweis des Gesetzes muss auch die Implikation in umgekehrter Richtung bewiesen werden:

{|class="wikitable"
|
{|class="hintergrundfarbe1" style="border:none; text-align:left; margin-left:2em"
|style="width:20em"|1 ¬a ∨ ¬b||[Prämisse]
|-
|2 a ∧ b||[Annahme des Gegenteils des Ziels; beginnt einen Unterbeweis]
|-
|3 ¬a||[Unterannahme; beginnt einen Unter-Unterbeweis]
|-
|4 a||[Konjunktionsbeseitigung aus Zeile 2]
|-
|5 ⊥||[Widerspruch zwischen Zeilen 3 und 4, beendet den ersten Unter-Unterbeweis]
|-
|6 ¬b||[Unterannahme, beginnt einen zweiten Unter-Unterbeweis]
|-
|7 b||[Konjunktionsbeseitigung aus Zeile 2]
|-
|8 ⊥||[Widerspruch zwischen Zeilen 6 und 7, beendet den zweiten Unter-Unterbeweis]
|-
|9 ⊥||[Disjunktionsbeseitigung aus Zeilen 1, 3–5 und 6–8, beendet den Unterbeweis]
|-
|10 ¬(a ∧ b)||[Negationseinführung aus Zeilen 2–9, _Beweis abgeschlossen]
|}
|}

Somit ist auch ¬a ∨ ¬b → ¬(a ∧ b) bewiesen. Da die Implikation nun in beiden Richtungen gezeigt ist, ist damit auch die logische Äquivalenz ¬(a ∧ b) ⇔ ¬a ∨ ¬b bewiesen. Mit ähnlichen Mitteln lässt sich auch das andere De-morgansche Gesetz, ¬(a ∨ b) ⇔ ¬a ∧ ¬b, zeigen.

Wahlweise kann der Beweis aber auch auf anderen Wegen, etwa mit [[Wahrheitstabelle]]n, geführt werden.

== Folgerungen ==

Eine [[Konjunktion (Logik)|Konjunktion]] (UND-Verknüpfung) lässt sich mithilfe des de-morganschen Gesetzes durch drei [[Negation]]en und einer [[Disjunktion]] (NICHT- beziehungsweise ODER-Verknüpfungen) darstellen:

:<math>a \wedge b \iff \neg(\neg{a} \vee \neg{b})\;.</math>

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

:<math> a \vee b \iff \neg(\neg{a} \wedge \neg{b})\;.</math>

== Anwendung ==

Die ''de-morganschen Gesetze'' haben wichtige Anwendungen in der [[Diskrete Mathematik|diskreten Mathematik]], der [[Elektrotechnik]], der [[Physik]] und der [[Informatik]]. Insbesondere werden die de-morganschen Gesetze beim Entwurf von [[Digitaltechnik|digitalen Schaltungen]] genutzt, um die Typen der verwendeten logischen [[Logikgatter|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 <span style="text-decoration:overline">A</span> und <span style="text-decoration:overline">B</span>.

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.

{| class="wikitable centered" style="text-align:center"
|-
| [[Datei:DeMorgan1.svg|200px]]
| [[Datei:DeMorgan2.svg|200px]]
| [[Datei:DeMorgan3.svg|200px]]
|-
| Aufteilung der Obermenge in A und B
| <math>\overline{A}\cup\overline{B} </math>
| <math>\overline{A\cap B} </math>
|}


''Eine Interpretation wäre:''<br />
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 <span style="text-decoration:overline">A</span> oder zur Menge <span style="text-decoration:overline">B</span> 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 ==
* [[Formelsammlung Logik]]
* [[T-Norm#T-Conormen|T-Norm und T-Conorm: De-Morgan-Triplett]]

== Weblinks ==
* [http://planetmath.org/?op=getobj&from=objects&id=4134 Beweis für die Mengenlehre über beliebige Indexmengen] (englisch)
* [http://www.ne555.at/2014/index.php/elektronik-grundlagen/digitaltechnik/175-schaltalgebra-boolsche-algebra- Einführung und Schaltungsbeispiele zu den de-morganschen Gesetzen]

[[Kategorie:Aussagenlogik]]
[[Kategorie:Mathematische Logik]]