Boolesche Algebra

Aus Aussagenlogik

Wechseln zu: Navigation, Suche

Eine Boolesche Algebra oder, im Mathe-Zoo richtig eingeordnet, ein Boolescher Verband ist ein sehr machtvolles Rechenwerkzeug, mit dem mindestens drei überaus nützliche Bereiche der Menschenwelt möglich und gut berechenbar werden:

  1. die Folgung oder Logik, die uns Voraussagungen und Planungen erlaubt, die für Jäger, Fallensteller, Ingenieure und Hausfrauen die Grundlage für den Haus- oder Menschenverstand bilden und überlebenswichtig sind. – Und mindestens erlaubt die Folgung die genaue, widerspruchsfreie Schlußweise in der Mathematik;
  2. die Schaltalgebra, mit der jedes heutige Telefon, jedes neuere Auto, jeder Rechner, jedes Verkehrsflugzeug, Kraftwerk und jede Ladenkasse funktionieren und mit der Bill Gates zum reichsten Mann der Welt geworden ist;
  3. die anschauliche Mengenlehre, die vom Hausverstand schon recht gut abgedeckt wird;
  4. die Wahrscheinlichkeitsrechnung.


Inhaltsverzeichnis

Wesen und Geschichte

Der Logik-Kalkül und mithin die Boolesche Algebra haben ihre Wurzeln im gewöhnlichen gesunden Menschenverstand – dieser ist bereits ein Teil der Booleschen Algebra. Viele Dinge der B.A. leuchten dem verständigen Hausmenschen direkt ein, und die B.A. bereichert seinen Hausverstand.
Schon die griechischen Philosophen haben wesentliche Sätze der B.A. ausgesprochen, so Aristoteles: Wenn A aus B folgt und B aus C, dann folgt auch A aus C. Dieser Satz ist in der B.A. enthalten. Gottfried Wilhelm Leibniz (1646–1716) hat in seiner Schrift De Formae Logicae per linearum ductus, um 1690, den Logik-Kalkül beschrieben, allerdings die Schrift nicht veröffentlicht.
George Boole (1815–1864) hat den Logik- und Mengenkalkül wiederum erdacht und ihn in seiner Schrift The Mathematical Analysis of Logic 1847 veröffentlicht. Die Weiterentwicklung auf den heutigen Stand wird im Abschnitt Geschichte beschrieben.

Vorgehensweise

Ebenso wie Leibniz und Boole wollen wir hier einen möglichst knappen und übersichtlichen Aufbau des Logikkalküls beginnen. Aus der Festlegung von möglichst wenigen Grundforderungen = Axiomen soll das gesamte Logik-Denkgebäude entstehen.

Somit kommt jetzt eine möglichst klare, sparsame Grundlegung der Booleschen Algebra:


Festlegung (Definition)

