Boolesche Algebren

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.

Definition

Eine boolesche Algebra ist ein distributiver komplementärer Verband.
Diese Definition geht nur von den Verknüpfungen \wedge und \lor aus und umfasst die Existenz von 0, 1 und ¬\neg und die unabhängigen Axiome (1)(1')(2)(2')(11)(11')(4)(9)(9') des gleichwertigen redundanten Axiomensystems von Peano mit zusätzlichen ableitbaren Axiomen; dieses charakterisiert eine boolesche Algebra als Menge mit Nullelement 0 und Einselement 1, auf der die zweistelligen Verknüpfungen \wedge und \lor und eine einstellige Verknüpfung ¬\neg definiert sind, durch folgende Axiome (originale Nummerierung von Peano):
Kommutativgesetze (1) ab=baa\land b = b\land a (1') ab=baa\lor b = b\lor a
Assoziativgesetze (2) (ab)c=a(bc)(a\land b)\land c = a\land (b\land c) (2') (ab)c=a(bc)(a\lor b)\lor c = a\lor (b\lor c)
Idempotenzgesetze (3) aa=aa\land a=a (3') aa=aa\lor a=a
Distributivgesetze (4) a(bc)=(ab)(ac)a\land (b\lor c) = (a\land b) \lor (a \land c) (4') a(bc)=(ab)(ac)a\lor (b\land c) = (a\lor b) \land (a \lor c)
Neutralitätsgesetze (5) a1=aa\land 1 = a (5') a0=aa\lor 0 = a
Extremalgesetze (6) a0=0a\land 0=0 (6') a1=1a\lor 1=1
Doppelnegationsgesetz (Involution) (7) ¬(¬a)=a\neg(\neg a)=a
De Morgansche Gesetze (8) ¬(ab)=¬a¬b\neg(a\land b)=\neg a\lor\neg b (8') ¬(ab)=¬a¬b\neg(a\lor b)=\neg a\land\neg b
Komplementärgesetze (9) a¬a=0a\land\neg a=0 (9') a¬a=1a\lor\neg a=1
Dualitätsgesetze (10) ¬0=1\neg 0 = 1 (10') ¬1=0\neg 1 = 0
Absorptionsgesetze (11) a(ab)=aa\lor(a\land b)=a (11') a(ab)=aa\land(a\lor b)=a
Jede Formel in einer booleschen Algebra hat eine duale Formel, die durch Ersetzung von 0 durch 1 und \wedge durch \lor 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 ab    a=aba\le b \iff a=a\land b eine partielle Ordnung definierbar; bei ihr haben je zwei Elemente ein Supremum und ein Infimum. Bei der mengentheoretischen Interpretation ist \le gleichbedeutend zur Teilmengenordnung \subseteq.

Beispiele

Zweielementige boolesche Algebra

Die wichtigste boolesche Algebra hat nur die zwei Elemente 0 und 1. Die Verknüpfungen sind wie folgt definiert:
Konjunktion
\wedge 0\bm{0} 1\bm{1}
0\bm{0} 0 0
1\bm{1} 0 1
Disjunktion
\lor 0\bm{0} 1\bm{1}
0\bm{0} 0 1
1\bm{1} 1 1
Negation
¬\neg
0\bm{0} 1
1\bm{1} 0
Diese Algebra hat Anwendungen in der Aussagenlogik, wo 0 als "falsch" und 1 als "wahr" interpretiert werden. Die Verknüpfungen ,,¬{\land},{\lor},{\neg} 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 ,{\land}, \lor und ¬\neg 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:
(ab)(¬ac)(bc)=(ab)(¬ac)(a \lor b) \land (\neg a \lor c) \land (b \lor c) = (a \lor b) \land (\neg a \lor c)
(ab)(¬ac)(bc)=(ab)(¬ac)(a \land b) \lor (\neg a \land c) \lor (b \land c) = (a \land b) \lor (\neg a \land c)
In der Aussagenlogik nennt man diese Regeln Resolutionsregeln.

Mengenalgebra

Die Potenzmenge P(S)\Pow (S) einer Menge SS 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 SS enthaltende, bezüglich Vereinigung und Komplement abgeschlossene Teilbereich der Potenzmenge von SS 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.

Andere Beispiele

Die Menge aller endlichen oder koendlichen Teilmengen von N0\mathbb N_0 bildet mit Durchschnitt und Vereinigung eine boolesche Algebra.
Für jede natürliche Zahl nn ist die Menge aller positiven Teiler von nn mit den Verknüpfungen ggT und kgV ein distributiver beschränkter Verband. Dabei ist 1 das Nullelement und nn das Einselement. Der Verband ist boolesch genau dann, wenn nn quadratfrei ist. Dieser Verband heißt Teilerverband von nn.
Für jeden topologischen Raum XX ist die Menge aller offenen abgeschlossenen Teilmengen eine boolesche Algebra mit Durchschnitt und Vereinigung.
Ist RR ein Ring mit Einselement, dann definieren wir die Menge
A={eRe2=e und ex=xexR}A=\{e\in R\mid e^2=e\ \mathrm{und}\ ex=xe \,\forall x\in R\}
aller idempotenten Elemente des Zentrums. Mit den Verknüpfungen
ef=e+fef,ef=efe\lor f = e + f - ef,\quad e \land f = ef
wird AA zu einer booleschen Algebra.
Ist HH ein Hilbertraum und P(H) die Menge der Orthogonalprojektionen auf HH. Definiert man für zwei Orthogonalprojektionen PP und QPQ=P+QnPQ,PQ=PQQ P\lor Q = P + Q - nPQ,\quad P \land Q = PQ, wobei nn gleich 1 oder 2 sein soll. In beiden Fällen wird P(H) zu einer booleschen Algebra. Der Fall n=2 ist in der Spektraltheorie von Bedeutung.

Homomorphismen

Ein Homomorphismus zwischen booleschen Algebren A,BA,B ist ein Verbandshomomorphismus f ⁣:ABf\colon A\to B, der 0 auf 0 und 1 auf 1 abbildet, d.h. für alle x,yAx,y\in A gilt:
  • f(xy)=f(x)f(y)f(x\land y)=f(x)\land f(y)
  • f(xy)=f(x)f(y)f(x\lor y)=f(x)\lor f(y)
  • f(0)=0,f(1)=1f(0)=0,\quad f(1)=1
Es folgt daraus, dass f(¬a)=¬f(a)f(\neg a)=\neg f(a) für alle aa aus AA. Die Klasse aller booleschen Algebren wird mit diesem Homomorphismenbegriff eine Kategorie. Ist ein Homomorphismus ff zusätzlich bijektiv, dann heißt ff Isomorphismus, und AA und BB heißen isomorph.

Boolesche Ringe

Als boolesche Ringe gelten seit Stone alle Ringe mit Einselement, die zusätzlich idempotent sind, also das Idempotenzgesetz aa=aa\cdot a = a 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, denn es gilt a+a=0\,a+a=0 und a=a\,-a=a, so dass die Inversen-Operation definierbar ist. 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:
\cdot 0\bm{0} 1\bm{1}
0\bm{0} 0 0
1\bm{1} 0 1
++ 0\bm{0} 1\bm{1}
0\bm{0} 0 1
1\bm{1} 1 0
Der Potenzreihen-Ring modulo xx+x\,x\cdot x+x über diesem Körper ist ebenfalls ein boolescher Ring, denn xx+x\, x\cdot x+x wird mit 0\, 0 identifiziert und liefert die Idempotenz. Diese Algebra benützte 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.
Die Kategorien boolescher Ringe und boolescher Algebren sind isomorph. Denn jeder boolesche Ring (R,+,,,1,0)(R,{+},{-},{\cdot}, 1, 0) wird zu einer booleschen Algebra (R,,,¬,1,0)(R, {\land}, {\lor}, {\neg}, 1, 0) durch folgende Definitionen:
xy=x+y+xyx\lor y = x + y + xy
xy=xyx\land y = xy
¬x=x+1\neg x = x+1
Umgekehrt wird jede boolesche Algebra (A,,,¬,1,0)(A, {\land}, {\lor}, {\neg}, 1, 0) zu einem booleschen Ring (A,+,,,1,0)(A,{+},{-},{\cdot}, 1, 0) durch folgende Definitionen:
a+b=(a¬b)(b¬a)a + b = (a\land\neg b)\lor(b\land\neg a)
a=a\,-a = a
ab=aba\cdot b = a\land b
Ferner ist eine Abbildung f ⁣:ABf\colon A\to B genau dann ein Homomorphismus boolescher Algebren, wenn sie ein Homomorphismus boolescher Ringe ist.

Literatur

  • Marshall Harvey Stone: The Theory of Representations for Boolean Algebras. In: Transactions of the American Mathematical Society. Lancaster 40.1936, S. 37-111. Unknown meta: ISSN|0002-9947
  • D. A. Vladimirov: Boolesche Algebren. In deutscher Sprache herausgegeben von G. Eisenreich. Berlin 1972.
 
 

Wer die erhabene Weisheit der Mathematik tadelt, nährt sich von Verwirrung.

Leonardo da Vinci

Copyright- und Lizenzinformationen: Diese Seite basiert dem Artikel Boolesche Algebra aus der frеiеn Enzyklοpädιe Wιkιpеdιa und stеht unter der Dοppellizеnz GNU-Lιzenz für freie Dokumentation und Crеative Commons CC-BY-SA 3.0 Unportеd (Kurzfassung). In der Wιkιpеdιa ist eine Listе dеr Autorеn des Originalartikels verfügbar. Da der Artikel geändert wurde, reicht die Angabe dieser Liste für eine lizenzkonforme Weiternutzung nicht aus!
Anbieterkеnnzeichnung: Mathеpеdιa von Тhοmas Stеιnfеld  • Dοrfplatz 25  •  17237 Blankеnsее  • Tel.: 01734332309 (Vodafone/D2)  •  Email: cο@maτhepedιa.dе