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 abstrahiert. Gleichwertig zu booleschen Algebren sind boolesche Ringe, die von UND und ENTWEDER-ODER beziehungsweise Durchschnitt und symmetrischer Differenz ausgehen.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 , und ab. Bei der mengentheoretischen Interpretation als Durchschnitt, Vereinigung und Komplement werden sie als , und geschrieben. In Schaltkreisen benutzt man oft die definierbaren Verknüpfungen NAND (NOT AND), NOR (NOT OR) und XOR (ENTWEDER-ODER). Mathematiker schreiben gelegentlich + für ODER und · für UND (wegen ihrer Ähnlichkeit zur Addition und Multiplikation anderer algebraischer Strukturen) und stellen NICHT mit einem Überstrich oder einer Tilde ~ dar.
In diesem Artikel werden die Operatoren , und verwendet.
Zur 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 entstand aber erst durch Umformung und Erweiterung anderer Mathematiker wie John Venn, W. Stanley Jevons, Charles Peirce, Ernst Schröder und Giuseppe Peano. In Booles originaler Algebra bedeutet die Multiplikation die Und-Operation, die Addition dagegen weder die exklusive Entweder-Oder-Operation noch die inklusive Oder-Operation ("mindestens eines von beiden ist wahr"). Boole-Nachfolger wie Peirce und Schröder gingen vom inklusiven Oder aus wie die moderne boolesche Algebra. Das exklusive Entweder-Oder, das Booles ursprünglicher Algebra näher kommt, legte erst Ivan Ivanovich ?egalkin 1927 dem booleschen Ring zugrunde, dem Marshall Harvey Stone 1936 den Namen gab. Die erste Formalisierung der Axiome der booleschen Algebra gab Peano bereits 1888 an (siehe unten); dabei führte er die Symbole ein. Die Symbol-Variante stammt aus den Principia Mathematica von Russell/Whitehead 1910; Arend Heyting führte 1930 die Symbole ein. Claude Shannon benutzte 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 (1)(1?)(2)(2?)(11)(11?)(4)(5)(5?)(9)(9?) 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, so dass folgende Axiome gelten: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').
Man beachte, 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 eine partielle_Ordnung definierbar; bei ihr haben je zwei Elemente ein Supremum und ein Infimum. Bei der mengentheoretischen Interpretation ist gleichbedeutend zur Teilmengenordnung .
Beispiele
Zweielementige boolesche Algebra
Die wichtigste boolesche Algebra hat nur die zwei Elemente 0 und 1. Die Verknüpfungen sind wie folgt definiert:
|
||
||
Der Potenzreihen-Ring über diesem Körper ist ebenfalls ein boolescher Ring. Ihn benützte bereits ?egalkin als Variante der originalen Algebra von Boole, der den Körper der reellen Zahlen zugrunde legte, welcher noch keinen booleschen Ring ergibt.
Die Kategorien boolescher Ringe und boolescher Algebren sind isomorph. Denn jeder boolesche Ring wird zu 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 Homomorphismus boolescher Ringe ist.
Ideale und Filter noch aus dem englischen Artikel zu übersetzen.
Literatur
* Peano, Giuseppe, Calcolo geometrico, 1888, in: G. Peano, Opere scelte II, Rom 1958, 3-19
* Stone, Marshall Harvey: The Theorie of Representations for Boolean Algebras, in: Transactions of the American Mathematical Society 40 (1936), 37-111.
Weblinks
*
