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.

Operatoren

$\backslash land$	UND
$\backslash lor$	ODER
$\backslash neg$	NICHT

Sie ist benannt nach George Boole, der sie im 19. Jahrhundert definierte, um algebraische Methoden in der Aussagenlogik anwenden zu können. Er publizierte eine erste Fassung der Algebra 1847. Sie wurde später von John Venn, W. Stanley Jevons und Charles Peirce erweitert. Boole arbeitete mit Und-, Oder- und Nicht-Operationen, wobei die Oder-Operation exklusiv war (im Sinne von: "genau eines von beiden ist wahr", entspricht einem XOR-Gatter). Peirce führte 1867 die inklusive Oder-Operation ("mindestens eines von beiden ist wahr") ein und bezeichnete sie mit einem Plus-Zeichen. Claude Shannon benutzte boolesche Algebren erstmals zur Beschreibung elektrischer Schaltungen. Heute werden sie vielfach bei der Entwicklung elektronischer Schaltungen angewandt.

Die Operatoren boolescher Algebren werden auf verschiedene Weisen geschrieben. Oft schreibt man sie als UND, ODER, NICHT (bzw. AND, OR, NOT), abgekürzt mit $\{\backslash land\},\{\backslash lor\},\{\backslash neg\}$ (bzw. ^, v, ~ in manchen Texten). In Schaltkreisen benutzt man oft die Verknüpfungen NAND (NOT AND), NOR (NOT OR) und XOR (exklusives Oder). Mathematiker schreiben oft + für ODER, · für UND (aufgrund ihrer Ähnlichkeit zur Addition und Multiplikation in anderen algebraischen Strukturen) und stellen mit einem Überstrich die Verknüpfung NICHT dar.

Hier werden die Operatoren $\backslash land$, $\backslash lor$ und $\backslash neg$ verwendet.

Definition

---

Eine boolesche Algebra ist eine Menge $S$ mit zwei darauf definierten zweistelligen Verknüpfungen $\backslash land$ (Konjunktion, und, Durchschnitt $\backslash cap$) und $\backslash lor$ (Disjunktion, oder, Vereinigung $\backslash cup$) sowie einer einstelligen Verknüpfung $\backslash neg$ (Negation, nicht, Komplement), für die gilt:

$(S,\{\backslash land\},\{\backslash lor\})$ ist ein Verband, d.h.

• $\backslash land$ und $\backslash lor$ sind assoziativ und kommutativ
• Absorptionsgesetze: $x\backslash lor(x\backslash land\; y)=x,$ $x\backslash land(x\backslash lor\; y)=x$

und zusätzlich:

• Nach unten beschränkt: Es gibt ein Element 0 (Nullelement), so dass $a\backslash lor0=a$ für alle $a$
• Nach oben beschränkt: Es gibt ein Element 1 (Einselement), so dass $a\backslash land1=a$ für alle $a$
• $\backslash land$ ist distributiv über $\backslash lor$: $x\backslash land(y\backslash lor\; z)=(x\backslash land\; y)\backslash lor(x\backslash land\; z)$
• Existenz der Komplemente: $x\backslash land\backslash neg\; x=0,$ $x\backslash lor\backslash neg\; x=1$

Aus diesen Bedingungen folgt

• 0 ist das neutrale Element von $\backslash lor$, es ist eindeutig bestimmt
• 1 ist das neutrale Element von $\backslash land$, es ist eindeutig bestimmt
• Booleschen Kongruenzen (Idempotenzgesetze): $x\backslash land\; x=x,$ $x\backslash lor\; x=x$
• $\backslash lor$ ist auch distributiv über $\backslash land$: $x\backslash lor(y\backslash land\; z)=(x\backslash lor\; y)\backslash land(x\backslash lor\; z)$
• $x\backslash land0=0,$ $x\backslash lor1=1$
• $\backslash neg(\backslash neg\; x)=x$
• $\backslash neg1=0,$ $\backslash neg0=1$
• De Morgansche Regeln: $\backslash neg(x\backslash land\; y)=(\backslash neg\; x)\backslash lor(\backslash neg\; y),$ $\backslash neg(x\backslash lor\; y)=(\backslash neg\; x)\backslash land(\backslash neg\; y)$

