Boolesche Algebra

Grundidee und Bedeutung

Eine boolesche Algebra ist eine algebraische Struktur, die logische und mengentheoretische Verknüpfungen verallgemeinert. Ihre Grundoperationen sind UND (Konjunktion, ∧), ODER (Disjunktion, ∨) und NICHT (Negation, ¬). In der Mengenlehre entsprechen ihnen Durchschnitt (∩), Vereinigung (∪) und Komplement. Gleichwertig lassen sich boolesche Algebren als boolesche Ringe beschreiben, deren grundlegende Operationen UND und ENTWEDER-ODER (XOR) beziehungsweise Durchschnitt und symmetrische Differenz sind.

Boolesche Algebra ist eine Grundlage digitaler Elektronik: Als Schaltalgebra beschreibt und vereinfacht sie Schaltnetze. Sie wird außerdem in modernen Programmiersprachen, der Aussagenlogik, der Mengenlehre und der Statistik verwendet.

Die heutige Theorie geht auf George Booles Logikkalkül von 1847 zurück. Ein erstes formales Axiomensystem entwickelte Ernst Schröder 1877; Giuseppe Peano brachte es 1888 in die heutige Form. Henry Maurice Sheffer prägte 1913 den Namen „boolesche Algebra“. Ivan Ivanovich Žegalkin legte 1927 das exklusive ODER einem booleschen Ring zugrunde, dem Marshall Harvey Stone 1936 seinen Namen gab.

Definition und Rechengesetze

Eine boolesche Algebra besteht aus einer Menge mit den besonderen Elementen 0 und 1, zwei zweistelligen Verknüpfungen ∧ und ∨ sowie der einstelligen Verknüpfung ¬. Für alle Elemente a, b und c gelten insbesondere:

• Kommutativität: a ∧ b = b ∧ a und a ∨ b = b ∨ a.

• Assoziativität: (a ∧ b) ∧ c = a ∧ (b ∧ c) und (a ∨ b) ∨ c = a ∨ (b ∨ c).

• Idempotenz: a ∧ a = a und a ∨ a = a.

• Distributivität: a ∧ (b ∨ c) = (a ∧ b) ∨ (a ∧ c) und a ∨ (b ∧ c) = (a ∨ b) ∧ (a ∨ c).

• Neutralität und Extremalgesetze: a ∧ 1 = a, a ∨ 0 = a, a ∧ 0 = 0 und a ∨ 1 = 1.

• Doppelnegation: ¬(¬a) = a.

• De Morgansche Gesetze: ¬(a ∧ b) = ¬a ∨ ¬b und ¬(a ∨ b) = ¬a ∧ ¬b.

• Komplementär- und Dualitätsgesetze: a ∧ ¬a = 0, a ∨ ¬a = 1, ¬0 = 1 und ¬1 = 0.

• Absorption: a ∨ (a ∧ b) = a und a ∧ (a ∨ b) = a.

Jede gültige Formel besitzt eine ebenfalls gültige duale Formel. Sie entsteht, indem gleichzeitig 0 und 1 sowie ∧ und ∨ vertauscht werden. Ein Komplement ist kein inverses Element: Die Verknüpfung eines Elements mit seinem Komplement ergibt das neutrale Element der jeweils anderen Operation.

Gleichwertig ist eine boolesche Algebra ein distributiver komplementärer Verband. Ein Verband ist eine geordnete Struktur, in der je zwei Elemente ein Infimum und ein Supremum besitzen. Die partielle Ordnung wird durch a ≤ b genau dann, wenn a = a ∧ b, definiert. Bei Mengen ist dies die Teilmengenordnung ⊆.

Das kompaktere Axiomensystem nach Huntington verlangt nur Kommutativität, Distributivität, neutrale Elemente 0 und 1 sowie zu jedem a ein Komplement ¬a. Daraus folgen alle weiteren genannten Gesetze. Auch die Eindeutigkeit von 0, 1 und des jeweiligen Komplements lässt sich daraus ableiten.

Grundlegende Beispiele

Die wichtigste boolesche Algebra ist die zweielementige Algebra {0, 1}. In der Aussagenlogik bedeutet 0 „falsch“ und 1 „wahr“. Für UND gilt: Das Ergebnis ist nur bei 1 ∧ 1 gleich 1, sonst 0. Für ODER gilt: Das Ergebnis ist nur bei 0 ∨ 0 gleich 0, sonst 1. Die Negation vertauscht die Werte: ¬0 = 1 und ¬1 = 0. Aus diesen Operationen aufgebaute Terme heißen boolesche Ausdrücke.

In der Schaltalgebra stehen 0 und 1 für zwei Spannungszustände beziehungsweise AUS und AN. Das Eingangs-Ausgangs-Verhalten jeder möglichen digitalen Schaltung lässt sich durch einen booleschen Ausdruck modellieren. Neben UND, ODER und NICHT verwendet man häufig NAND (NOT AND), NOR (NOT OR) und XOR (EXCLUSIVE OR).

