Boolesche Algebra – Serlo „Mathe für Nicht-Freaks“

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 ${\mathcal {V}}$ 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 ${\mathcal {V}}$ ist ein neutrales Element für den Durchschnitt $\cap$, die leere Menge $\varnothing$ ist ein neutrales Element für die Vereinigung $\cup$.

• $A\cap {\mathcal {V}}=A$
• $A\cup \varnothing =A$

Extremwerte

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

• $A\cap \varnothing =\varnothing$
• $A\cup {\mathcal {V}}={\mathcal {V}}$

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)$

Beweis: Mit den Definitionen für $\cap$ und $\cup$ wird die Behauptung auf die Distributivgesetze für $\land$ und $\lor$ zurückgeführt, s. Kapitel "Gesetze der Logik".

${\begin{aligned}&A\cap (B\cup C)\\[0.3em]&{\color {OliveGreen}\left\updownarrow \ {\mathsf {Definition\;von\;\cap }}\right.}\\[0.3em]=\;&\{x\,|\,x\in A\land x\in B\cup C\}\\[0.3em]&{\color {OliveGreen}\left\updownarrow \ {\mathsf {Definition\;von\;\cup }}\right.}\\[0.3em]=\;&\{x\,|\,x\in A\land x\in \{y\,|\,y\in B\lor y\in C\}\}\\[0.3em]&{\color {OliveGreen}\left\updownarrow \ {\mathsf {Abstraktionsprinzip}}\right.}\\[0.3em]=\;&\{x\,|\,x\in A\land (x\in B\lor x\in C)\}\\[0.3em]&{\color {OliveGreen}\left\updownarrow \ {\mathsf {Distributuvit{\ddot {a}}t\;von\;\land \;und\;\lor }}\right.}\\[0.3em]=\;&\{x\,|\,(x\in A\land x\in B)\lor (x\in A\land x\in C)\}\\[0.3em]&{\color {OliveGreen}\left\updownarrow \ {\mathsf {Abstraktionsprinzip}}\right.}\\[0.3em]=\;&\{x\,|\,x\in \{y\,|\,y\in A\land y\in B\}\lor x\in \{y\,|\,y\in A\land y\in C\}\}\\[0.3em]&{\color {OliveGreen}\left\updownarrow \ {\mathsf {Definition\;von\;\cap }}\right.}\\[0.3em]=\;&\{x\,|\,x\in A\cap B\lor x\in A\cap C\}\\[0.3em]&{\color {OliveGreen}\left\updownarrow \ {\mathsf {Definition\;von\;\cup }}\right.}\\[0.3em]=\;&(A\cap B)\cup (A\cap C)\\[0.3em]\end{aligned}}$

Die zweite Behauptung wird ebenso bewiesen.

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 }={\mathcal {V}}$

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

• ${\mathcal {V}}^{\complement }=\varnothing$
• $\varnothing ^{\complement }={\mathcal {V}}$

Boolsche Algebra

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

Potenzmenge

Beispiel (Potenzmenge als Boolesche Algebra)

Die Elemente von $M$ sind alle Teilmengen einer Grundmenge $G$, formalisiert: $M:={\mathcal {P}}(G)$. Weiterhin gehören der Durchschnitt $\cap$, die Vereinigung $\cup$, das Komplement $\complement$ und die beiden ausgezeichneten Elemente $G$ und $\varnothing$ zu der Struktur.

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