Wenn M eine Menge von Elementen ist, z.B. M = {0, 1}, und  +  und  ·  zwei Verknüpfungen (Abbildungen, Operatoren) von M x M in M sind, dann heißt die Menge A = {M, +, · , ' } genau dann eine Boolesche Algebra , wenn die vier Axiome A1 bis A4 gelten:

A1. Die Verknüpfungen + und · sind jeweils tauschbar (kommutativ), d. h.:  
Für alle a, b aus M gilt
   a + b = b + a    
und
   a · b = b · a .

A2. In M gibt es für jede der beiden Verknüpfungen + und · ein Einselement oder neutrales Element, genannt 0 bzw. 1, so daß für jedes a aus M gilt:
   a + 0 = a
und
   a · 1 = a .

A3. Jede der Verknüpfungen + und · ist verteilend (distributiv) gegenüber der anderen, das heißt
   a · (b + c) = a · b  +  a · c (wie beim Rechnen mit Zahlen)
und
   a + b · c = (a + b) · (a + c) (anders als beim Rechnen mit Zahlen, gewöhnungsbedürftig)

A4. Zu jedem a in M gibt es ein entgegengesetztes (inverses) Element   a'  in M, so daß gilt:
   a + a' = 1
und
   a · a' = 0 .


Mit diesen 4 Axiomen können wir die gesamte Schaltalgebra, Aussagenlogik und Mengenlehre begründen <freu>.


Sprechweise

Die Verknüpfung  +  sprechen wir als oder, die Verknüpfung  ·   als und .


Schreibweise

   a := b    bedeutet:  a  ist vereinbart (definiert, festgelegt) als  b .

Die Verknüpfung  ·  wird, wie es in der Mathematik und Physik auch gerne gemacht wird, beim Aufschreiben einfach weggelassen, z.B.
100 · km = 100 km , x · y = xy usw.; in gleicher Weise können wir für alle a, b aus M schreiben:
   ab := a · b

Klammerregel: Wie auch in der Zahlenalgebra üblich, können wir die Klammern um Ausdrücke mit und fortlassen:    ab   :=  (ab) = (a · b)

Andere Schreibweisen: Statt  +  und  · können wir auch zum Beispiel  v   und  ^  nehmen, wie es die Aussagenlogiker gerne machen; oder irgendwelche anderen Zeichen.

Sätze als Arbeitswerkzeug

Nun wollen wir mit einigen abgeleiteten Sätzen uns ein schönes Arbeitswerkzeug zusammenstellen:

Feststellung: (Eine Feststellung ist ein ganz winziges Sätzlein.)
Wenn  a  und  b  aus M sind, sind  a + b  und  ab  und daraus Zusammengesetztes (genannt Ausdruck) z.B.    (ab + ab') · bc' auch wieder aus M.
Beweis: Das folgt unmittelbar aus der Festlegung, daß  +  und  ·  Abbildungen von M x M in M sind.


Satz 1, Umstülp-Regel, Dualitätsprinzip

Zu jeder (gültigen) Gleichung können wir die dazu umgestülpte (duale) Gleichung bilden, indem wir jedes  +  gegen  · und jede  0  gegen  1  austauschen, und umgekehrt, und auch diese umgestülpte Gleichung ist wieder gültig.

Beweis: Weil diese Austauschbarkeit (Umstülpbarkeit) bereits in den Axiomen A1 bis A4 enthalten ist, sind auch alle Ableitungen aus den Axiomen gültig, wenn sie umgestülpt werden.

Folgerung: Entsprechend kommen sämtliche folgenden Sätze  im Doppelpack mit ihrer Umstülpung  daher.


Satz 2, Reflexivität:

a + a = a
Beweis:
a = a + 0            nach A2
   = a + aa'         nach A4
   = (a + a)(a+a')  nach A3
   = (a + a)(1)      nach A4
   = (a + a) · 1    (Schreibweise)
   = a + a           nach A2

Sowie entstprechend:
a · a = a
Beweis:
a = a · 1             nach A2
   = a · (a+a')      nach A4
   = aa + aa'       nach A3
   = aa + 0         nach A4
   = aa               nach A2


Satz 3, Aufsaugung mit  0  und  1  (Absorption)  [1];

a + 1 = 1 und a0 = 0

Beweis:
1 = a + a'              nach A4
   = a + a' · 1         nach A4
   = (a + a')( a + 1) nach A3
   = 1 · ( a + 1)      nach A4
   = a + 1              nach A2

entsprechend:
0 = a · a'              nach A4
   = a · (a' + 0)      nach A4
   = a · a' + a · 0   nach A3
   = 0 + a · 0        nach A4
   = a · 0              nach A2

Satz 4, Aufsaugung einer Untermenge  (Absorption)  [2];

Für je zwei Elemente a und b aus M gilt:
a + ab = a    und    a (a + b) = a
Beweis:
a = 1a            nach A2
   = (1 + b) a   nach A1 und Satz 3
   = 1a + ba    nach A2
   = a + ba      nach A2
   = a + ab      nach A1

Satz 5, Reihenfolgeverträglichkeit (Assoziativität):

Beide Verfahren  +  und  ·  sind reihenfolgeverträglich (assoziativ), d.h.:
Für alle a, b, c aus M gilt:
   (a + b) + c  =  a + (b + c)
und
   ab · c = a · bc

Der Beweis ist vergleichsweise aufwendig:
....
....
....

Satz 6

Zu jedem Ding a aus M ist das umgekehrte Element a' eindeutig bestimmt: Nur ein einziges Element a' aus M erfüllt die Bedingung nach A4.
Beweis durch Ausrechnen:
Sei A4 für x und auch für y aus M erfüllt, dann gilt nach A4:
    a + x = 1, ax = 0
und
    a + y = 1, ay = 0 .
Alsdann rechnen wir:
x = 1x           nach A2
   = (a + y) x  nach Voraussetzung
   = ax +yx    nach A1 und A3
   = 0 + yx     nach Voraussetzung
   = yx           nach A2
   = xy           nach A1
   = xy + 0     nach A2
   = xy + ay   nach Voraussetzung
   = (x + a) y   nach A3 und A1
   = 1y           nach Voraussetzung
   = y            nach A2


Weitere Merkmale

Mächtigkeit

Eine Boolesche Algebra enthält mindestens 0 und 1 (welches sinnvollerweise nicht selb sind), also zwei Dinger. Gleichzeitig ist diese Zwei-Dinger-Algebra die für die Arbeits- und Genußmenschen wichtigste Algebra, denn mit ihr sind alle Rechner, die meisten Maschinen und Autos und jeder neuere Fernseher und das gesamte Internet gebaut.


Satz: Die Untermengen einer Menge M bilden einen Booleschen Verband. Seine Mächtigkeit beträgt 2 hoch |M|, wobei |M| die Mächtigkeit von M ist.


Satz: Jede Boolesche Algebra ist aufbaugleich (isomorph) zu der Untermengen-Booleschen-Algebra einer Menge.


Folgerung: Die Elementezahl der Dingemenge in jeder Boooleschen Algebra beträgt 2 hoch n (mit  n  von  1  bis ganz viel); die Mächtigkeit kann auch abzählbar unendlich oder auch überabzählbar unendlich sein:
Die Untermengen der natürlichen Zahlen und der Bruchzahlen (rationalen Zahlen) sind abzählbar unendlich, die der reellen Zahlen sind überabzählbar unendlich.

Persönliche Werkzeuge