Venn-Diagramme für Konjunktion, Disjunktion und Negation bzw. für Durchschnitt, Vereinigung und Komplement
In derMathematik ist eineboolesche Algebra (oder einboolescher Verband) eine speziellealgebraische Struktur, die die Eigenschaften derlogischen Operatoren UND (Konjunktion), ODER (Disjunktion), NICHT (Negation) sowie die Eigenschaften dermengentheoretischen Verknüpfungen Durchschnitt, Vereinigung, Komplement verallgemeinert. Gleichwertig zu booleschen Algebren sindboolesche 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 alsSchaltalgebra, etwa bei der Erstellung vonSchaltnetzen, angewandt. Sie wird in allen modernen Programmiersprachen zur Verfügung gestellt und ist auch in derMengenlehre undStatistik vertreten.[1]
Die boolesche Algebra ist nachGeorge Boole benannt, da sie auf dessenLogikkalkül von 1847 zurückgeht, in dem er erstmals algebraische Methoden in derKlassenlogik undAussagenlogik anwandte. Ihre heutige Form verdankt sie der Weiterentwicklung durch Mathematiker wieJohn Venn,William Stanley Jevons,Charles Peirce,Ernst Schröder undGiuseppe Peano. InBooles 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.[2] Peano brachte dessen System 1888 in die heutige Form (siehe unten) und führte dabei die Symbole und ein.[3] Das aussagenlogische ODER-Zeichen stammt vonRussell 1906;[4]Arend Heyting führte 1930 die Symbole und ein.
Das redundanteAxiomensystem vonPeano (mit zusätzlichen ableitbaren Axiomen) charakterisiert eine boolesche Algebra alsMenge mit Nullelement 0 und Einselement 1, auf der diezweistelligen Verknüpfungen und und eineeinstellige Verknüpfung definiert sind, durch folgende Axiome (originale Nummerierung von Peano):[3]
Jede Formel in einer booleschen Algebra hat eineduale 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 mitinversen Elementen zu tun, denn die Verknüpfung eines Elementes mit seinem Komplement liefert dasneutrale Element der jeweilsanderen Verknüpfung.
Eineboolesche Algebra ist ein distributiver komplementärerVerband.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 jedemVerband durch einepartielle Ordnung definierbar; bei ihr haben je zwei Elemente einSupremum und ein Infimum. Bei der mengentheoretischen Interpretation ist gleichbedeutend zur Teilmengenordnung.
Eine kompaktere Definition ist das Axiomensystem nachHuntington:
Eineboolesche 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 geforderteAbgeschlossenheit der Verknüpfungen ist hier schon in der Formulierung „Verknüpfungenauf“ 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.
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 zurMultiplikation undAddition anderer algebraischer Strukturen) und stellen NICHT mit einem Überstrich, einer Tilde ~, oder einem nachgestelltenPrime-Zeichen dar. Diese Notation ist auch in derSchaltalgebra 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.
Die wichtigste boolesche Algebra hat nur die zwei Elemente 0 und 1. Die Verknüpfungen sind wie folgt definiert:
Konjunktion (UND)
0
1
0
0
0
1
0
1
Disjunktion (ODER)
0
1
0
0
1
1
1
1
Negation (NICHT)
0
1
1
0
Diese Algebra hat Anwendungen in derAussagenlogik, 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ßenboolesche Ausdrücke.
Auch fürdigitale Schaltungen wird diese Algebra verwendet und alsSchaltalgebra bezeichnet. Hier entsprechen 0 und 1 zweiSpannungszustä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:
DiePotenzmenge 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 alsTeilmengenverband oderMengenalgebra bezeichnet wird. DerDarstellungssatz vonStone besagt, dass jede boolesche Algebra isomorph (s. u.) zu einer Mengenalgebra ist. Daraus folgt, dass dieMächtigkeit jeder endlichen booleschen Algebra eine Zweierpotenz ist.
Über dieVenn-Diagramme veranschaulicht die Mengenalgebra boolesche Gesetze, beispielsweise Distributiv- und de-Morgansche-Gesetze. Darüber hinaus basiert auf ihrer Form alsKV-Diagramm eine bekannte Methode der systematischen Vereinfachung boolescher Ausdrücke in derSchaltalgebra.
Die Menge aller endlichen oderkoendlichen Teilmengen von bildet mit Durchschnitt und Vereinigung eine boolesche Algebra.
Für jede natürliche Zahln ist die Menge aller positiven Teiler vonn mit den Verknüpfungen ggT und kgV ein distributiver beschränkter Verband. Dabei ist 1 das Nullelement undn das Einselement. Der Verband ist boolesch genau dann, wennnquadratfrei ist. Dieser Verband heißtTeilerverband vonn.
Ist einRing mit Einselement, dann definieren wir die Menge
EinHomomorphismus 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 allea ausA. DieKlasse aller booleschen Algebren wird mit diesem Homomorphismenbegriff eineKategorie. Ist ein Homomorphismusf zusätzlichbijektiv, dann heißtIsomorphismus, und und heißenisomorph.
Eine andere Sichtweise auf boolesche Algebren besteht in sogenanntenbooleschen Ringen: Das sindRinge mit Einselement, die zusätzlichidempotent sind, also das Idempotenzgesetz erfüllen. Jeder idempotente Ring istkommutativ. Die Addition im booleschen Ring entspricht bei der mengentheoretischen Interpretation dersymmetrischen 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 dieCharakteristik 2. Der kleinste solche boolesche Ring ist zugleich einKörper mit folgenden Verknüpfungstafeln:
0
1
0
0
0
1
0
1
0
1
0
0
1
1
1
0
DerPotenzreihen-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 derreellen 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 einRinghomomorphismus (mit Erhaltung der Eins) boolescher Ringe ist.
Für jedentopologischen Raum ist die Menge allerabgeschlossenen offenen Teilmengen (englischclopen subsets) eine boolesche Algebra mit Durchschnitt und Vereinigung. Der Darstellungssatz von Stone, bewiesen vonMarshall Harvey Stone, besagt, dass umgekehrt für jede boolesche Algebra ein topologischer Raum (genauer einStone-Raum, das heißt eintotal unzusammenhängender,kompakterHausdorffraum) existiert, in dem sie als dessen boolesche Algebra abgeschlossener offener Mengen realisiert wird. Der Satz liefert sogar einekontravarianteÄquivalenz zwischen der Kategorie der Stone-Räume mitstetigen 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 durchUrbildbildung aus der von ergibt, nicht umgekehrt durch Bildung des Bildes).
Für die boolesche Algebra kann man auch dasfreie Objekt bilden, genannt diefreie boolesche Algebra.
Sei diekonkrete Kategorie der booleschen Algebren mit demVergissfunktor. Gegeben sei eine Menge, genanntBasis, ein Objekt aus und eine injektive Abbildung.Das Paar heißtfrei über, wenn dieuniverselle Eigenschaft erfüllt ist: Für jedes Objekt aus und jede Abbildung gibt es einen eindeutigenMorphismus mit. Das bedeutet, das folgende Diagram kommutiert:
Marshall Harvey Stone:The Theory of Representations for Boolean Algebras. In:Transactions of the American Mathematical Society. 40, 1936,ISSN0002-9947, S. 37–111.
D. A. Vladimirov:Boolesche Algebren (=Mathematische Lehrbücher und Monographien. Abteilung 2:Mathematische Monographien. Bd. 29,ISSN0076-5430). In deutscher Sprache herausgegeben vonG. Eisenreich. Akademie-Verlag, Berlin 1972.
