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:
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:
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:
Schritt 2
Außerdem gilt:
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!
Quellen
- Skript „Technische Informatik - Digitaltechnik und Entwurfsverfahren“ von Dr.-Ing. Tamim Asfour. S.33 - 37
- Folien von Dr.-Ing. Tamim Asfour
- Vorlesung von Dr.-Ing. Tamim Asfour