Boolesche Algebren
Allgemeine Boolesche Algebra
Eine Boolesche Algebra kann auf vielfache Art und Weise axiomatisiert werden. Den besten Überblick liefert zunächst das redundante Axiomensystem von Guiseppe Peano. Es charakterisiert eine Boolesche Algebra als Menge mit Nullelement 0 und Einselement 1, auf der die zweistelligen Verknüpfungen ∧ und ∨ und eine einstellige Verknüpfung ¬ definiert sind, durch folgende Axiome (Nummerierung unterscheidet sich von der Peanos): 11
Bildquelle: ZPG IMP [CC BY-SA 3.0 DE]
Die hier verwendete Symbolik wurde auch der Unterrichtseinheit zugrunde gelegt.
Auf verschiedene Schreibweisen wird am Ende von Kapitel 1 eingegangen.
Ein reduziertes Axiomensystem erhält man beispielsweise mit (1)-(6) und (1´)-(6´), die restlichen Gesetze können dann hergeleitet werden.12 Man kann nachweisen, dass sich dann auch die Assoziativgesetze (2) und die Absorptionsgesetze (3) aus den übrigen Axiomen folgern lassen. 13Damit gelangt man zur kompakteren Definition der Booleschen Algebra nach Huntington.14 Mit den Axiomen zur Kommutativität (1) und (1´), zur Distributivität (4) und (4´), zur Existenz der Komplemente (5) und (5´) und zur Existenz der neutralen Elemente (6) und (6´) ist die Boolesche Algebra bereits vollständig festgelegt.
Die Boolesche Algebra kann andererseits auch als distributiver komplementärer Verband definiert werden, wenn man die Kommutativität (1) und (1´), die Assoziativität (2) und (2´), die Absorptioneigenschaft (3) und (3´), eines der Distributivgesetze (4) oder (4´) und die Existenz der Komplemente (5) und (5´) fordert.
Das Dualitätsprinzip
Betrachtet man die in der Booleschen Algebra geltenden Gesetze (1)-(11) und (1´)-(11´) näher, so fällt auf, dass die jeweils nebeneinander stehenden Gesetze auseinander hervorgehen, wenn man die Symbole ∧ und ∨sowie 1 und 0 vertauscht. Aus dieser Symmetrie folgt, dass man diese Vertauschungen auch bei allen Folgerungen aus diesen Gesetzen durchführen darf. Diese weitreichende Eigenschaft der Booleschen Algebra nennt man Dualität: Zu jedem Satz existiert ein dualer Satz, der durch die oben beschriebenen Vertauschungen entsteht.
Zwei bekannte duale Sätze sind beispielsweise die beiden Regeln von De Morgan:
Bildquelle: ZPG IMP [CC BY-SA 3.0 DE]
Interpretation als Mengenalgebra
Weitreichende Bedeutung für die schulische Umsetzung hat der Satz von Stone:
"Zu jeder endlichen Booleschen Algebra (B,⊔,⊓, ¯ ) gibt es eine Mengenalgebra (P(M),∪,∩, ¯ ), so dass beide algebraischen Strukturen zueinander isomorph sind."15 |
P(M) bezeichnet hier die Potenzmenge der betrachteten Menge M, also die Menge aller möglichen Teilmengen von M. Besitzt die Menge M n Elemente, so besitzt ihre Potenzmenge P(M) bekanntlich 2n Elemente. Mit dem Satz von Stone kann man daraus direkt folgern, dass jede endliche Boolesche Algebra 2n 
Elemente besitzen muss.16 Dieser Zusammenhang wird im folgenden Abschnitt am Beispiel von Teilermengen verdeutlicht.
Der Satz von Stone sichert die Isomorphie jeder endlichen Booleschen Algebra zu einer entsprechenden Mengenalgebra und liefert so die Basis für die Visualisierung Boolescher Algebren im Kontext der Mengenalgebra. Venn-Diagramme sind dabei letzten Endes eine weitere (visuelle) Interpretation der Booleschen Algebra als Punktmengenbeziehungen in der Ebene mit Vereinigung, Durchschnitt und Komplementbildung als Verknüpfungen.
Interpretation als Teileralgebra
Eine Vernetzung mit der Teilbarkeitslehre bietet sich ebenfalls an. Sie fußt auf dem Satz:
"Zu jeder endlichen Booleschen Algebra (B,⊔,⊓, ¯) gibt es eine Teileralgebra (T(n),kgV,ggT, ¯ ) mit einer geeignet gewählten Zahl n, so dass beide algebraischen Strukturen zueinander isomorph sind."17 |
T(n) bezeichnet hier die Teilermenge der geeignet zu wählenden Zahl n.
Wie man n geeignet wählt, soll an zwei Beispielen verdeutlicht werden.
Bildquelle: ZPG IMP [CC BY-SA 3.0 DE] Beispiel 1: Teileralgebra zu T6
(B,+,·, ¯ )=(T6,+,·, ¯) mit der Teilermenge T6={1,2,3,6} als Trägermenge und den nebenstehenden Verknüpfungstafeln ist eine endliche Boolesche Algebra.
Die Verknüpfungssymbole "+" und "·" werden dabei als das kleinste gemeinsame Vielfache (kgV) und der größte gemeinsame Teiler (ggT) von je zwei Elementen der Trägermenge gedeutet.
Die geforderten Gesetze lassen sich leicht nachprüfen:
(1) und (1´): Aufgrund der Symmetrie der Verknüpfungstafeln gilt die Kommutativität.
(4) und (4´): Die Distributivgesetze lassen sich durch Einsetzen nachweisen.
(5) und (5´): Zu jedem a ϵ T6 gibt es den Komplementärteiler a mit a+a=6 und a·a=1.
(6) und (6´): Die neutralen Elemente sind 1 und 6, für jedes aϵT6 gilt: a+1=a und a·6=a
Die dabei zugrundeliegende Menge M={2,3} besteht aus zwei Elementen (die „ersten beiden“ Primzahlen). Ihre Potenzmenge P(M) enthält 22=4 Elemente und entspricht T6 , die als Trägermenge dieser Booleschen Algebra gewählt wurde.
{p1,p2} |
kgV(2,3)=6 |
{6} |
Grundmenge M={2,3} Trägermenge: |
{p2} |
kgV(1,3)=3 |
{3} |
|
{p1} |
kgV(1,2)=2 |
{2} |
|
{ } |
1 |
{1} |
Hinweise: Man hätte auch andere Primzahlen wählen können, z.B. würden 7 und 13 zu T91 führen und (T91,+,·,¯) wäre ebenfalls eine Boolesche Algebra. Um die Art der Verknüpfungen deutlich zu machen, kann man diese auch gleich direkt angeben: (B,+,·, ¯)=(T91,kgV,ggT, ¯).
Beispiel 2: (B,+,·,¯)=(T30,kgV,ggT, ¯) mit T30={1,2,3,5,6,10,15,30}
Zur Konstruktion einer geeigneten Teileralgebra kann man nun umgekehrt vorgehen. Man wählt sich z.B. als Grundmenge M={2,3,5} und gelangt über das Produkt 2·3·5=30 zur Trägermenge T30, die die weiter unten aufgeführten 23=8 Elemente besitzt.
Die Verknüpfungstafeln ergeben sich dann wie folgt:
Bildquelle: ZPG IMP [CC BY-SA 3.0 DE]
Die Potenzmenge P(M) der Menge M={p1,p2,p3}={2,3,5} ist äquivalent zur Trägermenge
B={ { },{p1},{p2},{p3},{p1,p2},{p1,p3},{p2,p3},{p1,p2,p3} } mit den Elementen:
Bildquelle: ZPG IMP [CC BY-SA 3.0 DE]
Will man eine Teileralgebra mit 16 Elementen konstruieren, so kann man das Produkt von vier beliebigen Primzahlen berechnen, z.B. 2·5·7·11=770 und hätte in der zugehörigen Teilermenge T770 eine passende Trägermenge gefunden.18
Bemerkungen zu Teileralgebren:
- Man muss die Zahl n also so wählen, dass ihre Primfaktorzerlegung nur einfache Primfaktoren enthält. Nur eine Grundmenge, die aus paarweise verschiedenen Primzahlen besteht, führt zu einer geeigneten Trägermenge.
- Teilermengen eignen sich bestens für die Vernetzung der Booleschen Algebra und der Teilbarkeitslehre. Ergänzend wäre auch hier wie bereits in Klasse 8 der Brückenschlag zu Teilergraphen möglich (vgl. Hasse-Diagramme).19
- Die Teilmengenrelation der Mengenalgebra ("A ist Teilmenge von B") entspricht bei einer Teileralgebra der Relation "a ist Teiler von b". So ist beispielsweise bei der oben betrachteten Teileralgebra mit T30 die Zahl 2 Teiler der Zahl 10. In der zugehörigen Mengenalgebra ist in Analogie hierzu die Menge {p1} Teilmenge der Menge {p1,p3}.
- Hinweis zur Anzahl der Elemente einer Booleschen Algebra:
Eine Boolesche Algebra (genauer: ihre Trägermenge) besitzt 2n Elemente, wobei n die natürliche Anzahl der Elemente der zugrundeliegenden Menge angibt.
Viele Autoren fassen den Begriff der Booleschen Algebra aber enger und verstehen darunter nur die boolsche Struktur mit der Trägermenge B={0,1}, die nun im Mittelpunkt stehen soll.
11 Hier wurde die Reihenfolge aus [ARZ], S. 28 gewählt.
12 Vgl. [LES], S. 82
13 Vgl. [LES], S. 93-95 "Zur Abhängigkeit von Grundgesetzen der Booleschen Algebra"
oder auch [ARZ], S. 39ff zur Definition eines Booleschen Verbandes und Herleitung weiterer Gesetze. 14 Vgl. Wikipedia: Artikel "Boolesche Algebra" unter https://de.wikipedia.org/wiki/Boolesche_Algebra (zuletzt abgerufen am 9.3.2019).
15 Vgl. [LES], S. 110
16 a.a.O.
17 Beweis vgl. [LES], S. 105
18 Weitere Informationen zu den Beispielen und Teileralgebren findet man in [ARZ], S.39 und [LES], S. 97 ff.
19 Hinweise dazu z.B. in [ARZ], S. 82ff
Hintergrund: Herunterladen [odt][601 KB]
Hintergrund: Herunterladen [pdf][698 KB]
Weiter zu Boolesche Algebra über der Trägermenge B=[0,1]