Endliche Mengen & Einschluss-Ausschluss-Prinzip

Endliche Mengen und das Einschluss-Ausschluss-Prinzip

Viele praktische Probleme befassen sich mit endlichen Mengen, also Mengen mit abzählbarer Anzahl von Elementen. Für solche Mengen spielt das Zählen von Elementen und Überschneidungen eine zentrale Rolle.

Endliche und unendliche Mengen

Eine Menge heisst endlich, wenn sie genau *m* verschiedene Elemente enthält, wobei *m* eine natürliche Zahl ist. Sonst heisst sie unendlich.

Beispiele:

• ∅ → endlich, da keine Elemente
• Alphabet = {A, B, …, Z} → endlich
• ℕ = {1, 2, 3, 4, …} → unendlich

Die Anzahl der Elemente einer endlichen Menge A wird mit |A| bezeichnet.

Beispiel:

A = {1, 2, 3, 4} → |A| = 4

Vereinigung endlicher Mengen

Sind A und B endlich, so ist auch A ∪ B endlich. Dabei gilt die Grundformel:

|A ∪ B| = |A| + |B| − |A ∩ B|

Diese Formel korrigiert die doppelte Zählung der Schnittmenge.

Beispiel

A = {1, 2, 3, 4}, B = {3, 4, 5, 6} |A| = 4, |B| = 4, |A ∩ B| = 2 → |A ∪ B| = 4 + 4 − 2 = 6 A ∪ B = {1, 2, 3, 4, 5, 6}

Herleitung der Formel

Die Mengen A und B können als drei disjunkte Teilmengen betrachtet werden:

• A \ (A ∩ B)
• A ∩ B
• B \ (A ∩ B)

Da diese drei Mengen keine Überschneidung haben, gilt:

|A ∪ B| = |A \ (A ∩ B)| + |A ∩ B| + |B \ (A ∩ B)|

Daraus folgt:

|A ∪ B| = |A| + |B| − |A ∩ B|

Erweiterung auf drei Mengen

Für drei endliche Mengen A, B, C gilt die Einschluss-Ausschluss-Formel:

|A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |A ∩ C| − |B ∩ C| + |A ∩ B ∩ C|

Diese Formel berücksichtigt alle Überschneidungen korrekt:

• Einfache Mengen: +
• Doppelte Schnittmengen: −
• Dreifache Schnittmenge: +

Erweiterung auf vier Mengen

Für A, B, C, D gilt:

|A ∪ B ∪ C ∪ D| =  
|A| + |B| + |C| + |D|  
− (|A ∩ B| + |A ∩ C| + |A ∩ D| + |B ∩ C| + |B ∩ D| + |C ∩ D|)  
+ (|A ∩ B ∩ C| + |A ∩ B ∩ D| + |A ∩ C ∩ D| + |B ∩ C ∩ D|)  
− |A ∩ B ∩ C ∩ D|

Beispiel: Anwendung auf Studierende

An einer Universität studieren 2’504 Studierende Informatik. Davon belegen:

• 1’876 Java
• 999 C
• 345 Prolog
• 876 sowohl Java als auch C
• 231 C und Prolog
• 290 Java und Prolog
• 189 alle drei Kurse

(a) Wie viele Studierende belegen keinen der drei Kurse?

|U| = 2’504 |A ∪ B ∪ C| = 1’876 + 999 + 345 − 876 − 231 − 290 + 189 = 2’012 → Studierende ohne Kurs = 2’504 − 2’012 = 492

(b) Wie viele belegen genau einen Kurs?

= |A| + |B| + |C| − 2·(|A ∩ B| + |A ∩ C| + |B ∩ C|) + 3·|A ∩ B ∩ C| = 1’876 + 999 + 345 − 2·(876 + 231 + 290) + 3·189 = 1’002

Bedeutung

Das Einschluss-Ausschluss-Prinzip ist ein zentrales Werkzeug:

• zur Bestimmung der Kardinalität von Vereinigungen
• in Kombinatorik, Statistik und Wahrscheinlichkeitstheorie
• für logische Vereinfachungen in der Informatik (z. B. Boolesche Algebra)

Zusammenfassung

• Eine Menge ist endlich, wenn sie eine abzählbare Anzahl von Elementen hat.
• |A ∪ B| = |A| + |B| − |A ∩ B| korrigiert doppelte Zählung.
• Das Einschluss-Ausschluss-Prinzip erweitert diese Idee auf mehrere Mengen.
• In der Informatik hilft es beim Zählen von Zuständen, Kombinationen und logischen Fällen.