Boolesche Algebra – Serlo „Mathe für Nicht-Freaks“
In den vorangegangenen Kapiteln haben wir verschiedene Verknüpfungen zwischen Mengen kennengelernt. Die Regeln, die für diese Verknüpfungen gelten, sind hier übersichtlich zusammengestellt. , , , seien im Folgenden beliebige Mengen.
Regeln für den Durchschnitt und die Vereinigung
[Bearbeiten]Durchschnitt und Vereinigung verhalten sich zueinander "dual": wenn du in einer Regel mit und mit vertauschst, erhältst du wieder eine gültige Regel! Die Beweise - soweit sie hier nicht angegeben sind - findest du in den Kapiteln Durchschnitt von Mengen und Vereinigung von Mengen.
Assoziativität
[Bearbeiten]Beim Durchschnitt und bei der Vereinigung ist es egal, in welcher Reihenfolge du die Verknüpfungen ausführst.
Kommutativität
[Bearbeiten]Beim Durchschnitt und bei der Vereinigung kannst du die Seiten vertauschen.
Idempotenz
[Bearbeiten]Verknüpfst du eine Menge mit sich selbst, ändert sich nichts.
Neutrales Element
[Bearbeiten]Die Allklasse ist ein neutrales Element für den Durchschnitt , die leere Menge ist ein neutrales Element für die Vereinigung .
Extremwerte
[Bearbeiten]Bezüglich der Teilmengen-Beziehung ist die leere Menge die kleinste und die Allklasse die die gröste Menge. Die Verknüpfung mit bzw. liefert daher nichts Neues.
Distributivität
[Bearbeiten]Ein Durchschnitt kann in eine Vereinigung "hineingezogen" werden, ebenso eine Vereinigung in einen Durchschnitt.
Beweis: Mit den Definitionen für und wird die Behauptung auf die Distributivgesetze für und zurückgeführt, s. Kapitel "Gesetze der Logik".
Die zweite Behauptung wird ebenso bewiesen.
Regeln für das Komplement
[Bearbeiten]Die Beweise findest du im Kapitel Differenz, symmetrische Differenz und Komplement.
Existenz des Komplements
[Bearbeiten]Zu jeder Menge gibt es ein Komplement .
De Morgansche Gesetze
[Bearbeiten]Das Komplement kann in einen Durchschnitt bzw. in eine Vereinigung "hereingezogen" werden.
Doppeltes Komplement
[Bearbeiten]Ein doppeltes Komplement entfällt.
Grösstes und kleinstes Element
[Bearbeiten]Boolsche Algebra
[Bearbeiten]Eine Struktur mit den oben aufgeführten Eigenschaften wird Boolesche Algebra genannt. Die wichtigsten Beispiele sind die Potenzmengen einer Grundmenge .
Potenzmenge
[Bearbeiten]Beispiel (Potenzmenge als Boolesche Algebra)
Die Elemente von sind alle Teilmengen einer Grundmenge , formalisiert: . Weiterhin gehören der Durchschnitt , die Vereinigung , das Komplement und die beiden ausgezeichneten Elemente und zu der Struktur.
Das folgende Bild zeigt die Boolesche Algebra mit und .
Aussagenlogik
[Bearbeiten]In den Beweisen für die Mengengesetze haben wir immer wieder auf die Gesetze der Aussagenlogik zurückgegriffen. Das ist kein Zufall, sondern liegt daran, dass die Aussagenlogik ebenfalls eine Boolesche Algebra bilden.
Beispiel (Boolesche Algebra mit zwei Elementen)
Die Menge der besteht aus den beiden Wahrheitswerten und , es gilt also: . Die Verknüpfungen sind die Konjunktion (und), die Disjunktion (oder) und die Negation (nicht). Die Verknüpfungen sind wie folgt festgelegt, vgl. Kapitel "Junktoren":
A | B | A B | A B | A |
---|---|---|---|---|
W | W | W | W | F |
W | F | F | W | W |
F | W | F | W | |
F | F | F | F |
Verständnisfrage: Was sind die neutralen Elemente dieser Booleschen Algebra?
Da nur zwei Elemente hat, sind es und . Wegen ist das neutrale Element zu . Und wegen ist das neutrale Element zu .
Die Boolesche Algebra mit zwei Elementen gibt nicht nur die Struktur der Aussagenlogik wieder, sondern spielt auch in der Informatik als Schaltagebra eine wichtige Rolle.
Teilerverband
[Bearbeiten]Beispiel (Teilerverband)
Die Menge der positiven Teiler einer natürlichen Zahl bilden eine Boolesche Algebra, wenn in der Primzahlzerlegung von jede Primzahl höchstens einmal vorkommt. Die beiden zweistelligen Verknüpfungen sind das kleinste gemeinsame Vielfache mit dem neutralen Element und der größte gemeinsame Teiler mit dem neutralen Element .
Aufgabe: Wie sieht der Teilerverband von 210 aus?
Die Elemente des Teilerverbandes von sind . Das komplementäre Element zu einem Teiler bezeichnen wir mit . Es muss für alle gelten: und . Also ist .
Aufgabe: Kann die Bedingung, dass in der Primzahlzerlegung von jede Primzahl höchstens einmal vorkommt, weggelassen werden? Gib ein Beispiel dafür an, dass der Teilerverband dann keine Boolesche Algebra sein muss.
Wir betrachten , denn das ist die kleinste Zahl, in der eine Primzahl in der Primzahlzerlegung doppelt vorkommt. Die Elemente dieses Teilerverbandes sind . Das neutrale Element zu ist , das neutrale Element zu ist . Wir suchen das komplementäre Element zu . Für muss gelten: und . Aus der ersten Bedingung folgt , aber aus der zweiten . ↯ Also ist der Teilerveband von keine Boolesche Algebra!
Definition
[Bearbeiten]Nun ist es mühsam, alle in diesem Kapitel aufgeführten Eigenschaften nachzuprüfen, um zu zeigen, dass eine Struktur eine Boolesche Algebra ist. Zum Glück ist das auch nicht nötig, denn aus einigen Regeln können die anderen Regeln hergeleitet werden. Die Regeln, die zugrunde gelegt werden heißen Axiome. Ein häufig verwendetes Axiomensystem für Boolesche Algebren stammt vom amerikanischen Mathematiker Edward Huntington aus dem Jahre 1904. Um deutlich zu machen, dass hier eine allgemeine Struktur gemeint ist, benutzen wir neue Symbole für die Verknüpfungen, nämlich , und , und bezeichnen die neutralen Elemente mit und .
Warnung
In der Mathematik werden je nach Zusammenhang völlig unterschiedliche Symbole für Boolesche Algebren verwendet! Einige davon haben wir in den Beispielen bereits kennengelernt.
Definition (Boolesche Algebra)
Eine Struktur mit der Menge , den 2-stelligen Verknüpfungen und auf , der 1-stelligen Verknüpfung auf und den beiden ausgezeichneten Elementen und aus heißt Boolesche Algebra, wenn für alle Elemente die folgenden vier Axiome gelten:
- Kommutativität: und
- Distributivität: und
- Neutrale Elemente: und
- Komplementäres Element: und
Aufgabe: Wir betrachten die ganzen Zahlen mit der Multiplikation und der Addition und den neutralen Elementen und . Zeige, dass diese Struktur keine Boolesche Algebra ist. Welche Axiome werden erfüllt, welche nicht?
- Beide Verknüpfungen sind kommutativ, denn es gilt ja: und .
- Es gilt bekanntlich: . Die duale Regel dagegen gilt nicht! Zum Beispiel gilt: .
- Die Elemente und sind tatsächlich neutral: und .
- Es gibt keine komplementären Elemente! Bezeichnen wir wieder das komplementäre Element zu mit , dann müsste für alle gelten: und . ↯
Wie wir gesehen haben, gibt es sehr verschiedene Booleschen Algebren. Werfen wir noch einmal einen Blick auf unsere Beispiele und vergleichen die beiden folgenden Boolschen Algeben;
- Die Boolesche Algebra der Aussagenlogik hat genau zwei Elemente.
- Sei die einelementige Grundmenge . Dann hat die Boolesche Algebra der Potenzmenge ebenfalls genau zwei Elemente, nämlich die leere Menge und die Grundmenge .
Der Vergleich zeigt folgende Entsprechungen:
Menge: | ||
---|---|---|
Verknüpfungen: | Konjunktion | Durchschnitt |
Disjunktion | Vereinigung | |
Negation | Komplement | |
Neutrale Elemente: | Wahr | Grundmenge |
Falsch | Leere Menge |
Ersetzen wir nun in irgendeiner Regel die Verknüpfungen und Elemente der Booleschen Algebra der Aussagenlogik durch die entsprechenden Verknüpfungen der Booleschen Algebra der Potenzmenge, so gilt dort die Regel ganz genauso! Beispiel: Aus entsteht so .
Betrachten wir nun das dritte Beispiel, den Teilerverband. Auch hier fällt auf, dass unser konkretes Beispiel 210 genau 16 Elemente hat, also genauso viele wie die Potenzmenge einer Menge mit vier Elementen. Wir erstellen daher für alle hier behandelten Booleschen Algebren eine Übersetzungstabelle:
Allgemein | Aussagenlogik | Teilerverband | Potenzmenge | |
---|---|---|---|---|
Menge: | ||||
Verknüpfungen: | ||||
Neutrale Elemente: | ||||
Wenn wir solche Übersetzungstabellen erstellen können und bei der Übersetzung wahre Aussagen in wahre, und falsche Aussagen in falsche übergehen, werden die beiden verglichenen Strukturen isomorph (d.h. strukturgleich) genannt. Dabei müssen nicht nur die neutralen Elemente einander entsprechen, sondern alle Elemente der einen Struktur müssen genau einem Element der anderen Struktur entsprechen und umgekehrt. Wir werden das im Kapitel Abbildung, Funktion genauer ausführen. Zwei isomorphe Strukturen sind bis auf Umbenennungen gleich!
Für Boolesche Strukturen gilt nun folgender eigentlich erstaunlicher Satz:
Satz (Darstellungsatz für Boolesche Algebren)
Jede Boolsche Algebra entspricht der Boolschen Algebra einer Potenzmenge. Mathematisch ausgedrückt: jede Boolesche Algebra ist zur Booleschen Algebra einer Potenzmenge isomorph.
Den Beweis[1] wollen wir hier nicht führen, da wir dazu noch einiges an Definitionen und Hilfsmitteln bräuchten.