Mathe für Nicht-Freaks: Boolesche Algebra

{{#invoke:Mathe für Nicht-Freaks/Seite|oben}}

In den vorangegangenen Kapiteln haben wir verschiedene Verknüpfungen zwischen Mengen kennengelernt. Die Regeln, die für diese Verknüpfungen gelten, sind hier übersichtlich zusammengestellt. $A$, $B$, $C$, $\dots$ seien im Folgenden beliebige Mengen.

Regeln für den Durchschnitt und die Vereinigung

Durchschnitt $\cap$ und Vereinigung $\cup$ verhalten sich zueinander "dual": wenn du in einer Regel $\cap$ mit $\cup$ und $𝒱$ mit $\varnothing$ vertauschst, erhältst du wieder eine gültige Regel! Die Beweise - soweit sie hier nicht angegeben sind - findest du in den Kapiteln Durchschnitt von Mengen und Vereinigung von Mengen.

Assoziativität

Beim Durchschnitt $\cap$ und bei der Vereinigung $\cup$ ist es egal, in welcher Reihenfolge du die Verknüpfungen ausführst.

• $(A\cap B)\cap C=A\cap (B\cap C)$
• $(A\cup B)\cup C=A\cup (B\cup C)$

Kommutativität

Beim Durchschnitt $\cap$ und bei der Vereinigung $\cup$ kannst du die Seiten vertauschen.

• $A\cap B=B\cap A$
• $A\cup B=B\cup A$

Idempotenz

Verknüpfst du eine Menge mit sich selbst, ändert sich nichts.

• $A\cap A=A$
• $A\cup A=A$

Neutrales Element

Die Allklasse $𝒱$ ist ein neutrales Element für den Durchschnitt $\cap$, die leere Menge $\varnothing$ ist ein neutrales Element für die Vereinigung $\cup$.

• $A\cap 𝒱=A$
• $A\cup \varnothing =A$

Extremwerte

Bezüglich der Teilmengen-Beziehung $\subseteq$ ist die leere Menge $\varnothing$ die kleinste und die Allklasse die $𝒱$ die gröste Menge. Die Verknüpfung mit $\cap$ bzw. $\cup$ liefert daher nichts Neues.

• $A\cap \varnothing =\varnothing$
• $A\cup 𝒱=𝒱$

Distributivität

Ein Durchschnitt $\cap$ kann in eine Vereinigung "hineingezogen" werden, ebenso eine Vereinigung $\cup$ in einen Durchschnitt.

• $A\cap (B\cup C)=(A\cap B)\cup (A\cap C)$
• $A\cup (B\cap C)=(A\cup B)\cap (A\cup C)$

Regeln für das Komplement

Die Beweise findest du im Kapitel Differenz, symmetrische Differenz und Komplement.

Existenz des Komplements

Zu jeder Menge gibt es ein Komplement $\complement$.

• $A\cap A^{\complement }=\varnothing$
• $A\cup A^{\complement }=𝒱$

De Morgansche Gesetze

Das Komplement kann in einen Durchschnitt bzw. in eine Vereinigung "hereingezogen" werden.

• $(A\cap B{)}^{\complement }=A^{\complement }\cup B^{\complement }$
• $(A\cup B{)}^{\complement }=A^{\complement }\cap B^{\complement }$

Doppeltes Komplement

Ein doppeltes Komplement entfällt.

• $(A^{\complement }{)}^{\complement }=A$

Grösstes und kleinstes Element

• ${𝒱}^{\complement }=\varnothing$
• ${\varnothing }^{\complement }=𝒱$

Boolsche Algebra

Eine Struktur mit den oben aufgeführten Eigenschaften wird Boolesche Algebra genannt. Die wichtigsten Beispiele sind die Potenzmengen $M:=𝒫(G)$ einer Grundmenge $G$.

Potenzmenge

Das folgende Bild zeigt die Boolesche Algebra $𝒫(\{a,b,c\})$ mit $G=\{a,b,c\}$ und $\varnothing =\{\}$.

Boolesche Algebra $𝒫(\{a,b,c\})$ - die Pfeile zeigen die Teilmengen-Beziehung

Aussagenlogik

In den Beweisen für die Mengengesetze haben wir immer wieder auf die Gesetze der Aussagenlogik zurückgegriffen. Das ist kein Zufall, sondern liegt daran, dass die Aussagenlogik ebenfalls eine Boolesche Algebra bilden.

A	B	A $\wedge$ B	A $\vee$ B	$\mathrm{\neg }$ A
W	W	W	W	F
W	F	F	W	W
F	W	F	W
F	F	F	F

Die Boolesche Algebra mit zwei Elementen gibt nicht nur die Struktur der Aussagenlogik wieder, sondern spielt auch in der Informatik als Schaltagebra eine wichtige Rolle.

Definition

Nun ist es mühsam, alle in diesem Kapitel aufgeführten Eigenschaften nachzuprüfen, um zu zeigen, dass eine Struktur eine Boolesche Algebra ist. Zum Glück ist das auch nicht nötig, denn aus einigen Regeln können die anderen Regeln hergeleitet werden. Die Regeln, die zugrunde gelegt werden heißen Axiome. Ein häufig verwendetes Axiomensystem für Boolesche Algebren stammt vom amerikanischen Mathematiker Edward Huntington aus dem Jahre 1904. Um deutlich zu machen, dass hier eine allgemeine Struktur gemeint ist, benutzen wir neue Symbole für die Verknüpfungen, nämlich $\sqcap$, $\bigsqcup$ und $\sim$, und bezeichnen die neutralen Elemente mit $\mathrm{\top }$ und $\mathrm{\perp }$.

Wie wir gesehen haben, gibt es sehr verschiedene Booleschen Algebren. Werfen wir noch einmal einen Blick auf unsere Beispiele und vergleichen die beiden folgenden Boolschen Algeben;

• Die Boolesche Algebra der Aussagenlogik hat genau zwei Elemente.
• Sei $G$ die einelementige Grundmenge $G:=\{\varnothing \}$. Dann hat die Boolesche Algebra der Potenzmenge $𝒫(G)=\{\varnothing ,G\}$ ebenfalls genau zwei Elemente, nämlich die leere Menge $\varnothing$ und die Grundmenge $G$.

Der Vergleich zeigt folgende Entsprechungen:

Menge:	$\{𝖶,𝖥\}$	$\{\varnothing ,G\}$
Verknüpfungen:	Konjunktion $\wedge$	Durchschnitt $\cap$
	Disjunktion $\vee$	Vereinigung $\cup$
	Negation $\mathrm{\neg }$	Komplement $\complement$
Neutrale Elemente:	Wahr $𝖶$	Grundmenge $G$
	Falsch $𝖥$	Leere Menge $\varnothing$

Ersetzen wir nun in irgendeiner Regel die Verknüpfungen und Elemente der Booleschen Algebra der Aussagenlogik durch die entsprechenden Verknüpfungen der Booleschen Algebra der Potenzmenge, so gilt dort die Regel ganz genauso! Beispiel: Aus $a\vee (a\wedge 𝖶)=a$ entsteht so $a\cup (a\cap G)=a$.

Betrachten wir nun das dritte Beispiel, den Teilerverband. Auch hier fällt auf, dass unser konkretes Beispiel 210 genau 16 Elemente hat, also genauso viele wie die Potenzmenge einer Menge mit vier Elementen. Wir erstellen daher für alle hier behandelten Booleschen Algebren eine Übersetzungstabelle:

	Allgemein	Aussagenlogik	Teilerverband	Potenzmenge
Menge:	$\{\mathrm{\top },\cdots ,\mathrm{\perp }\}$	$\{𝖶,𝖥\}$	$\{1,\cdots ,n\}$	$\{\varnothing ,\cdots ,G\}$
Verknüpfungen:	$\sqcap$	$\wedge$	$kgV$	$\cap$
	$\bigsqcup$	$\vee$	$ggT$	$\cup$
	$\sim$	$\mathrm{\neg }$	$\bar{x}$	$\complement$
Neutrale Elemente:	$\mathrm{\top }$	$𝖶$	$n$	$G$
	$\mathrm{\perp }$	$𝖥$	$1$	$\varnothing$

Wenn wir solche Übersetzungstabellen erstellen können und bei der Übersetzung wahre Aussagen in wahre, und falsche Aussagen in falsche übergehen, werden die beiden verglichenen Strukturen isomorph (d.h. strukturgleich) genannt. Dabei müssen nicht nur die neutralen Elemente einander entsprechen, sondern alle Elemente der einen Struktur müssen genau einem Element der anderen Struktur entsprechen und umgekehrt. Wir werden das im Kapitel Abbildung, Funktion genauer ausführen. Zwei isomorphe Strukturen sind bis auf Umbenennungen gleich!

Für Boolesche Strukturen gilt nun folgender eigentlich erstaunlicher Satz:

Den Beweis wollen wir hier nicht führen, da wir dazu noch einiges an Definitionen und Hilfsmitteln bräuchten.

{{#invoke:Mathe für Nicht-Freaks/Seite|unten}}