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.

Operatoren

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

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 $\land$, $\lor$, $\neg$ ab. Bei der mengentheoretischen Interpretation als Durchschnitt, Vereinigung und Komplement werden sie als $\cap$, $\cup$, C geschrieben. In Schaltkreisen benutzt man oft die definierbaren Verknüpfungen NAND (NOT AND), NOR (NOT OR) und XOR (Entweder-Oder). Mathematiker schreiben oft + 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.

Hier werden die Operatoren $\land$, $\lor$ und $\neg$ 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 Marshall Harvey Stone 1936 dem booleschen Ring zugrunde. Die erste Formalisierung der Axiome der booleschen Algebra gab Peano bereits 1888 an; dabei führte er die Symbole $\cap \cup$ ein. Die Symbol-Varianten $\lor \land$ gehen auf die Prinicipia Mathematica von Russell/Whitehead 1910 zurück. Claude Shannon benutzte boolesche Algebren erstmals zur Beschreibung elektrischer Schaltungen.

Definition

Eine boolesche Algebra ist eine Menge $S$ mit zwei auf ihr definierten zweistelligen Verknüpfungen $\land$ und $\lor$ sowie einer einstelligen Verknüpfung $\neg$ für die gilt:

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

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

und zusätzlich:

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

Aus diesen Bedingungen folgt

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

Jede Aussage innerhalb einer booleschen Algebra hat eine duale Aussage, die durch Ersetzung von 0 durch 1 und $\land$ durch $\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 $\land$ 0 0 0 0 0 1 0 1

Disjunktion $\lor$ 0 1 0 0 1 1 1 1

Negation   $\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 ${\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. 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 ${\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 (engl. Name: Consensus Theorems) in jeder booleschen Algebra:

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

$(a\land b)\lor (\neg a\land c)\lor (b\land c)=(a\land b)\lor (\neg a\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 $\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=\{e\in R\mid e^{2}=e\ \mathrm {und} \ ex=xe\ \mathrm {f{\ddot {u}}r\ alle} \ x\in R\}$

aller idempotenten Elemente des Zentrums. Mit den Verknüpfungen

$e\lor f=e+f-ef,\quad e\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\lor Q=P+Q-nPQ,\quad P\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\colon A\to B$, der 0 auf 0 und 1 auf 1 abbildet, d.h. für alle $x,y\in A$ gilt:

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

Es folgt daraus, dass $f(\neg a)=\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,{\land },{\lor })$ wird zu einem kommutativen Ring $(A,{+},{\cdot })$, indem man definiert:

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

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

$a\cdot b=a\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\cdot a=a$ für alle $a\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\lor y=x+y-xy$

$x\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\colon A\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:

Absorption:	$a\lor 1=1$ $a\land 0=0$
Absorption (2):	$a\land (a\lor b)=a$ $a\lor (a\land b)=a$
Idempotenz:	$a\lor a=a$ $a\land a=a$
De Morgan:	$\neg (a\lor b)=\neg a\land \neg b$ $\neg (a\land b)=\neg a\lor \neg b$
$a\Rightarrow b\equiv \neg a\vee b$
$a\Leftrightarrow b\equiv (a\wedge b)\vee (\neg a\wedge \neg b)$
$a\Rightarrow (b\vee c)\equiv (a\Rightarrow b)\vee (a\Rightarrow c)$
$a\Rightarrow (b\wedge c)\equiv (a\Rightarrow b)\wedge (a\Rightarrow c)$
$(a\vee b)\Rightarrow c\equiv (a\Rightarrow c)\wedge (b\Rightarrow c)$
$(a\wedge b)\Rightarrow c\equiv (a\Rightarrow c)\vee (b\Rightarrow c)$

Weblinks

• Eintrag in Edward N. Zalta (Hrsg.): Stanford Encyclopedia of Philosophy.Vorlage:SEP/Wartung/Parameter 1 und weder Parameter 2 noch Parameter 3