Logo

DISKRETE MATHEMATIK
Erich Prisner
Sommersemester 2000

Boolesche Algebra

Definition: Gegeben sei ein Verband (B,Ù,Ú).
Falls außerdem folgende Regeln gelten (jeweils für alle a,b,c Î B):
  1. Distributivgesetze: a Ù (b Ú c) = (a Ù b) Ú (a Ù c), sowie
    a Ú (b Ù c) = (a Ú b) Ù (a Ú c).
  2. Existenz von 0 und 1: $0, 1 Î B "a Î B: a Ù 1 = a, a Ú 0 = a,
  3. Existenz eines Komplements:
    "a Î B $Øa Î B: a Ù Øa = 0, a Ú Øa = 1,
so nennt man (B,Ù,Ú) eine Boolesche Algebra
(Idempotenz ergibt sich sogar automatisch aus obigen Regeln zusammen mit Kommunitativität, Assoziativität und Absorption.) Diese Regeln wurden von George Boole formuliert.

In jeder Booleschen Algebra (B,Ù,Ú) gilt:
Doppelte Verneinung: ØØa = a.
de Morgan'sche Regeln:
Ø(a Ù b) = Ø a Ú Ø b, sowie Ø (a Ú b) = Ø a Ù Ø b.

Wie sehen Boolesche Algebren aus und "wie viele" gibt es? Typische Beispiele sind Potenzmengenverbände (P(M),Ù, Ú), oder als verbandsgeordnete Mengen ausgedrückt: (P(M),Í). Für endliches M haben diese Algebren 2n Elemente. Rechts ist das Hasse-Diagramm des entstehenden Potenzmengenverbands für ein 4-elementiges M abgebildet.
Interessanterweise is jede endliche Boolesche Algebra zu einem Potenzmengenverband isomorph. Boolesche Algebren sind also selten und sehr konkret.

Für jede endliche Boolesche Algebra (B,Ù,Ú) gibt es eine Menge M und eine Bijektion f: B ® P(M), so daß für alle x,y Î B gilt:
  • f(0) = Æ, f(1) = M,
  • f(x Ú y) = f(x) Ç f(y), und f(x Ù y) = f(x) È f(y),
  • f(Ø x) = M \ f(x).
D.h. (B,Ù,Ú) ist zu (P(M),Ç, È) isomorph.
Beweis:

Allerdings gibt es unendliche Boolesche Algebren, die nicht zu einem Potenzmengenverband isomorph sind.

Übungsaufgabe: Betrachten Sie die Menge CF(N) aller Teilmengen S der Menge N der natürlichen Zahlen, die endlich sind oder für die das Komplement N\S endlich ist. Zeigen Sie, daß (CF(N),Ç,È) zwar eine Boolesche Algebra ist, aber zu keinem Potenzmengenverband isomorph ist.

Genauso wie kartesische Produkte von Verbänden wieder Verbände sind, sind auch kartesische Produkte von Booleschen Algebren wieder Boolesche Algebren.

Für jedes i Î I sei (Bi,Ùi, Úi) eine Boolesche Algebra. Dann ist das kartesische Produkt i Î I Bi wieder eine Boolesche Algebra. Beweis:
Tatsächlich ist (P(M),Ç, È) zu x Î M (P({x}),Ç, È) isomorph.

Normalformen

A, B, C seien beliebige Teilmengen einer Menge M. Die rechts skizzierte Menge
(((A È (M\B)) Ç (M \ (C Ç (M\A))) È A ) ) Ç (B È (M\C))
läßt sich auch in der kanonischen disjunktiven Normalform
((M\A) Ç (M\B) Ç (M\C)) È (A Ç (M\B) Ç (M\C)) È (A Ç B Ç (M\C)) È (A Ç B Ç C) ausdrücken (Vereinigung von vier der acht möglichen entstehenden Teilmengen von M). Das läßt sich verallgemeinern:

(B,Ù,Ú) sei eine Boolesche Algebra. f: Bn ® B sei eine n-stellige Verknüpfung auf B.
Bildet f nicht alles auf 0 ab, so läßt sich f als kanonische disjunktive Normalform ausdrücken.
Bildet f nicht alles auf 1 ab, so läßt sich f als kanonische konjunktive Normalform ausdrücken.
Beweis für endliches B: Nach obigem Satz können wir uns auf Boolesche Algebren der Form i Î M (P({x}),Ç, È) beschränken. Dann können wir einfach in jeder Koordinate das Resultat für 2-elementige Boolesche Algebren (Aussagenalgebren) benutzen.
Beweis für beliebiges B.

Satz von Sperner

Satz von Sperner Wir betrachten den Potenzmengenverband (P({1,2,...,n}), Ç,È). Dann ist die maximale Anzahl der Elemente in einer Antikette gleich
(
n
n/2
 ) für gerades n, bzw. (
n
(n+1)/2
 ) für ungerades n
Beweis

Test

Ist ({1,2,3,4,6,12},kgV,ggT) eine Boolesche Algebra?

Ist ({1,2,3,5,6,10,15,30},kgV,ggT) eine Boolesche Algebra?

Weiter zu ...
Erich Prisner
File partially translated from TEX by T TH, version 2.53.
erstellt im Februar 2000.