• Martin Thoma
  • Home
  • Categories
  • Tags
  • Archives
  • Support me

Beweise aus der booleschen Algebra

Contents

  • Beweise aus der booleschen Algebra
    • Definition
    • Folgerungen
      • Eindeutigkeit des Nullelements
      • Eindeutigkeit des Einselements
      • Eindeutigkeit der komplementären Elemente
      • Nullelement ungleich Einselement
      • Extremalgesetze
      • Absorptionsgesetz
    • Körper
    • Boolesche Algebren und die Schaltalgebra
    • Quellen

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!

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

Published

Nov 8, 2012
by Martin Thoma

Category

German posts

Tags

  • Boolean algebra 2
  • mathematics 59

Contact

  • Martin Thoma - A blog about Code, the Web and Cyberculture
  • E-mail subscription
  • RSS-Feed
  • Privacy/Datenschutzerklärung
  • Impressum
  • Powered by Pelican. Theme: Elegant by Talha Mansoor