Boolesche Algebra

In der Mathematik ist eine boolesche Algebra eine spezielle algebraische Struktur, die die Eigenschaften der logischen Operatoren UND, ODER, NICHT sowie die Eigenschaften der mengentheoretischen Verknüpfungen Durchschnitt, Vereinigung, Komplement verallgemeinert. Gleichwertig zu booleschen Algebren sind boolesche Ringe, die von UND und ENTWEDER-ODER beziehungsweise Durchschnitt und symmetrischer Differenz ausgehen.

Operatoren:                        ∧  UND                       ∨ ODER              ¬  NICHT 

Die Operatoren boolescher Algebren werden verschiedenartig notiert. Bei der logischen Interpretation als Konjunktion, Disjunktion und Negation schreibt man sie als UND, ODER, NICHT bzw. AND, OR, NOT und kürzt sie mit  ∧ , ∨ sowie ¬  ab. Bei der mengentheoretischen Interpretation als Durchschnitt, Vereinigung und Komplement werden sie als ∩, ∪  geschrieben. In Schaltkreisen benutzt man oft die definierbaren Verknüpfungen NAND (NOT AND), NOR (NOT OR) und XOR (ENTWEDER-ODER).

Geschichtliche Basis

Die boolesche Algebra ist nach George Boole benannt, da sie auf dessen Logikkalkül von 1847 zurückgeht, in dem er erstmals algebraische Methoden in der Klassenlogik und Aussagenlogik anwandte. Ihre heutige Form verdankt sie der Weiterentwicklung durch Mathematiker wie z.B. John Venn, W. Stanley Jevons, Charles Peirce, Ernst Schröder und Giuseppe Peano. In Booles originaler Algebra entspricht die Multiplikation dem UND, die Addition dagegen weder dem exklusiven ENTWEDER-ODER noch dem inklusiven ODER ("mindestens eines von beiden ist wahr"). Die genannten Boole-Nachfolger gingen dagegen vom inklusiven ODER aus: Schröder entwickelte 1877 das erste formale Axiomensystem einer booleschen Algebra in additiver Schreibweise, Peano brachte es 1888 in die heutige Form (siehe unten) und führte dabei die Symbole ∩ und ∪ ein. Das aussagenlogische ODER-Zeichen ∨ stammt aus den Principia Mathematica von Russell/Whitehead 1910; Arend Heyting führte 1930 die Symbole ∧  und ¬ ein. Den Namen „boolesche Algebra“ bzw. „boolean algebra“ prägte Henry Maurice Sheffer erst 1913. Das exklusive ENTWEDER-ODER, das Booles originaler Algebra näher kommt, legte erst Ivan Ivanovich Žegalkin 1927 dem booleschen Ring zugrunde, dem Marshall Harvey Stone 1936 den Namen gab. 1940 benutzte Claude Shannon boolesche Algebren erstmals zur Beschreibung elektrischer Schaltungen.

Definition

Eine boolesche Algebra ist ein distributiver komplementärer Verband.

Diese Definition geht nur von den Verknüpfungen ∧ und ∨ aus und umfasst die Existenz von 0, 1 und ¬ und die unabhängigen Axiome (i)(i’)(ii)(ii’)(xi)(xi’)(iv)(ix)(ix’) des gleichwertigen redundanten Peano-Axiomensystems mit zusätzlichen ableitbaren Axiomen; dieses charakterisiert eine boolesche Algebra als Menge mit Nullelement 0 und Einselement 1, auf der die zweistelligen Verknüpfungen ∧  und ∨ und eine einstellige Verknüpfung ¬ definiert sind, durch folgende Axiome (originale Nummerierung von Peano):

Jede Formel in einer booleschen Algebra hat eine duale Formel, die durch Ersetzung von 0 durch 1 und ∧ durch ∨ und umgekehrt entsteht. Ist die eine Formel gültig, dann ist es auch ihre duale Formel, wie im Peano-Axiomensystem.

Es sollte beachtet werden, dass die Komplemente nichts mit inversen Elementen zu tun haben, denn die Verknüpfung eines Elementes mit seinem Komplement liefert das neutrale Element der anderen Verknüpfung.

Auf einer booleschen Algebra ist wie in jedem Verband durch  a < b <==> a = a ∧ b  eine partielle Ordnung definierbar; bei ihr haben je zwei Elemente ein Supremum und ein Infimum. Bei der mengentheoretischen Interpretation ist  ≤  gleichbedeutend zur Teilmengenordnung  ⊆.

Boolesche Ringe

Als boolesche Ringe gelten seit Stone alle kommutative Ringe mit Einselement, die zusätzlich das Idempotenzgesetz  a · a = a  erfüllen. Die Addition im booleschen Ring entspricht bei der mengentheoretischen Interpretation der symmetrischen Differenz und bei aussagenlogischer Interpretation der Alternative "entweder...oder" (XOR); die Multiplikation entspricht der Durchschnittsbildung beziehungsweise der Konjunktion UND.

Boolesche Ringe sind stets selbstinvers, denn es gilt  a + a = 0  und  --a = a  . Daher besitzen sie, falls 1 und 0 verschieden sind, stets die Charakteristik 2. Der kleinste solche boolesche Ring ist zugleich ein Körper mit folgenden Verknüpfungstafeln:

