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.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 arbeitet mit Und-, Oder- und Nicht-Operationen, wobei die Oder-Operation exklusiv war. Peirce führte 1867 die inklusive Oder-Operation 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 ∧, ∨, ¬ (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 verwenden wir die Operatoren ∧, ∨ und ¬.
| Table of contents |
|
2 Beispiele 3 Homomorphismen 4 Boolesche Ringe, Ideale und Filter 5 Repräsentation Boolescher Algebren |
Eine Boolesche Algebra ist eine Menge S mit zwei darauf definierten zweistelligen Verknüpfungen ∧ (Konjunktion und, Durchschnitt
(S, ∧, ∨) ist ein Verband, d.h.
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.
Die wichtigste Boolesche Algebra hat nur die zwei Elemente 0 und 1. Die Verknüpfungen sind wie folgt definiert:
{| border="0"
|
{| border="1" cellspacing="0" cellpadding="6"
|+ Konjunktion
| ∧
| 0
| 1
|-
| 0
| 0
| 0
|-
| 1
| 0
| 1
|}
|
|
{| border="1" cellspacing="0" cellpadding="6"
|+ Disjunktion
| ∨
| 0
| 1
|-
| 0
| 0
| 1
|-
| 1
| 1
| 1
|}
|
|
{| border="1" cellspacing="0" cellpadding="6"
|+ Negation
|
| ¬
|-
| 0
| 1
|-
| 1
| 0
|}
|}
Diese Algebra hat Anwendungen in der Logik, wo 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ßen Boolesche Ausdrücke.
Auch für elektrische Schaltungen wird diese Algebra verwendet. Hier entsprechen 0 und 1 zwei Spannungszuständen. Das Eingangs-Ausgangs-Verhalten jeder möglichen elektrischen 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 (engl. Name: Consensus Theorems) in jeder Booleschen Algebra:
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 von S.
Alle Teilverbände eines Teilmengenverbandes sind distributiv.
Die Menge aller endlichen oder ko-endlichen Teilmengen von N0 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 distributiber 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, dann definieren wir die Menge
Siehe auch Aussagenlogik, Schaltalgebra.
Ein Homomorphismus zwischen Booleschen Algebren A, B ist ein Verbands-Homomorphismus f: A -> B, der 0 auf 0 und 1 auf 1 abbildet, d.h. für alle a,b aus A gilt:
Noch aus dem englischen Artikel zu übersetzen.
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.
Text über das "Stone Repräsentations-Theorem" ist noch aus dem englischen Artikel zu übersetzen.
Definition
) und ∨ (Disjunktion oder, Vereinigung 
) sowie einer einstelligen Verknüpfung ¬ (Negation nicht, Komplement), für die gilt:
und zusätzlich:
Aus diesen Bedingungen folgt
Jede Aussage innerhalb einer Booleschen Algebra hat eine duale Aussage, die durch Ersetzung von 0 durch 1 und ∧ durch ∨ und umgekehrt entsteht. Ist die eine Aussage gültig, dann auch ihre duale Aussage (z.B. das zweite Distributivgesetz).Beispiele
Zweielementige Boolesche Algebra
Andere Beispiele
aller idempotenten Elemente des Zentrums. Mit den Verknüpfungen e ∨ f = e + f + ef, e ∧ f = ef wird A zu einer Booleschen Algebra.Homomorphismen
Es folgt daraus, dass f(¬a) = ¬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
Repräsentation Boolescher Algebren
