Boolesche Algebren (George Boole)

Ein distributiver komplementärer Verband $(V,$ ,,o,e,') heißt eine Boolesche Algebra. In jeder Booleschen Algebra gelten die De Morganschen Gesetze ( Augustus De Morgan) für alle $a, b$ aus $V$

(1)

(a

b)' = a'

und

(2)

(a

b)' = a'

b'.

Zunächst folgt in jedem komplementären Verband aus $(x')' = x$ nämlich, daß (1) und (2) äquivalent sind, denn aus (1) folgt $(a'$ b')' = a'' b'' = a b und daraus $a'$ b' = (a b)', also (2). Die Umkehrung ergibt sich analog. Daher genügt es, etwa (1) mit Hilfe der Eindeutigkeit des Komplementes und der Distributivgesetze zu bestätigen, d. h. man zeigt $(a$ b) (a' b') = o und $(a$ b) (a' b') = e.

Zum Nachweis, daß es sich bei einer algebraischen Struktur $(V,$ ,,o,e,') um eine Boolesche Algebra handelt, reicht es, die folgenden Axiome für alle $a, b, c$ aus $V$ nachzurechnen, die ein minimales Axiomensystem für Boolesche Algebren darstellen.

a b = b a	a b = b a
a e = a	a o = a
a (b c) = (a b) (a c)	a (b c) = (a b) (a c)
a a' = e	a a' = o

Zunächst läßt sich die Idempotenz von nachweisen: $a = a$ o = a (a a') = (a a) (a a') = (a a) e = a a. Durch Dualisieren, d. h. durch Vertauschen von und sowie von $e$ und $o$ erhält man hieraus einen Beweis der Idempotenz von . Das liegt daran, daß das angegebene Axiomensystem bei diesen Vertauschungen unverändert bleibt. Übrigens wurde bisher von der Kommutativität der Operationen noch kein Gebrauch gemacht.

Jetzt rechnet man die absorbierenden Eigenschaften von $o$ in $(V,$ ) nach: $o = a$ a' = a (a' o) = (a a') (a o) = o (a o) = a o. Durch Dualisieren erhält man hieraus $a$ e = e.

Jetzt lassen sich die Absorptionsgesetze zeigen: $a = a$ o = a (b o) = (a b) (a o) = (a b) a = a (a b) und dual $a = a$ (a b).

Nun kann man zeigen, daß die einstellige Verknüpfung $' : V -> V$ eine Involution ist: $(a')' = e$ (a')' = (a a') (a')' = (a (a')') (a' (a')') = a (a')' = (a a') (a (a')') = a (a' (a')') = a. Damit folgt aus $o' = o$ o' = e sofort $e' = (o')' = o$ und dual $o' = e$ .

Man beachte, daß sämtliche bisherigen Beweise ohne die Benutzung von Assoziativgesetzen erfolgten!

Es bleibt also schließlich wegen des Dualitätsprinzips noch der Nachweis eines Assoziativgesetzes übrig. Zunächst gilt $a$ ((a b) c) = (a (a b)) (a c) = a (a c) = a = a (a (b c). Weiterhin hat man $a'$ ((a b) c) = (a' (a b)) (a' c) = ((a' a) (a' b)) (a' c) = (a' b) (a' c) = a' (b c) = (a' a) (a' (b c)) = a' (a (b c)). Verknüpft man nun jeweils beide Seiten dieser zwei Gleichungen mit , so erhält man wegen der Distributivgesetze $(a$ a') ((a b) c) = (a a') (a (b c). Wegen $(a$ a') = o folgt hieraus aber das Assoziativgesetz für .

Damit handelt es sich bei $(V,$ ,) tatsächlich um einen distributiven Verband, der durch $o$ und $e$ beschränkt ist und in dem $' : V -> V$ eine eindeutige Komplementbildung definiert. Insbesondere erfüllt die Komplementbildung auch die De Morganschen Gesetze.

Beispiele für Boolesche Algebren

Der Boolesche Halbring ist eine Boolesche Algebra. Diese ergibt sich auch aus dem folgenden Beispiel für den Spezialfall einer einelementigen Menge $X$ .

Für jede Menge $X$ ist die Potenzmenge P(X), also die Menge aller Teilmengen von $X$ eine Boolesche Algebra $($ P(X),,,{ },X,'). Dabei ist $A$ B der mengentheoretische Durchschnitt, $A$ B die mengentheoretische Vereinigung, die leere Menge { } das kleinste Element, die Menge $X$ das größte Element und $A' = X \ A = { x aus X | x nicht aus
A }$ das mengentheoretische Komplement für alle Teilmengen $A$ und $B$ von $X$ . (Diese Beispiele sind in gewisser Weise charakteristisch: Zu jeder endlichen Booleschen Algebra $B$ gibt es eine Menge $X$ , so daß $B$ zu P(X) isomorph ist.)

Für die abzählbare Menge $N$ ₀ der natürlichen Zahlen ist $B = { X aus$ P(N₀) | X endlich oder N₀ \ X endlich } eine Boolesche Algebra. (Man kann zeigen, daß $B$ zu keiner Booleschen Algebra P(X) für eine beliebige Menge $X$ isomorph ist.)