De-Morgan-Regeln für Mengen

Erklärung

Die De-Morgan-Regeln beschreiben, wie sich das Komplement (Bezeichnung $\overline{A}$ oder $A^c$) mit Vereinigung und Schnitt verträgt: Beim Übergang zum Komplement wird aus $\cup$ ein $\cap$ und umgekehrt.

• „Nicht in $A$ oder $B$“ heißt „weder in $A$ noch in $B$“: $\overline{A \cup B} = \overline{A} \cap \overline{B}$.
• „Nicht in beiden“ heißt „nicht in $A$ oder nicht in $B$“: $\overline{A \cap B} = \overline{A} \cup \overline{B}$.

Beweis: $x \in \overline{A \cup B}$ bedeutet $\neg(x \in A \vee x \in B)$. Nach den De-Morgan-Regeln der Logik ist das gleichwertig zu $x \notin A \wedge x \notin B$, also $x \in \overline{A} \cap \overline{B}$.

Die Regeln gelten für beliebig viele Mengen, $\overline{\bigcup_i A_i} = \bigcap_i \overline{A_i}$, und auch für Differenzen: $C \setminus (A \cup B) = (C \setminus A) \cap (C \setminus B)$. In der Stochastik liefern sie Gegenereignisse, z.B. ist das Gegenteil von „$A$ oder $B$ tritt ein“ das Ereignis „weder $A$ noch $B$“.

Beispiele

Grundmenge $\Omega = \{1, \ldots, 10\}$, $A = \{2, 4, 6, 8, 10\}$ (gerade Zahlen), $B = \{3, 6, 9\}$ (Vielfache von $3$).

Erste Regel: $A \cup B = \{2, 3, 4, 6, 8, 9, 10\}$ hat $5 + 3 - 1 = 7$ Elemente, also $\overline{A \cup B} = \{1, 5, 7\}$ mit $10 - 7 = 3$ Elementen. Andererseits ist $\overline{A} = \{1, 3, 5, 7, 9\}$ und $\overline{B} = \{1, 2, 4, 5, 7, 8, 10\}$, und deren Schnitt ist ebenfalls $\{1, 5, 7\}$.

Zweite Regel: $A \cap B = \{6\}$, also hat $\overline{A \cap B}$ genau $10 - 1 = 9$ Elemente. Die Vereinigung $\overline{A} \cup \overline{B}$ hat $5 + 7 - 3 = 9$ Elemente, nämlich alle außer der $6$.

Typische Fehler

• Das Zeichen nicht umdrehen. $\overline{A \cup B} = \overline{A} \cup \overline{B}$ ist falsch. Im Beispiel wäre die $3$ in $\overline{A} \cup \overline{B}$, obwohl sie in $B$ liegt.
• Komplement ohne Grundmenge. $\overline{A}$ hängt von $\Omega$ ab. Für $A = \{2, 4\}$ ist das Komplement in $\{1, \ldots, 5\}$ eine andere Menge als in $\{1, \ldots, 10\}$.
• Doppelte Komplemente übersehen. Aus $\overline{A \cap \overline{B}}$ wird $\overline{A} \cup \overline{\overline{B}} = \overline{A} \cup B$, nicht $\overline{A} \cup \overline{B}$.