Mengenalgebra & Dualität: Gesetze und de Morgan

Mengenalgebra und Dualität

Die in der Mengenlehre definierten Operationen (Vereinigung, Durchschnitt, Komplement, Differenz) folgen bestimmten algebraischen Gesetzen. Diese Gesetze erlauben es, Ausdrücke zu vereinfachen oder zu beweisen, dass zwei Mengenoperationen äquivalent sind.

Grundlegende Gesetze der Mengenalgebra

Für beliebige Mengen A, B, C und die Universalmenge U gelten folgende Gesetze:

1. Idempotenz

A ∪ A = A A ∩ A = A

Das Zusammenfassen oder Schneiden einer Menge mit sich selbst ändert nichts.

2. Assoziativgesetz

(A ∪ B) ∪ C = A ∪ (B ∪ C) (A ∩ B) ∩ C = A ∩ (B ∩ C)

Die Reihenfolge der Ausführung spielt keine Rolle.

3. Kommutativgesetz

A ∪ B = B ∪ A A ∩ B = B ∩ A

Die Reihenfolge der Mengen kann vertauscht werden.

4. Distributivgesetz

A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C) A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)

Dies erlaubt, Ausdrücke zu „verteilen“, ähnlich wie beim Distributivgesetz der Algebra.

5. Identitätsgesetz

A ∪ ∅ = A A ∩ U = A

∅ und U verhalten sich wie 0 und 1 in der Arithmetik.

6. Null- und Einheitsgesetz

A ∪ U = U A ∩ ∅ = ∅

Alles mit der Universalmenge vereinigt ergibt U; alles mit der leeren Menge geschnitten ergibt ∅.

7. Gesetz vom doppelten Komplement

(Aᶜ)ᶜ = A

Das Komplement des Komplements ergibt wieder die ursprüngliche Menge.

8. Komplementgesetze

A ∪ Aᶜ = U A ∩ Aᶜ = ∅

Eine Menge und ihr Komplement decken die Universalmenge vollständig ab, ohne sich zu überschneiden.

9. Komplemente der Universal- und Leermenge

Uᶜ = ∅ ∅ᶜ = U

10. de Morgan’sche Gesetze

(A ∪ B)ᶜ = Aᶜ ∩ Bᶜ (A ∩ B)ᶜ = Aᶜ ∪ Bᶜ

Diese sind besonders wichtig, da sie eine enge Verbindung zur Aussagenlogik zeigen:

• Das Komplement einer Vereinigung ist der Durchschnitt der Komplemente.
• Das Komplement eines Durchschnitts ist die Vereinigung der Komplemente.

Beispiel: Beweis des de Morgan Gesetzes

Beweise (A ∩ B)ᶜ = Aᶜ ∪ Bᶜ mithilfe der Logik:

| Aussage      | Logisches Pendant      |
|--------------|------------------------|
| x ∈ (A ∩ B)ᶜ | ¬(x ∈ A ∧ x ∈ B)       |
|              | ⇔ (¬x ∈ A) ∨ (¬x ∈ B) |
|              | ⇔ x ∈ Aᶜ ∨ x ∈ Bᶜ     |
| ⇒           | x ∈ (Aᶜ ∪ Bᶜ)          |

Daraus folgt: (A ∩ B)ᶜ = Aᶜ ∪ Bᶜ

Dualitätsprinzip

Die Gesetze der Mengenlehre treten paarweise auf. Tauscht man überall

• ∪ ↔ ∩
• U ↔ ∅

so erhält man den dualen Ausdruck.

Beispiel:

• Gesetz A ∪ ∅ = A hat als Dual A ∩ U = A
• de Morgan’s Gesetz (A ∪ B)ᶜ = Aᶜ ∩ Bᶜ hat als Dual (A ∩ B)ᶜ = Aᶜ ∪ Bᶜ

Dieses Prinzip zeigt die symmetrische Struktur der Mengenoperationen.

Visualisierung

Venn-Diagramme verdeutlichen diese Gesetze grafisch:

• Die Vereinigungen und Durchschnitte entsprechen farblich markierten Bereichen.
• Komplementbereiche sind die Flächen ausserhalb der betrachteten Menge.

Zusammenfassung

• Mengenoperationen folgen festen algebraischen Gesetzen.
• Diese Gesetze entsprechen den Regeln der Aussagenlogik.
• Das Dualitätsprinzip erlaubt, aus jedem Gesetz sein komplementäres Gegenstück zu bilden.
• Die de Morgan’schen Gesetze sind besonders zentral für logische und rechnerische Anwendungen.