Was ist eine Boolesche Algebra?1 Halbgruppen Halbverbände

Wilhelm-Schickard-Institut fur
¨ Informatik
Arbeitsbereich Symbolisches Rechnen
Prof. Dr. Wolfgang Kuchlin
¨
Dipl. Inf. Christoph Zengler
04.05.2011
Was ist eine Boolesche Algebra?1
Mathematisch betrachtet ist eine Boolesche Algebra eine Algebraische Struktur. Eine Algebraische Struktur besteht
aus
1. einer nicht-leeren Menge A, dem Universum,
2. ausgezeichneten Elementen des Universums, z.B. 0 oder 1,
3. einstelligen oder mehrstelligen Operationen auf A, z.B. − : A → A oder + : A × A → A.
Aus den Grundlagen der Mathematik sind wahrscheinlich bereits einige Algebraische Strukturen bekannt, z.B.
• das kommutative Monoid (N; 0, +) der nat¨urlichen Zahlen mit Addition und der 0,
• die abelsche Gruppe (Z; 0, +, −) der ganzen Zahlen mit Addition, einstelliger Negation und der 0,
• der K¨orper (R; 0, 1, +, −, ·) der reellen Zahlen mit den u¨ blichen Operationen.
Aus dieser mathematischen Sicht ist eine Boolesche Algebra ein spezieller Verband. Da ein Verband wiederum aus
Halbverb¨anden besteht und diese wiederum spezielle Halbgruppen sind, wollen wir das Ganze bottom-up aufziehen
und uns von unten nach oben hocharbeiten.
Halbgruppen
Definition 1 (Halbgruppe). Eine Halbgruppe H = (H; ◦) besteht aus einer nicht-leeren Menge H und einer zweistelligen assoziativen Operation ◦ : H × H → H. H heißt eine kommutative Halbgruppe falls die Operation ◦
kommutativ ist.
Beispiel 1. Die positiven nat¨urlichen Zahlen mit der Addition bilden eine kommutative Halbgruppe (N \ {0}; +).
Offensichtlich ist N \ {0} eine nicht-leere Menge und die Addition ist eine zweistellige assoziative und kommutative
Operation auf dieser Menge.
Halbverb¨ande
Um zu verstehen, was ein Halbverband ist, m¨ussen wir zuerst das Konzept der Idempotenz kl¨aren.
Definition 2 (Idempotenz). Sei A = ∅ eine Menge und sei f : A × A → A eine zweistellige Operation auf A. f
heißt idempotent, falls f¨ur alle a ∈ A gilt, dass
f (a, a) = a.
Beispiel 2. Betrachten wir die Menge { , ⊥} der aussagenlogischen Wahrheitswerte mit der Verkn¨upfung ∧. Dann
ist ∧ idempotent, da ∧ = und ⊥ ∧ ⊥ = ⊥ gilt. Ebenso ist ∨ idempotent.
Nun k¨onnen wir einen Halbverband definieren:
Definition 3. Eine kommutative Halbgruppe (A; ◦) heißt ein Halbverband, falls ◦ idempotent ist.
1 Die Definitionen und Beispiele in dieser Abhandlung sind aus dem bisher unver¨
offentlichtem Buch ”Algebra und Logik” von Thomas Sturm
und Volker Weispfenning.
1
Mit anderen Worten: Ein Halbverband ist eine algebraische Struktur bestehend aus einer nicht-leeren Menge A und
einer zweistelligen Operation ◦ : A × A → A, die
1. assoziativ,
2. kommutativ und
3. idempotent
ist.
Verb¨ande
Nachdem wir nun wissen, was Halbverb¨ande sind, k¨onnen wir Verb¨ande definieren:
Definition 4. Seien (A; ) und (A; ) zwei Halbverb¨ande mit der Menge A und zwei unterschiedlichen zweistelligen
Operationen und . Dann heißt A = (A; , ) ein Verband, falls f¨ur alle a, b ∈ A die folgenden Absorptionsgesetze gelten:
a (a b) = a,
a (a b) = a.
Wir wissen bereits, dass eine Boolesche Algebra ein spezieller Verband ist, d.h. f¨ur ∧ und ∨ gelten die Absorbtionsgesetze. Dies kann man z.B. in der Aussagenlogik einfach u¨ berpr¨ufen: Es gilt sowohl a ∧ (a ∨ b) = a als auch
a ∨ (a ∧ b) = a f¨ur alle a, b ∈ { , ⊥}.
Ein Verband kann zus¨atzliche Eigenschaften besitzen. Zwei davon sind f¨ur uns von Interesse:
1. Ein Verband A heißt ein distributiver Verband, falls sowohl distributiv u¨ ber
ist. D.h. es gelten f¨ur alle a, b, c ∈ A folgende beiden Distributivgesetze:
a
(b
c) = (a
b)
(a
c) und a
(b
c) = (a
b)
als auch
(a
distributiv u¨ ber
c).
2. Eine Struktur A = (A; 0, 1, , ) heißt ein beschr¨ankter Verband, falls (A, , ) ein Verband ist und 0 ∈ A
ein neutrales Element f¨ur und 1 ∈ A ein neutrales Element f¨ur ist.
Eine Boolesche Algebra ist sowohl distributiv als auch beschr¨ankt. Wir wollen dies wieder anhand der Aussagenlogik illustrieren:
Beispiel 3. Wir wissen bereits, dass in der Aussagenlogik die Distributivgesetzte gelten.
f¨ur ∧, ⊥ ist das neutrale Element f¨ur ∨. Es gilt also f¨ur alle a ∈ { , ⊥}
a∧
ist das neutrale Element
= a sowie a ∨ ⊥ = a.
Boolesche Algebren
Definition 5 (Boolesche Algebra). Eine Struktur A = (A; 0, 1, , ,∗ ) heißt eine Boolesche Algebra, falls die
Struktur (A; 0, 1, , ) ein beschr¨ankter distributiver Verband ist und f¨ur alle a ∈ A gilt:
a
a∗ = 0,
a
a∗ = 1
F¨ur a ∈ A heißt a∗ dann das Komplement von a.
Auch diese letzte Eigenschaft k¨onnen wir anhand der Aussagenlogik zeigen:
Beispiel 4. Das Komplement in der Aussagenlogik ist die Negation ¬. Es gilt f¨ur alle a ∈ { , ⊥}:
a ∧ ¬a = ⊥ und a ∨ ¬a =
.
Nun kann man auch zeigen, dass das Komplement zu einem Element in einer Booleschen Algebra eindeutig bestimmt ist.
2
Satz 1 (Endeutigkeit des Komplements). Das Komplement a∗ ist das jeweils einzige Element, das die beiden Gleichungen
a a∗ = 0,
a a∗ = 1
simultan erf¨ullt.
Beweis. Sei b ∈ A mit a
b=0
b = 0 und a
b = 1. Dann folgt
b
= (a
(0 ist neutral f¨ur )
∗
a )
b
= (a
b)
(a
=1
(a∗
b)
= (a
∗
=a
= a∗
∗
a )
(a
0
(Komplementregel f¨ur Boolesche Algebra)
∗
b)
(Distributivgesetz)
(gilt nach Voraussetzung)
∗
(a
b)
(Komplementregel f¨ur Boolesche Algebra)
b)
(Distributivgesetz)
(gilt nach Voraussetzung)
= a∗
(0 ist neutral f¨ur )
Damit ist gezeigt, dass jedes Element, das beide Gleichungen simultan erf¨ullt, das Komplement a∗ von a sein muss
und dieses damit eindeutig bestimmt ist.
Aus der Eindeutigkeit des Komplements folgt auch die Involutivit¨at, d.h. a∗∗ = a. Auch diesen Fakt kennen wir
bereits aus der Aussagenlogik, in der f¨ur alle a ∈ { , ⊥} gilt ¬¬a = a.
In einer Booleschen Algebra haben auch die beiden Gesetze von de Morgan G¨ultigkeit, d.h.
a
b = (a∗
b∗ )∗ und a
b = (a∗
b∗ )∗ .
¨ Boolesche Algebren
Beispiele fur
Wie nun schon des o¨ fteren erw¨ahnt, ist das wohl bekannteste Beispiel f¨ur eine Boolesche Algebra die Aussagenlogik,
bzw. das Aussagenkalk¨ul. Dabei handelt es sich um die Struktur ({ , ⊥}; ⊥, , ∧, ∨, ¬). Dies ist eine zweielementige Boolesche Algebra, d.h. das Universum besteht aus nur zwei Elementen. Es gibt jedoch durchaus auch Boolesche
Algebren mit mehr als zwei Elementen.
Beispiel 5. Sei M eine Menge und ℘(M ) die Potenzmenge dieser Menge (die Menge aller Teilmengen von M ).
Definiere f¨ur A ∈ ℘(M ) das Komplement A = M \ A. Dann bildet die Struktur (℘(M ); ∅, M, ∪, ∩, ) eine
Boolesche Algebra, die Potenzmengenalgebra von M .
Die Potenzmengenalgebra ist genau dann unendlich, wenn M unendlich ist. In diesem Fall ist die Potenzmengenalgebra sogar u¨ berabz¨ahlbar unendlich. Man kann jedoch auch abz¨ahlbar unendliche Boolesche Algebren konstruieren. Wir wollen es hier jedoch bei diesen beiden Beispielen belassen.
Rekapitulation
Wir wollen noch einmal zusammenfassen, welche Eigenschaften eine Boolesche Algebra (A; 0, 1, , ,∗ ) hat:
• A ist eine nicht-leere Menge (wg. Halbgruppe).
• 0 ∈ A ist neutrales Element f¨ur
(wg. beschr¨anktem Verband).
• 1 ∈ A ist neutrales Element f¨ur
(wg. beschr¨anktem Verband).
•
und
sind jeweils
– assoziativ und kommutativ (wg. kommutativer Halbgruppe),
– idempotent (wg. Halbverband) und
– distributiv u¨ bereinander (wg. distributivem Verband).
• Es gelten die Absorptionsgesetze (wg. Verband).
• F¨ur alle a ∈ A gilt a
a∗ = 0 und a
a∗ = 1 (wg. Boolescher Algebra).
3

Download Report