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 heißt **endlich**, wenn sie genau *m* verschiedene Elemente enthält, wobei *m* eine natürliche Zahl ist. Sonst heißt 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.