Der Potenzreihen-Ring über diesem Körper ist ebenfalls ein boolescher Ring. Die Kategorien boolescher Ringe und boolescher Algebren sind isomorph. Denn jeder boolesche Ring   (R, + ,∙ , 1, 0) wird zu einer booleschen Algebra (R, ∧, ∨, ¬, 1 , 0 )  durch folgende Definitionen:

x ∨ y = x + y + xy

x ∧ y = xy

¬ x = x + 1

Umgekehrt wird jede boolesche Algebra (A, ∧, ∨, ¬, 1 , 0 ) zu einem booleschen Ring (A, + ,∙ , 1, 0) durch folgende Definitionen:

a + b = (a ∧¬b) ∨(b ∧¬a)

  a · b = a ∧ b

Ferner ist eine Abbildung f : A → B genau dann ein Homomorphismus boolescher Algebren, wenn sie ein Homomorphismus boolescher Ringe ist.

Homomorphismen

Ein Homomorphismus zwischen booleschen Algebren A,B ist ein Verbandshomomorphismus  f : A → B, der 0 auf 0 und 1 auf 1 abbildet, d.h. für alle gilt:

• f  (x ∧y) = f (x) ∧ f (y)
• f  (x ∨y) = f (x) ∨f (y)
• f  (0) = 0  ,   f  (1) = 1

Es folgt daraus, dass  f (¬a) = ¬f (a) für alle a aus A. Die Klasse aller booleschen Algebren wird mit diesem Homomorphismenbegriff eine Kategorie. Ist ein Homomorphismus f zusätzlich bijektiv, dann heißt f Isomorphismus, und A und B heißen isomorph.

Beispiele (aus gängiger Literatur)

Zweielementige boolesche Algebra

Die wichtigste boolesche Algebra hat nur die zwei Elemente 0 und 1. Die Verknüpfungen sind wie folgt definiert :

Diese Algebra hat Anwendungen in der Logik, wo 0 als „falsch“ und 1 als „wahr“ interpretiert werden. Die Verknüpfungen ∧ , ∨ ,  ¬ entsprechen den logischen Verknüpfungen UND, ODER, NICHT. Ausdrücke in dieser Algebra heißen boolesche Ausdrücke.

Auch für digitale Schaltungen wird diese Algebra verwendet. Hier entsprechen 0 und 1 zwei Spannungszuständen. Das Eingangs-Ausgangs-Verhalten jeder möglichen digitalen Schaltung kann durch einen booleschen Ausdruck modelliert werden.

Die zweielementige boolesche Algebra ist auch wichtig für die Theorie allgemeiner boolescher Algebren, da jede Gleichung, in der nur Variablen, 0 und 1 durch ∧ , ∨ sowie ¬ verknüpft sind, genau dann in einer beliebigen booleschen Algebra für jede Variablenbelegung erfüllt ist, wenn sie in der zweielementigen Algebra für jede Variablenbelegung erfüllt ist (was man einfach durchtesten kann). Zum Beispiel gelten die folgenden beiden Aussagen (Konsensusregeln, engl.: Consensus Theorems) über jede boolesche Algebra:

(a ∨ b) ∧(¬a ∨ c) ∧ (b ∨ c) = (a ∨ b) ∧(¬a ∨ c)

(a ∧ b) ∨ (¬a ∧ c) ∨ (b ∧ c) = (a ∧ b) ∨ (¬a ∧ c)

In der Aussagenlogik werden diese Regeln Resolutionsregeln genannt.

Mengenalgebra

Die Potenzmenge P(S) einer Menge S wird mit Durchschnitt und Vereinigung zu einer booleschen Algebra. Dabei ist 0 die leere Menge und 1=S und die Negation das Komplement; der Sonderfall S=0 ergibt die einelementige Potenzmenge mit 1=0. Auch jeder S enthaltende, bezüglich Vereinigung und Komplement abgeschlossene Teilbereich der Potenzmenge von S ist eine boolesche Algebra, die als Teilmengenverband oder Mengenalgebra bezeichnet wird. Der Darstellungssatz von Stone besagt, dass jede boolesche Algebra isomorph (s.u.) zu einer Mengenalgebra ist. Daraus folgt, dass die Mächtigkeit jeder endlichen booleschen Algebra eine Zweierpotenz ist.

Weitere Beispiele

Die Menge aller endlichen oder ko-endlichen Teilmengen von  N° bildet mit Durchschnitt und Vereinigung eine boolesche Algebra.

Für jede natürliche Zahl n ist die Menge aller positiven Teiler von n mit den Verknüpfungen ggT und kgV ein distributiver beschränkter Verband. Dabei ist 1 das Nullelement und n das Einselement. Der Verband ist boolesch genau dann, wenn n quadratfrei ist. Dieser Verband heißt Teilerverband von n.

Für jeden topologischen Raum X ist die Menge aller offenen abgeschlossenen Teilmengen eine boolesche Algebra mit Durchschnitt und Vereinigung.

Ist R ein Ring mit Einselement, dann definieren wir die Menge

    A = { e ∈ R |  e² = e und ex = xe für alle x ∈ R }

aller idempotenten Elemente des Zentrums. Mit den Verknüpfungen

    e ∨ f = e + f - ef ,  e ∧ f = ef

wird A zu einer booleschen Algebra.