Jede Aussage innerhalb einer booleschen Algebra hat eine duale Aussage, die durch Ersetzung von 0 durch 1 und $\backslash land$ durch $\backslash lor$ und umgekehrt entsteht. Ist die eine Aussage gültig, dann auch ihre duale Aussage (z.B. das zweite Distributivgesetz).

Eine boolesche Algebra ist also ein distributiver komplementärer Verband.

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.

Wie im Artikel Verband erläutert, kann man auf $S$ eine partielle Ordnung definieren, bei der je zwei Elemente ein Supremum und ein Infimum haben.

Beispiele

---

Zweielementige boolesche Algebra

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

Konjunktion

$\backslash land$	0	1
0	0	0
1	0	1

 

Disjunktion

$\backslash lor$	0	1
0	0	1
1	1	1

 

Negation

	$\backslash neg$
0	1
1	0

Diese Algebra hat Anwendungen in der Logik, wo 0 als "falsch" und 1 als "wahr" interpretiert werden. Die Verknüpfungen $\{\backslash land\},\{\backslash lor\},\{\backslash 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. 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 $\{\backslash land\},$ $\backslash lor$ und $\backslash 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 (engl. Name: Consensus Theorems) in jeder booleschen Algebra:

$(a\; \backslash lor\; b)\; \backslash land\; (\backslash neg\; a\; \backslash lor\; c)\; \backslash land\; (b\; \backslash lor\; c)\; =\; (a\; \backslash lor\; b)\; \backslash land\; (\backslash neg\; a\; \backslash lor\; c)$

$(a\; \backslash land\; b)\; \backslash lor\; (\backslash neg\; a\; \backslash land\; c)\; \backslash lor\; (b\; \backslash land\; c)\; =\; (a\; \backslash land\; b)\; \backslash lor\; (\backslash neg\; a\; \backslash land\; c)$

Andere Beispiele

Die Potenzmenge P(S) einer Menge S wird mit Durchschnitt und Vereinigung zu einer booleschen Algebra. Dabei ist 0 die leere Menge und 1 ist S selbst. Dieser Verband heißt Teilmengenverband oder Mengenalgebra von S. Alle Teilverbände eines Teilmengenverbandes sind distributiv.

Die Menge aller endlichen oder koendlichen Teilmengen von $\backslash mathbb\; N\_0$ 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=\backslash \{e\backslash in\; R\backslash mid\; e^2=e\backslash \; \backslash mathrm\{und\}\backslash \; ex=xe\backslash \; \backslash mathrm\{f\backslash ddot\; ur\backslash \; alle\}\backslash \; x\backslash in\; R\backslash \}$

aller idempotenten Elemente des Zentrums. Mit den Verknüpfungen

$e\backslash lor\; f\; =\; e\; +\; f\; -\; ef,\backslash quad\; e\; \backslash land\; f\; =\; ef$

wird $A$ zu einer booleschen Algebra.

Ist H ein Hilbertraum und P(H) die Menge der Orthogonalprojektionen auf H. Definiert man für zwei Orthogonalprojektionen P und Q $P\backslash lor\; Q\; =\; P\; +\; Q\; -\; nPQ,\backslash quad\; P\; \backslash land\; Q\; =\; PQ$, wobei n 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.

Siehe auch Aussagenlogik, Schaltalgebra, Boolesche Funktion.

Homomorphismen

---

Ein Homomorphismus zwischen booleschen Algebren $A,B$ ist ein Verbandshomomorphismus $f\backslash colon\; A\backslash to\; B$, der 0 auf 0 und 1 auf 1 abbildet, d.h. für alle $x,y\backslash in\; A$ gilt:

• $f(x\backslash land\; y)=f(x)\backslash land\; f(y)$
• $f(x\backslash lor\; y)=f(x)\backslash lor\; f(y)$
• $f(0)=0,\backslash quad\; f(1)=1$

Es folgt daraus, dass $f(\backslash neg\; a)=\backslash neg\; 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.

Boolesche Ringe, Ideale und Filter

---

Jede boolesche Algebra $(A,\; \{\backslash land\},\; \{\backslash lor\})$ wird zu einem kommutativen Ring $(A,\{+\},\{\backslash cdot\})$, indem man definiert:

$a\; +\; b\; =\; (a\backslash land\backslash neg\; b)\backslash lor(b\backslash land\backslash neg\; a)$

(diese Operation nennt man "symmetrische Differenz" bei Mengen und XOR in der Aussagenlogik) und

$a\backslash cdot\; b\; =\; a\backslash land\; b.$

Das Nullelement dieses Ringes entspricht der 0 der booleschen Algebra; das neutrale Element der Multiplikation ist die 1 der booleschen Algebra. Dieser Ring hat die Eigenschaft, dass $a\backslash cdot\; a=a$ für alle $a\backslash in\; A$; Ringe mit Einselement, die diese Eigenschaft besitzen, werden Boolesche Ringe genannt. Sie besitzen stets die Charakteristik 2.

Umgekehrt, wenn ein boolescher Ring $A$ gegeben ist, können wir ihn in eine boolesche Algebra umwandeln, indem wir definieren:

$x\backslash lor\; y\; =\; x\; +\; y\; -\; xy$

$x\backslash land\; y\; =\; xy.$

Da diese zwei Konstruktionen invers zueinander sind, können wir sagen, dass jeder boolesche Ring aus einer booleschen Algebra entsteht, und umgekehrt. Weiterhin ist eine Abbildung $f\backslash colon\; A\backslash to\; B$ genau dann ein Homomorphismus boolescher Algebren, wenn sie ein Homomorphismus boolescher Ringe ist. Die Kategorien boolescher Ringe und boolescher Algebren sind isomorph.

Ideale und Filter noch aus dem englischen Artikel zu übersetzen.

Repräsentation boolescher Algebren

---

Zu jeder endlichen booleschen Algebra B gibt es eine endliche Menge X, so dass B zu P(X) isomorph ist. Insbesondere folgt daraus, dass die Mächtigkeit jeder endlichen booleschen Algebra eine Zweierpotenz ist.

Der Text über das "Stone Repräsentationstheorem" ist noch aus dem englischen Artikel zu übersetzen.

Gesetze auf booleschen Algebren

---

Folgende Gesetze gelten auf booleschen Algebren:

$a\backslash land0=0$$a\backslash lor(a\backslash land\; b)=a$$a\backslash land\; a=a$$\backslash neg(a\backslash land\; b)=\backslash neg\; a\backslash lor\backslash neg\; b$

Absorption:	$a\backslash lor1=1$
Absorption (2):	$a\backslash land(a\backslash lor\; b)=a$
Idempotenz:	$a\backslash lor\; a=a$
De Morgan:	$\backslash neg(a\backslash lor\; b)=\backslash neg\; a\backslash land\backslash neg\; b$

Weblinks

---

Digitaltechnik | Algebra | Logik | Mengenlehre

Булева алгебра | বুলিয়ান বীজগণিত | Àlgebra de Boole | Booleova algebra | Boolean algebra | Álgebra de Boole | جبر بولی | Algèbre de Boole (logique) | Álxebra de Boole | אלגברה בוליאנית | Booleova algebra | Aljabar Boolean | Booleana algebro | Algebra di Boole | ブール代数 | Būlio algebra | Booleaanse algebra | Algebra Boole'a | Álgebra booleana | Булева алгебра | Boolean algebra | Booleova algebra | Булова алгебра | Boolesk algebra | พีชคณิตแบบบูล | Boole cebiri | Булева алгебра | 布尔代数