Benutzer:Jürgen-Michael Glubrecht/Mengenalgebra
Mengenalgebra
BearbeitenIn den vorangegangenen Kapiteln haben wir verschiedene Verknüpfungen zwischen Mengen kennengelernt. Die Regeln, die für diese Verknüpfungen gelten, sind hier übersichtlich zusammengestellt. , , , seine beliebige Mengen.
Regeln für den Durchschnitt und die Vereinigung
BearbeitenDurchschnitt und Vereinigung verhalten sich zueinander "dual": wenn du in einer Regel mit und mit vertauscht, erhältst du wieder eine gültige Regel!
Assoziativität
BearbeitenBeim Durchschnitt und bei der Vereinigung ist es egal, in welcher Reihenfolge du die Verknüpfungen ausführst.
Kommutativität
BearbeitenBeim Durchschnitt und bei der Vereinigung kannst du die Seiten vertauschen.
Idempotenz
BearbeitenVerknüpfst du eine Menge mit sich selbst, ändert sich nichts.
Neutrales Element
BearbeitenDie Allklasse ist ein neutrales Element für den Durchschnitt , die leere Menge ist ein neutrales Element für die Vereinigung .
Extremwerte
BearbeitenBezü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
BearbeitenEin 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
BearbeitenExistenz des Komplements
BearbeitenZu jeder Menge gibt es ein Komplement .
De Morgansche Gesetze
BearbeitenDas Komplement kann in einen Durchschnitt bzw. in eine Vereinigung "hereingezogen" werden.
Doppeltes Komplement
BearbeitenEin doppeltes Komplement entfällt.
Grösstes und kleinstes Element
BearbeitenBoolsche Algebra
BearbeitenEine Struktur mit den oben aufgeführten Eigenschaften wird Boolesche Algebra genannt. Die wichtigsten Beispiele sind die Potenzmengen einer Grundmenge .
Potenzmenge
BearbeitenBeispiel (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
BearbeitenIn den Beweisen für die Mengenesetze 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
BearbeitenBeispiel (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 ixt .
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
BearbeitenNun 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 heisst 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 Algebar 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 hat 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.
Einzelnachweise
Bearbeiten- ↑ Einen Beweis findest du beispielsweise hier: Darstellungssatz für Boolesche Algebren