Definition
Edward Vermilye Huntington hat eine sehr kompakte Definition boolescher Algebren erarbeitet:
Sei $B$ eine Menge und $\sqcap: B \times B \rightarrow B$ sowie $\sqcup: B \times B \rightarrow B$ Verknüfungen auf B.
Weiter gelte:
H1: Kommutativgesetze
- $\forall a,b \in B: a \sqcap b = b \sqcap a$
- $\forall a,b \in B: a \sqcup b = b \sqcup a$
H2: Distributivgesetze
- $\forall a,b,c \in B: a \sqcap (b \sqcup c) = (a \sqcap b) \sqcup (a \sqcap c)$
- $\forall a,b,c \in B: a \sqcup (b \sqcap c) = (a \sqcup b) \sqcup (a \sqcap c)$
H3: Neutrale Elemente
- $\exists e \in B \forall a \in B: a \sqcap e = a$ (e wird Einselement genannt)
- $\exists n \in B \forall a \in B: a \sqcup n = a$ (n wird Nullelement genannt)
H4: Komplementäre Elemente
- $\forall a \in B: \exists \bar a: a \sqcap \bar a = n \land a \sqcup \bar a = e$
Dann wird $(B, \sqcap, \sqcup)$ eine boolesche Algebra gennant.
Folgerungen
Sei im folgendem immer $\mathcal{B} = (B, \sqcap, \sqcup)$ eine boolesche Algebra mit dem Einselement „1“ und dem Nullelement „0“.
Eindeutigkeit des Nullelements
Behauptung: Es exisitiert genau ein Nullelement für $\mathcal{B}$.
Beweis: direkt
Die Existenz von mindestens einem Nullelement wird durch H3 garantiert.
Seien $n_1, n_2$ Nullelemente auf $\mathcal{B}$. Dann gilt:
\begin{align} & \forall a \in B: a \sqcup n_1 \stackrel{H3}{=} a\ \Rightarrow & n_2 \sqcup n_1 = n_2\ \stackrel{H3}{\Rightarrow} & n_1 = n_2 \blacksquare \end{align}
Eindeutigkeit des Einselements
Behauptung: Es exisitiert genau ein Einselement für $\mathcal{B}$.
Beweis: direkt
Die Existenz von mindestens einem Einselement wird durch H3 garantiert.
Seien $e_1, e_2$ Einselemente auf $\mathcal{B}$. Dann gilt:
\begin{align} & \forall a \in B: a \sqcap e_1 \stackrel{H3}{=} a\ \Rightarrow & e_2 \sqcup e_1 = e_2\ \stackrel{H3}{\Rightarrow} & e_1 = e_2 \blacksquare \end{align}
Eindeutigkeit der komplementären Elemente
Behauptung: Die komplementären Elemente bzgl. $\sqcup$ sind eindeutig
Beweis: direkt
Sei $a \in B$ beliebig und es gelte:
$a \sqcup \bar a_1 = 0$ und $a \sqcup \bar a_2 = 0$ sowie
$a \sqcap \bar a_1 = 1$ und $a \sqcap \bar a_2 = 1$
Schritt 1
Es gilt:
\begin{align} \bar a_1 \sqcap (a \sqcup \bar a_2) &\stackrel{H2}{=} (\bar a_1 \sqcap a) \sqcup (\bar a_1 \sqcap \bar a_2)\ \Leftrightarrow \bar a_1 \sqcap 1 &= 0 \sqcup (\bar a_1 \sqcap \bar a_2)\ \Leftrightarrow \bar a_1 &= \bar a_1 \sqcap \bar a_2 \end{align}
Schritt 2
Außerdem gilt:
\begin{align} \bar a_2 \sqcap (a \sqcup \bar a_1) &\stackrel{H2}{=} (\bar a_2 \sqcap a) \sqcup (\bar a_2 \sqcap \bar a_1)\ \Leftrightarrow \bar a_2 \sqcap 1 &= 0 \sqcup (\bar a_2 \sqcap \bar a_1)\ \Leftrightarrow \bar a_2 &= (\bar a_2 \sqcap \bar a_1) \stackrel{H1}{=} \bar a_1 \sqcap \bar a_2 \end{align}
Aus den Ergebnissen von Schritt 1 und Schritt 2 folgt: $\bar a_1 = \bar a_2$.
Das bedeutet, zu jedem $a \in B$ existiert genau ein Komplement. $\blacksquare$
Nullelement ungleich Einselement
Behauptung: $0 \neq 1$
Beweis:
Wegen (H3) und (H4) gilt:
- $\exists 1 \in B \forall a \in B: a \sqcap 1 \stackrel{H1}{=} 1 \sqcap a = a$
- $\exists 0 \in B \forall a \in B: a \sqcup 0 \stackrel{H1}{=} 0 \sqcup a = a$
- $\forall a \in B: \exists \bar a \in B: a \sqcap \bar a \stackrel{H1}{=} 0$
- $\forall a \in B: \exists \bar a \in B: a \sqcup \bar a \stackrel{H1}{=} 1$
Annahme: 1 = 0
$\Rightarrow \forall a \in B: \exists \bar a \in B = a \sqcap \bar a = a \sqcup \bar a = 0 = 1$
Hmmm ... irgendwie konnte man $(0 = 1) \Rightarrow (\sqcap = \sqcup)$ zeigen ... aber wie genau?
Extremalgesetze
$\forall a \in B: 1 \sqcup a = 1$ $\forall a \in B: 0 \sqcap a = 0$
Wie beweist man das?
Absorptionsgesetz
Version 1
Voraussetzungen: Sei $\mathcal{B} = (B, \sqcap, \sqcup)$ eine boolesche Algebra.
Behauptung: $\forall a, b \in B: a \sqcup (a \sqcap b) = a$
Beweis: direkt
$a \sqcup (a \sqcap b) \stackrel{H3}{=} (a \sqcap 1) \sqcup (a \sqcap b) \stackrel{H3}{=} a \sqcap (1 \sqcup b) \stackrel{\text{Extremalgesetze}}{=} a \sqcap 1 \stackrel{H3}{=} a$
Version 2
Voraussetzungen: Sei $\mathcal{B} = (B, \sqcap, \sqcup)$ eine boolesche Algebra.
Behauptung: $\forall a, b \in B: a \sqcap (a \sqcup b) = a$
Beweis: Duale Aussage zu Version 1
Version 3
Voraussetzungen: Sei $\mathcal{B} = (B, \sqcap, \sqcup)$ eine boolesche Algebra.
Behauptung: $\forall a, b \in B: a \sqcup (\bar a \sqcap b) \stackrel{H2}{=} a \sqcup b$
Beweis: direkt
$a \sqcup (\bar a \sqcap b) \stackrel{H2}{=} (a \sqcup \bar a) \sqcap (a \sqcup b) \stackrel{H4}{=} 1 \sqcap (a \sqcup b) \stackrel{H3}{=} a \sqcup b \blacksquare$
Körper
Ist jede Boolesche Algebra ein Körper?
Ein Körper ist eine Menge $V$ mit zwei Verknüpfungen $\oplus, \otimes$: $(V, \oplus, \otimes)$, für den gilt:
- $(K, \oplus)$ ist abelsche Gruppe mit neutralem Element 0
- $(K \setminus \{0\}, \otimes)$ ist abelsche Gruppe mit neutralem Element 1
- Es gelten die Distributivgesetze:
- $\forall a, b, c \in V: a\cdot (b+c) = a\cdot b+a\cdot c$
- $\forall a, b, c \in V: (a+b)\cdot c= a\cdot c+b\cdot c$
Es scheint relativ offensichtlich, dass jede boolesche Algebra ein Körper ist. Allerdings muss man aufpassen. Für die neutrale Elemente eines Körpers $K = (V, \oplus, \otimes)$ muss gelten:
- $\forall a: 0 \oplus a = a$
- $\forall a: 1 \otimes a = a$
Für eine boolesche Algebra $\mathcal{B} = (B, \sqcap, \sqcup)$ muss gelten (H3):
- $\exists 1 \in B \forall a \in B: a \sqcap 1 = a$
- $\exists 0 \in B \forall a \in B: a \sqcup 0 = a$
Für die Inversen von $K$ muss gelten:
- $\forall a \exists \bar a: a \oplus \bar a = 0$
- $\forall a \exists \bar a: a \otimes \bar a = 1$
Für die Komplemente von $\mathcal{B}$ muss gelten:
- $\forall a \in B: \exists \bar a: a \sqcap \bar a = 0$
- $\forall a \in B: \exists \bar a: a \sqcup \bar a = 1$
Das Komplement eines Elements verknüfpft mit $\sqcap$ ergibt also das neutrale Element von $\sqcup$!
Offensichtlich ist, dass die Schaltalgebra mit den Operatoren XOR und AND, also $({0,1}, XOR, AND)$ ein Körper ist, da Sie offensichtlich isomorph zu $\mathbb{Z}/2\mathbb{Z}$ ist.
Behauptung: Alle booleschen Algebren mit drei oder mehr Elementen sind keine Körper
Beweis: (danke an Chricho)
Sei $\mathcal{B} = (B, \sqcap, \sqcup)$ mit $|B| \geq 3$. Sei $a \in B$ mit $0 \neq a \neq 1$.
Es gilt:
$\forall b \in B: a \land b \leq a \lneq 1 \Rightarrow a$ hat kein Inverses $\Rightarrow \mathcal{B}$ ist kein Körper $\blacksquare$
Boolesche Algebren und die Schaltalgebra
Die wohl bekannteste boolesche Algebra ist die Schaltalgebra: $({0,1}, \lor, \land, 0, 1)$
Allerdings ist nicht jede Boolesche Algebra eine Schaltalgebra!