3. Boole'sche Algebra
3.1. Einführung
Die Boole'sche Algebra geht zurück auf den britischen Mathematiker George Boole (1815 - 1864). Er
veröffentlichte 1847 sein Buch „The Mathematical Analysis of Logic“, in welchem er algebraische Methoden
in der klassischen Logik und in der Aussagenlogik (algebraisches Logikkalkül) formulierte. Durch die
Weiterentwicklung verschiedener Mathematiker ist die heutige Form der Boole’schen Algebra entstanden. So
wurden z.B. erst Anfang des 20. Jahrhunderts die Symbole
für das Und (AND),
für das Oder (OR) und
für die Negation (NOT) eingeführt; der Begriff Boole’sche Algebra selber wurde erst 1913 geprägt.
3.2. Definition
Die Boole’sche Algebra beinhaltet die Werte 0 und 1 sowie die zweistelligen (binären) Operatoren
und
und den einstelligen (unären) Operator
. Dazu gelten folgende Axiome (Gesetze):
Kommutativgesetz (Vertauschungsgesetz)
A B = B A
A B = B A
Assoziativgesetz (Verknüpfungsgesetz)
(A B) C = A (B C)
(A B) C = A (B C)
Idempotenzgesetz
A A = A
A A = A
Distributivgesetz (Verteilungsgesetz)
A (B C) = (A B) (A C)
A (B C) = (A B) (A C)
Neutralitätsgesetz
A 1 = A
A 0 = A
Extremalgesetz
A 0 = 0
A 1 = 1
Gesetz der doppelten Negation
(A) = A
De Morgan’sches Gesetz (De Morgan’sche Regel)
(A B) = A B
(A B) = A B
Komplementärgesetz
A A = 0
A A = 1
Dualitätsgesetz
0 = 1
1 = 0
Absorptionsgesetz
A (A B) = A
A (A B) = A
Die Boole’sche Algebra wird in verschiedenen Bereichen angewendet:
In der Aussagenlogik wird der Wert 0 als Falsch (false) und der Wert 1 als Wahr (true) interpretiert. Die Verknüpfungen
, und
entsprechen den logischen Verknüpfungen Und, Oder und Nicht. Logische Ausdrücke,
die aus den beiden Werten und einer der Verknüpfungen bestehen, werden Boole’sche Ausdrücke genannt.
Auch bei digitalen Schaltungen kommt die Boole’sche Algebra zum Einsatz (Schaltalgebra); hierbei werden die Werte 0 und 1 als Spannungszustände Aus und An
interpretiert. Jede digitale Schaltung kann durch einen Boole’schen Ausdruck dargestellt werden: Zwei Spannungszustände werden verknüpft und ergeben einen neuen Spannungszustand.
3.3. AND (Konjunktion)
Bei einer -Operation ist das Ergebnis nur dann 1, wenn beide Operanden gleich 1 sind. In allen anderen
Fällen ist das Ergebnis gleich 0. In der Aussagenlogik bedeutet dies, dass eine mit Und verknüpfte Aussage nur dann wahr ist, wenn beide Teilaussagen wahr sind. Im
allgemeinen werden diese Ergebnisse in einer sogenannten Wahrheitstabelle dargestellt.
| A | B | A B |
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
3.4. OR (Disjunktion)
Bei einer -Operation ist das Ergebnis dann 1, wenn mindestens einer der beiden Operanden
gleich 1 ist. Nur in dem Fall, dass beide Operanden gleich 0 sind, ist auch das Ergebnis gleich 0. In der Aussagenlogik bedeutet dies, dass eine mit Oder verknüpfte
Aussage dann wahr ist, wenn mindestens eine der beiden Teilaussagen wahr ist.
| A | B | A B |
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
3.5. NOT (Negation)
Mit der -Operation wird von einem Wert zum anderen gewechselt, d.h. von 0 zur 1 und von 1 zur 0.
In der Aussagenlogik wird dabei von einer Negation (nicht zu verwechseln mit der mathematischen Negation) gesprochen, denn aus wahr wird falsch und umgedreht.
| A | A |
| 0 | 1 |
| 1 | 0 |
3.6. XOR (Exklusiv-Oder, Kontravalenz)
Die Entweder-Oder-Verknüpfung wird auch ausschließende Disjunktion (zur Unterscheidung zur einschließenden Disjunktion, dem OR) oder Kontravalenz bzw. Antivalenz
genannt. Sie gehört nicht zu den Grundoperationen, denn sie lässt sich durch die drei anderen Operatoren darstellen:
A xor B = (A B) (A B)
| A | B | A xor B |
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
3.7. Logisch oder bitweise
Voriges Kapitel: 2. Zahlensysteme
Nächstes Kapitel: 4. Programmentwicklung