Beweisen mit Venn-Diagrammen

Schritt 0 Die Aufgabe

Es seien $A$ und $B$ zwei beliebige Mengen. Beweisen Sie mithilfe von Venn-Diagrammen …

… die de Morgan’schen Regeln, das heißt $(A \cup B)^{c} = A^{c} \cap B^{c} \qquad\text{und}\qquad (A \cap B)^{c} = A^{c} \cup B^{c}.$
… die Gültigkeit der Beziehung $|A \cup B| = |A| + |B| - |A \cap B|,$ wobei $|\cdot|$ die Anzahl der Elemente einer Menge beschreibt.

(i) Linke Seite gegen rechte Seite

beide Seiten der Gleichung einfärben und vergleichen

Schritt 1 Zuerst A ∪ B

Linke Seite, zuerst die Klammer: beide Kreise zusammen sind gefärbt

A \cup B

Schritt 2 Und jetzt das Komplement

Das Komplement dreht die Färbung um: übrig bleibt nur der Bereich außerhalb beider Kreise

(A \cup B)^{c}

Schritt 3 Rechts: zuerst Aᶜ, alles außer A

Rechte Seite, erster Baustein: alles außerhalb von Kreis

A

, also „nur

B

" und „in keinem"

A^{c}

Schritt 4 Dann Bᶜ, alles außer B

Zweiter Baustein: alles außerhalb von Kreis

B

, also „nur

A

" und „in keinem"

B^{c}

Schritt 5 Der Schnitt — und der Vergleich

$A^{c} \cap B^{c}$ behält nur, was in $A^{c}$ und in $B^{c}$ liegt: den Bereich „in keinem“ außerhalb beider Kreise. Links ist genau dieselbe Fläche gefärbt.

Erste Regel: „nicht (A oder B)" ist dasselbe wie „nicht A und nicht B"

(A \cup B)^{c} = A^{c} \cap B^{c}

Schritt 6 Jetzt die zweite Regel: A ∩ B

Zweite Regel, linke Seite, zuerst die Klammer: nur der Bereich „in beiden" in der Mitte ist gefärbt

A \cap B

Schritt 7 Komplement: alles außer der Mitte

Das Komplement dreht die Färbung wieder um: gefärbt sind die drei Bereiche außer „in beiden"

(A \cap B)^{c}

Schritt 8 Rechts: Aᶜ oder Bᶜ

Rechte Seite:

A^{c}

und

B^{c}

zusammengelegt ergeben „nur

A

", „nur

B

" und „in keinem"

A^{c} \cup B^{c}

Schritt 9 Auch hier dieselbe Fläche

Links und rechts ist wieder dieselbe Fläche gefärbt: alles außer der Mitte.

Zweite Regel: „nicht (A und B)" ist dasselbe wie „nicht A oder nicht B"

(A \cap B)^{c} = A^{c} \cup B^{c}

(ii) Warum man den Schnitt abziehen muss

Beispielzahlen aus Aufgabe 3

Schritt 10 Was |A| bedeutet

|A|

ist die Anzahl der Elemente von

A

. Beispiel: die Mengen aus Aufgabe 3

A = \{1, 2, 3\}, \qquad B = \{2, 4, 6\}

Schritt 11 Einfach addieren geht schief

Beide Mengen einzeln gezählt — die 2 steckt in beiden und zählt dabei zweimal

|A| = 3, \qquad |B| = 3, \qquad |A| + |B| = 6

Schritt 12 Wirklich sind es fünf

Tatsächlich sind es nur fünf verschiedene Zahlen: 1, 2, 3, 4, 6

|A \cap B| = |\{2\}| = 1

|A \cup B| = 5 \;=\; 6 - 1 \;=\; |A| + |B| - |A \cap B|

Schritt 13 Die Regel allgemein

Allgemein:

x

= Anzahl in „nur

A

y

= Anzahl in „in beiden",

z

= Anzahl in „nur

B

|A| + |B| - |A \cap B| = (x + y) + (y + z) - y = x + y + z = |A \cup B|

Schritt 14 Ergebnis

✓(i) Beide de Morgan’schen Regeln färben links und rechts dieselbe Fläche

✓(ii)

|A \cup B| = |A| + |B| - |A \cap B|

, weil der Schnitt sonst doppelt gezählt wird

Beides sind Aussagen über beliebige Mengen $A$ und $B$ — die Bilder zeigen alle vier möglichen Lagen einer Zahl und decken damit jeden Fall ab.

Bereich	$A^{c}$	$B^{c}$	$A^{c} \cap B^{c}$	$(A \cup B)^{c}$
nur A	nein	ja	nein	nein
in beiden	nein	nein	nein	nein
nur B	ja	nein	nein	nein
in keinem	ja	ja	ja	ja

Bereich	$A^{c}$	$B^{c}$	$A^{c} \cup B^{c}$
nur A	nein	ja	ja
in beiden	nein	nein	nein
nur B	ja	nein	ja
in keinem	ja	ja	ja

nur in $A$	1, 3	2 Stück
in beiden	2	1 Stück
nur in $B$	4, 6	2 Stück

$A$ besteht aus „nur A“ und „in beiden“	$\|A\| = x + y$
$B$ besteht aus „in beiden“ und „nur B“	$\|B\| = y + z$
$A \cap B$ ist „in beiden“	$\|A \cap B\| = y$
$A \cup B$ sind alle drei Bereiche	$\|A \cup B\| = x + y + z$