Endliche Mengen & Einschluss-Ausschluss-Prinzip - Revision history

Bfh-sts: /* Beispiel */

2025-10-27T08:14:55Z

Beispiel

← Older revision		Revision as of 10:14, 27 October 2025
Line 26:		Line 26:

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

	== Herleitung der Formel ==		== Herleitung der Formel ==

Bfh-sts at 08:14, 27 October 2025

2025-10-27T08:14:11Z

← Older revision		Revision as of 10:14, 27 October 2025
Line 1:		Line 1:
	= Endliche Mengen und das 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.		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.		Für solche Mengen spielt das Zählen von Elementen und Überschneidungen eine zentrale Rolle.

	== Endliche und unendliche Mengen ==		== Endliche und unendliche Mengen ==
	Eine Menge heißt endlich, wenn sie genau m verschiedene Elemente enthält, wobei m eine natürliche Zahl ist.		Eine Menge heisst endlich, wenn sie genau m verschiedene Elemente enthält, wobei m eine natürliche Zahl ist.
	Sonst ~~heißt~~ sie unendlich.		Sonst heisst sie unendlich.

	Beispiele:		Beispiele:
Line 32:		Line 32:

	== Herleitung der Formel ==		== Herleitung der Formel ==
	Die Mengen A und B können als drei disjunkte Teilmengen betrachtet werden:		Die Mengen A und B können als drei disjunkte Teilmengen betrachtet werden:
	* A \ (A ∩ B)		* A \ (A ∩ B)
	* A ∩ B		* A ∩ B
Line 44:		Line 44:

	== Erweiterung auf drei Mengen ==		== Erweiterung auf drei Mengen ==
	Für drei endliche Mengen A, B, C gilt die Einschluss-Ausschluss-Formel:		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\|		\|A ∪ B ∪ C\| = \|A\| + \|B\| + \|C\| − \|A ∩ B\| − \|A ∩ C\| − \|B ∩ C\| + \|A ∩ B ∩ C\|
Line 73:		Line 73:
	* 189 alle drei Kurse		* 189 alle drei Kurse

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

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

	(b) Wie viele belegen genau einen Kurs?		(b) Wie viele belegen genau einen Kurs?

	= \|A\| + \|B\| + \|C\| − 2·(\|A ∩ B\| + \|A ∩ C\| + \|B ∩ C\|) + 3·\|A ∩ B ∩ C\|		= \|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		= 1’876 + 999 + 345 − 2·(876 + 231 + 290) + 3·189 = 1’002

	== Bedeutung ==		== Bedeutung ==
Line 91:		Line 91:

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

	[[Category:Set Theory (Mengenlehre)]]		[[Category:Set Theory (Mengenlehre)]]

Bfh-sts: Created page with "= 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. Beispie..."

2025-10-27T08:00:00Z

Created page with "= 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**. Beispie..."

New page

= 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.

[[Category:Set Theory (Mengenlehre)]]