Boolesche Algebra

In der Mathematik ist eine boolesche Algebra (oder ein boolescher Verband) 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 (exklusiv-ODER) beziehungsweise Durchschnitt und symmetrischer Differenz ausgehen.

Die boolesche Algebra ist die Grundlage bei der Entwicklung von digitaler Elektronik und wird dort als Schaltalgebra, etwa bei der Erstellung von Schaltnetzen, angewandt. Sie wird in allen modernen Programmiersprachen zur Verfügung gestellt und ist auch in der Satztheorie und Statistik vertreten.

Geschichte 

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 John Venn, William 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 dessen System 1888 in die heutige Form (siehe unten) und führte dabei die Symbole  und  ein. Das aussagenlogische ODER-Zeichen  stammt von Russell 1906; Arend Heyting führte 1930 die Symbole  und  ein.

Den Namen boolesche 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.

Definition 

Das redundante Axiomensystem von Peano (mit zusätzlichen ableitbaren Axiomen) 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 jeweils (n) und (n').

Die Komplemente haben nichts mit inversen Elementen zu tun, denn die Verknüpfung eines Elementes mit seinem Komplement liefert das neutrale Element der jeweils anderen Verknüpfung.

Definition als Verband 

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 (1)(1’)(2)(2’)(11)(11’)(4)(9)(9’) des gleichwertigen Axiomensystems von Peano. Auf einer booleschen Algebra ist wie in jedem Verband durch  eine partielle Ordnung definierbar; bei ihr haben je zwei Elemente ein Supremum und ein Infimum. Bei der mengentheoretischen Interpretation ist  gleichbedeutend zur Teilmengenordnung .

Definition nach Huntington 

Eine kompaktere Definition ist das Axiomensystem nach Huntington:

Eine boolesche Algebra ist eine Menge  mit zwei Verknüpfungen auf , so dass für alle Elemente ,  und  gilt:

 Kommutativität: (1) und (1’)
 Distributivität: (4) und (4’)
 Existenz neutraler Elemente: Es gibt Elemente  und , so dass (5) und (5’)
 Existenz von Komplementen: Zu jedem  gibt es , so dass (9) und (9’)

(Die manchmal separat geforderte Abgeschlossenheit der Verknüpfungen ist hier schon in der Formulierung „Verknüpfungen auf “ enthalten.)

Auch aus diesen vier Axiomen lassen sich alle oben genannten Gesetze und weitere ableiten. Auch lässt sich aus dem Axiomensystem, das zunächst nur die Existenz neutraler und komplementärer Elemente fordert, deren Eindeutigkeit ableiten, d. h., es kann nur ein Nullelement, ein Einselement, und zu jedem Element nur ein Komplement geben.

Schreibweise 

Die Operatoren boolescher Algebren werden verschiedenartig notiert. Bei der logischen Interpretation als Konjunktion, Disjunktion und Negation schreibt man sie als ,  und  und verbalisiert sie als UND, ODER, NICHT bzw. AND, OR, NOT. Bei der mengentheoretischen Interpretation als Durchschnitt, Vereinigung und Komplement werden sie als ,  und  () geschrieben. Zur Betonung der Abstraktion in der allgemeinen booleschen Algebra werden auch Symbolpaare wie ,  oder ,  benutzt.

Mathematiker schreiben gelegentlich „·“ für UND und „+“ für ODER (wegen ihrer entfernten Ähnlichkeit zur Multiplikation und Addition anderer algebraischer Strukturen) und stellen NICHT mit einem Überstrich, einer Tilde ~, oder einem nachgestellten Prime-Zeichen dar. Diese Notation ist auch in der Schaltalgebra zur Beschreibung der booleschen Funktion digitaler Schaltungen üblich; dort benutzt man oft die definierbaren Verknüpfungen NAND (NOT AND), NOR (NOT OR) und XOR (EXCLUSIVE OR).

In diesem Artikel werden die Operatorsymbole ,  und  verwendet.

Beispiele

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 Aussagenlogik, wobei 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 und als Schaltalgebra bezeichnet. Hier entsprechen 0 und 1 zwei Spannungszuständen in der Schalterfunktion von AUS und AN. 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   und  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:

In der Aussagenlogik nennt man diese Regeln Resolutionsregeln.

Mengenalgebra 

Die Potenzmenge einer Menge  wird mit Durchschnitt, Vereinigung und dem Komplement  zu einer booleschen Algebra, bei der 0 die leere Menge  und 1 die ganze Menge  ist. Der Sonderfall  ergibt die einelementige Potenzmenge mit 1 = 0. Auch jeder  enthaltende, bezüglich Vereinigung und Komplement abgeschlossene Teilbereich der Potenzmenge von  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.

Über die Venn-Diagramme veranschaulicht die Mengenalgebra boolesche Gesetze, beispielsweise Distributiv- und de-Morgansche-Gesetze. Darüber hinaus basiert auf ihrer Form als KV-Diagramm eine bekannte Methode der systematischen Vereinfachung boolescher Ausdrücke in der Schaltalgebra.

Weitere Beispiele für boolesche Mengenalgebren stammen aus der Topologie. Die Menge der abgeschlossenen offenen Mengen eines topologischen Raums bildet mit den üblichen Operationen für die Vereinigung, den Durchschnitt und das Komplement von Mengen eine boolesche Algebra. Die regulär abgeschlossenen Mengen und die regulär offenen Mengen stellen mit den jeweiligen regularisierten Mengenoperationen ,  und  ebenfalls boolesche Algebren dar.

Andere Beispiele 

Die Menge aller endlichen oder koendlichen Teilmengen von  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.

Ist  ein Ring mit Einselement, dann definieren wir die Menge

 

aller idempotenten Elemente des Zentrums. Mit den Verknüpfungen

 

wird  zu einer booleschen Algebra.

Homomorphismen 

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

 
 
 

Es folgt daraus, dass  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  Isomorphismus, und  und  heißen isomorph.

Boolesche Ringe 

Eine andere Sichtweise auf boolesche Algebren besteht in sogenannten booleschen Ringen: Das sind Ringe mit Einselement, die zusätzlich idempotent sind, also das Idempotenzgesetz  erfüllen. Jeder idempotente Ring ist kommutativ. Die Addition im booleschen Ring entspricht bei der mengentheoretischen Interpretation der symmetrischen Differenz und bei aussagenlogischer Interpretation der Alternative ENTWEDER-ODER (exclusiv-ODER, XOR); die Multiplikation entspricht der Durchschnittsbildung beziehungsweise der Konjunktion UND.

Boolesche Ringe sind stets selbstinvers, d. h. es gilt  und folglich für das additive Inverse . Wegen dieser Eigenschaft besitzen sie auch, 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 modulo  über diesem Körper ist ebenfalls ein boolescher Ring, denn  wird mit  identifiziert und liefert die Idempotenz. Diese Algebra benutzte bereits Žegalkin 1927 als Variante der originalen Algebra von Boole, der den Körper der reellen Zahlen zugrunde legte, welcher noch keinen booleschen Ring ergibt.

Jeder boolesche Ring  entspricht einer booleschen Algebra  durch folgende Definitionen:

 
 
 

Umgekehrt wird jede boolesche Algebra  zu einem booleschen Ring  durch folgende Definitionen:

 
 
 

Ferner ist eine Abbildung  genau dann ein Homomorphismus boolescher Algebren, wenn sie ein Ringhomomorphismus (mit Erhaltung der Eins) boolescher Ringe ist.

Darstellungssatz von Stone 

Für jeden topologischen Raum ist die Menge aller abgeschlossenen offenen Teilmengen eine boolesche Algebra mit Durchschnitt und Vereinigung. Der Darstellungssatz von Stone, bewiesen von Marshall Harvey Stone, besagt, dass umgekehrt für jede boolesche Algebra ein topologischer Raum (genauer ein Stone-Raum, das heißt ein total unzusammenhängender, kompakter Hausdorffraum) existiert, in dem sie als dessen boolesche Algebra abgeschlossener offener Mengen realisiert wird. Der Satz liefert sogar eine kontravariante Äquivalenz zwischen der Kategorie der Stone-Räume mit stetigen Abbildungen und der Kategorie der booleschen Algebren mit ihren Homomorphismen (die Kontravarianz erklärt sich dadurch, dass sich für  stetig die boolesche Algebra der abgeschlossenen offenen Mengen in  durch Urbildbildung aus der von  ergibt, nicht umgekehrt durch Bildung des Bildes).

Siehe auch 

 Bitweiser Operator
 Boolesche Funktion
 Boolescher Differentialkalkül
 Boolescher Operator
 Boolesches Retrieval
 Halbring
 Heyting-Algebra
 Logikgatter
 Logische Verknüpfung
 Relationsalgebra

Literatur 

 Marshall Harvey Stone: The Theory of Representations for Boolean Algebras. In: Transactions of the American Mathematical Society. 40, 1936, , S. 37–111.
 D. A. Vladimirov: Boolesche Algebren (= Mathematische Lehrbücher und Monographien. Abteilung 2: Mathematische Monographien. Bd. 29, ). In deutscher Sprache herausgegeben von G. Eisenreich. Akademie-Verlag, Berlin 1972.

Weblinks 

 
 Online-Rechner zum Vereinfachen von Ausdrücken mit den Axiomen der booleschen Algebra.

Einzelnachweise 

 
!