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 VereinigungBearbeiten

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ätBearbeiten

Beim Durchschnitt   und bei der Vereinigung   ist es egal, in welcher Reihenfolge du die Verknüpfungen ausführst.

  •  
  •  

KommutativitätBearbeiten

Beim Durchschnitt   und bei der Vereinigung   kannst du die Seiten vertauschen.

  •  
  •  

IdempotenzBearbeiten

Verknüpfst du eine Menge mit sich selbst, ändert sich nichts.

  •  
  •  

Neutrales ElementBearbeiten

Die Allklasse   ist ein neutrales Element für den Durchschnitt  , die leere Menge   ist ein neutrales Element für die Vereinigung  .

  •  
  •  

ExtremwerteBearbeiten

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ätBearbeiten

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 KomplementBearbeiten

Die Beweise findest du im Kapitel Differenz, symmetrische Differenz und Komplement.

Existenz des KomplementsBearbeiten

Zu jeder Menge gibt es ein Komplement  .

  •  
  •  

De Morgansche GesetzeBearbeiten

Das Komplement kann in einen Durchschnitt bzw. in eine Vereinigung "hereingezogen" werden.

  •  
  •  

Doppeltes KomplementBearbeiten

Ein doppeltes Komplement entfällt.

  •  

Grösstes und kleinstes ElementBearbeiten

  •  
  •  

Boolsche AlgebraBearbeiten

Eine Struktur mit den oben aufgeführten Eigenschaften wird Boolesche Algebra genannt. Die wichtigsten Beispiele sind die Potenzmengen   einer Grundmenge  .

PotenzmengeBearbeiten

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  .

 
Boolesche Algebra   - die Pfeile zeigen die Teilmengen-Beziehung

AussagenlogikBearbeiten

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.

TeilerverbandBearbeiten

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!

DefinitionBearbeiten

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:

  1. Kommutativität:       und    
  2. Distributivität:       und    
  3. Neutrale Elemente:      und    
  4. 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?

  1. Beide Verknüpfungen sind kommutativ, denn es gilt ja:   und  .
  2. Es gilt bekanntlich:  . Die duale Regel dagegen gilt nicht! Zum Beispiel gilt:  .
  3. Die Elemente   und   sind tatsächlich neutral:   und  .
  4. 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.