Boolesche Algebra ${\mathcal {P}}(\{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.

Beispiel (Boolesche Algebra mit zwei Elementen)

Die Menge $M$ der besteht aus den beiden Wahrheitswerten ${\mathsf {W}}$ und ${\mathsf {F}}$, es gilt also: $M:=\{{\mathsf {W}},{\mathsf {F}}\}$. Die Verknüpfungen sind die Konjunktion $\land$ (und), die Disjunktion $\lor$ (oder) und die Negation $\neg$ (nicht). Die Verknüpfungen sind wie folgt festgelegt, vgl. Kapitel "Junktoren":

A	B	A $\land$ B	A $\lor$ B	$\neg$ A
W	W	W	W	F
W	F	F	W	W
F	W	F	W
F	F	F	F

Verständnisfrage: Was sind die neutralen Elemente dieser Booleschen Algebra?

Da $M$ nur zwei Elemente hat, sind es ${\mathsf {W}}$ und ${\mathsf {F}}$. Wegen $A\land {\mathsf {W}}=A$ ist ${\mathsf {W}}$ das neutrale Element zu $\land$. Und wegen $A\lor {\mathsf {F}}=A$ ist ${\mathsf {F}}$ das neutrale Element zu $\lor$.

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.

Teilerverband

Beispiel (Teilerverband)

Die Menge der positiven Teiler einer natürlichen Zahl $n$ bilden eine Boolesche Algebra, wenn in der Primzahlzerlegung von $n$ jede Primzahl höchstens einmal vorkommt. Die beiden zweistelligen Verknüpfungen sind das kleinste gemeinsame Vielfache $kgV$ mit dem neutralen Element $1$ und der größte gemeinsame Teiler $ggT$ mit dem neutralen Element $n$.

Aufgabe: Wie sieht der Teilerverband von 210 aus?

Die Elemente des Teilerverbandes von $n$ sind $\{1,2,3,5,7,6,10,14,15,21,30,35,42,70,105,210\}$. Das komplementäre Element zu einem Teiler $x$ bezeichnen wir mit ${\overline {x}}$. Es muss für alle $x$ gelten: $kgV(x,{\overline {x}})=n$ und $ggT(x,{\overline {x}})=1$. Also ist ${\overline {x}}=n:x$.

Aufgabe: Kann die Bedingung, dass in der Primzahlzerlegung von $n$ jede Primzahl höchstens einmal vorkommt, weggelassen werden? Gib ein Beispiel dafür an, dass der Teilerverband dann keine Boolesche Algebra sein muss.

Wir betrachten $n:=4$, denn das ist die kleinste Zahl, in der eine Primzahl in der Primzahlzerlegung doppelt vorkommt. Die Elemente dieses Teilerverbandes sind $\{1,2,4\}$. Das neutrale Element zu $kgV$ ist $1$, das neutrale Element zu $ggT$ ist $4$. Wir suchen das komplementäre Element ${\overline {x}}$ zu $2$. Für ${\overline {x}}$ muss gelten: $kgV(2,{\overline {x}})=4$ und $ggT(2,{\overline {x}})=1$. Aus der ersten Bedingung folgt ${\overline {x}}=4$, aber aus der zweiten ${\overline {x}}=1$. ↯ Also ist der Teilerveband von $4$ keine Boolesche Algebra!

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$, $\sqcup$ und $\sim$, und bezeichnen die neutralen Elemente mit $\top$ und $\bot$.

Warnung

In der Mathematik werden je nach Zusammenhang völlig unterschiedliche Symbole für Boolesche Algebren verwendet! Einige davon haben wir in den Beispielen bereits kennengelernt.

Definition (Boolesche Algebra)

Eine Struktur mit der Menge $M$, den 2-stelligen Verknüpfungen $\sqcap$ und $\sqcup$ auf $M$, der 1-stelligen Verknüpfung $\sim$ auf $M$ und den beiden ausgezeichneten Elementen $\top$ und $\bot$ aus $M$ heißt Boolesche Algebra, wenn für alle Elemente $a,b,c\in M$ die folgenden vier Axiome gelten:

1. Kommutativität:   $a\sqcap b=b\sqcap a$   und   $a\sqcup b=b\sqcup a$
2. Distributivität:   $a\sqcap (b\sqcup c)=(a\sqcap b)\sqcup (a\sqcap c)$   und   $a\sqcup (b\sqcap c)=(a\sqcup b)\sqcap (a\sqcup c)$
3. Neutrale Elemente:  $a\sqcap \top =a$   und   $a\sqcup \bot =a$
4. Komplementäres Element:   $a\,\sqcap \sim a=\bot$   und  $a\,\sqcup \sim a=\top$

Aufgabe: Wir betrachten die ganzen Zahlen $\mathbb {Z}$ mit der Multiplikation $\cdot$ und der Addition $+$ und den neutralen Elementen $1$ und $0$. Zeige, dass diese Struktur keine Boolesche Algebra ist. Welche Axiome werden erfüllt, welche nicht?

1. Beide Verknüpfungen sind kommutativ, denn es gilt ja: $a\cdot b=b\cdot a$ und $a+b=b+a$.
2. Es gilt bekanntlich: $a\cdot (b+c)=(a\cdot b)+(a\cdot c)$. Die duale Regel dagegen gilt nicht! Zum Beispiel gilt: $7=1+(2\cdot 3)\neq (1+2)\cdot (1+3)=12$.
3. Die Elemente $1$ und $0$ sind tatsächlich neutral: $a\cdot 1=a$ und $a+0=a$.
4. Es gibt keine komplementären Elemente! Bezeichnen wir wieder das komplementäre Element zu $x$ mit ${\overline {x}}$, dann müsste für alle $x$ gelten: $x\cdot {\overline {x}}=0$ und $x+{\overline {x}}=1$. ↯

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 ${\mathcal {P}}(G)=\{\varnothing ,G\}$ ebenfalls genau zwei Elemente, nämlich die leere Menge $\varnothing$ und die Grundmenge $G$.

Der Vergleich zeigt folgende Entsprechungen:

Menge:	$\{{\mathsf {W}},{\mathsf {F}}\}$	$\{\varnothing ,G\}$
Verknüpfungen:	Konjunktion $\land$	Durchschnitt $\cap$
	Disjunktion $\lor$	Vereinigung $\cup$
	Negation $\neg$	Komplement $\complement$
Neutrale Elemente:	Wahr ${\mathsf {W}}$	Grundmenge $G$
	Falsch ${\mathsf {F}}$	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\lor (a\land {\mathsf {W}})=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:	$\{\top ,\cdots ,\bot \}$	$\{{\mathsf {W}},{\mathsf {F}}\}$	$\{1,\cdots ,n\}$	$\{\varnothing ,\cdots ,G\}$
Verknüpfungen:	$\sqcap$	$\land$	$kgV$	$\cap$
	$\sqcup$	$\lor$	$ggT$	$\cup$
	$\sim$	$\neg$	${\overline {x}}$	$\complement$
Neutrale Elemente:	$\top$	${\mathsf {W}}$	$n$	$G$
	$\bot$	${\mathsf {F}}$	$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:

Satz (Darstellungsatz für Boolesche Algebren)

Jede Boolsche Algebra entspricht der Boolschen Algebra einer Potenzmenge. Mathematisch ausgedrückt: jede Boolesche Algebra ist zur Booleschen Algebra einer Potenzmenge isomorph.

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