Die zweielementige Algebra genügt außerdem zum Prüfen allgemeiner Gleichungen: Eine Gleichung aus Variablen, 0, 1, ∧, ∨ und ¬ gilt bei jeder Belegung in jeder booleschen Algebra genau dann, wenn sie bei jeder Belegung in der zweielementigen Algebra gilt.

Ein zweites zentrales Beispiel ist die Potenzmenge einer Menge S. Mit Durchschnitt, Vereinigung und Aᶜ := {x | (x ∈ S) ∧ (x ∉ A)} bildet sie eine boolesche Algebra. Dabei ist 0 die leere Menge ∅ und 1 die Gesamtmenge S. Für S = ∅ entsteht die einelementige Algebra mit 1 = 0. Auch ein Teilbereich der Potenzmenge, der S enthält und unter Vereinigung und Komplement abgeschlossen ist, heißt Mengenalgebra. Venn-Diagramme veranschaulichen hier unter anderem Distributiv- und de-Morgansche Gesetze; KV-Diagramme dienen zur systematischen Vereinfachung boolescher Ausdrücke.

Weitere Beispiele sind die Algebra aller endlichen oder koendlichen Teilmengen von ℕ₀ sowie der Teilerverband einer natürlichen Zahl n mit ggT und kgV. Dieser Teilerverband ist genau dann boolesch, wenn n quadratfrei ist. Für einen Ring R mit Eins bilden außerdem die zentralen idempotenten Elemente e mit e² = e eine boolesche Algebra, wenn e ∨ f = e + f − ef und e ∧ f = ef gesetzt wird.

Abbildungen, Ringe und Darstellung

Ein Homomorphismus f: A → B ist eine strukturerhaltende Abbildung zwischen booleschen Algebren. Für alle x, y ∈ A gilt f(x ∧ y) = f(x) ∧ f(y), f(x ∨ y) = f(x) ∨ f(y), f(0) = 0 und f(1) = 1. Daraus folgt f(¬a) = ¬f(a). Ist f zusätzlich bijektiv, heißt sie Isomorphismus; dann heißen A und B isomorph, besitzen also dieselbe algebraische Struktur.

Ein boolescher Ring ist ein Ring mit Einselement, in dem jedes Element idempotent ist: a · a = a. Jeder solche Ring ist kommutativ. Seine Multiplikation entspricht UND beziehungsweise dem Durchschnitt; seine Addition entspricht XOR beziehungsweise der symmetrischen Differenz. Es gilt stets a + a = 0 und daher −a = a. Sind 0 und 1 verschieden, hat der Ring die Charakteristik 2.

Jeder boolesche Ring wird durch x ∨ y = x + y + xy, x ∧ y = xy und ¬x = x + 1 zu einer booleschen Algebra. Umgekehrt wird jede boolesche Algebra durch a + b = (a ∧ ¬b) ∨ (b ∧ ¬a), −a = a und a · b = a ∧ b zu einem booleschen Ring. Eine Abbildung ist genau dann ein Homomorphismus boolescher Algebren, wenn sie ein die Eins erhaltender Ringhomomorphismus der zugehörigen booleschen Ringe ist.

Der Darstellungssatz von Stone besagt, dass jede boolesche Algebra als Algebra abgeschlossener offener Mengen eines geeigneten Stone-Raums realisiert werden kann. Ein Stone-Raum ist ein total unzusammenhängender, kompakter Hausdorffraum. Gleichwertig ist jede boolesche Algebra isomorph zu einer Mengenalgebra. Daraus folgt insbesondere, dass die Mächtigkeit jeder endlichen booleschen Algebra eine Zweierpotenz ist. Der Satz liefert darüber hinaus eine kontravariante Äquivalenz zwischen Stone-Räumen mit stetigen Abbildungen und booleschen Algebren mit Homomorphismen: Eine stetige Abbildung f: X → Y überführt abgeschlossene offene Mengen aus Y durch Urbildbildung in solche aus X.

Freie boolesche Algebra

Eine freie boolesche Algebra wird allein durch eine Menge X von Erzeugern, die Basis, bestimmt und besitzt außer den Gesetzen der booleschen Algebra keine zusätzlichen Beziehungen. Formal sei BoolAlg die Kategorie der booleschen Algebren, V: BoolAlg → Set der Vergissfunktor, A eine boolesche Algebra und i: X → V(A) injektiv. Das Paar (A, i) heißt frei über X, wenn folgende universelle Eigenschaft gilt: Für jede boolesche Algebra B und jede Abbildung f: X → V(B) existiert genau ein Homomorphismus g: A → B mit f = V(g) ∘ i. Jede beliebige Zuordnung der Basiselemente zu Elementen einer anderen booleschen Algebra lässt sich somit eindeutig zu einem Homomorphismus fortsetzen. Der zugehörige linksadjungierte Funktor W: Set → BoolAlg heißt freier Funktor.