Boolesche Mengenoperationen
Eine Mengenoperation liefert, angewendet auf eine oder mehrere Mengen, erneut eine Menge. Wichtige Beispiele sind die Booleschen Mengenoperation bezüglich einer Grundmenge M. Sie sind für alle A, B ⊆ M definiert.
Operation | Definition | Bezeichnung | Lesart |
Ac | { a ∈ M | a ∉ A } | relatives Komplement | A Komplement |
A ∩ B | { a ∈ M | a ∈ A ∧ a ∈ B } | Durchschnitt | A geschnitten B |
A ∪ B | { a ∈ M | a ∈ A ∨ a ∈ B } | Vereinigung | A vereinigt B |
A − B, A \ B | { a ∈ M | a ∈ A ∧ a ∉ B } | Differenz | A ohne B |
A Δ B | { a ∈ M | a ∈ A ⩒ a ∈ B } | symmetrische Differenz | A Delta B |
Identität („Rechenregel“) | Name |
(Ac)c = A | doppeltes Komplement |
A ∪ Ac = M, A ∩ Ac = ∅ | Komplementzerlegung |
(A ∩ B)c = Ac ∪ Bc (A ∪ B)c = Ac ∩ Bc | de Morgansche Regeln |
A ∩ (B ∩ C) = (A ∩ B) ∩ C A ∪ (B ∪ C) = (A ∪ B) ∪ C | Assoziativgesetze |
A ∩ B = B ∩ A, A ∪ B = B ∪ A | Kommutativgesetze |
A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C) A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C) | Distributivgesetze |
A − B = A − (B ∩ A) = A ∩ Bc A − (B − C) = (A − B) ∪ (A ∩ C) (A − B) − C = A − (B ∪ C) | Differenzenregeln |
A Δ (B Δ C) = (A Δ B) Δ C A Δ B = B Δ A (A Δ B) ∩ C = (A ∩ C) Δ (B ∩ C) | Δ-Regeln |
Zwischen den Booleschen Mengenoperationen und den logischen Junktoren bestehen die folgenden Entsprechungen:
Operation | Ac | A ∩ B | A ∪ B | Ac ∪ B | (A Δ B)c | A Δ B | A − B |
Junktor | ¬ A | A ∧ B | A ∨ B | A → B | A ↔ B | A ⩒ B | A ∧ ¬ B |
Zudem kann der leeren Menge das Falsum ⊥ und der Grundmenge M das Verum ¬ ⊥ zugeordnet werden.
Auf der Ebene einer Aussage über Mengen hat die Inklusion A ⊆ B die Entsprechung A → B und die Gleichheit A = B die Entsprechung A ↔ B. Die Aussage A = ∅ für Mengen entspricht ¬ A für Aussagen, und ebenso entsprechen A = M und A einander. Damit lassen sich Identitäten für Mengen in Tautologien übersetzen und umgekehrt. Beispiele sind:
Identität | Tautologie |
A ⊆ A, Ac ∪ A = M | A → A |
A = A, (A Δ A)c = M | A ↔ A |
(Ac)c = A | ¬ ¬ A ↔ A |
Ac = Ac ∪ ∅ | ¬ A ↔ A → ⊥ |
A ∪ Ac = M | A ∨ ¬ A |
A ∩ Ac = ∅ | A ∧ ¬ A ↔ ⊥, ¬ (A ∧ ¬ A) |
∅ ⊆ A | ⊥ → A |
A ∩ B ⊆ A | A ∧ B → A |
Ac ∪ B = (Bc)c ∪ Ac | (A → B) ↔ (¬ B → ¬ A) |
(A ∪ B)c = Ac ∩ Bc | ¬ (A ∨ B) ↔ ¬ A ∧ ¬ B |
Da sich Tautologien mechanisch (zum Beispiel mit Wahrheitstafeln) als solche erkennen lassen, gilt dies auch für Identitäten der Booleschen Mengenoperationen. Bemerkenswert ist, dass die Wichtigkeit einander entsprechender Aussagen stark verschieden sein kann. Das Kontrapositionsgesetz (vorletzte Zeile der Tabelle) spielt für das indirekte Beweisen eine fundamentale Rolle. Seine mengentheoretische Entsprechung ist nicht besonders aufregend.