1 Einführung in die boolesche Algebra

Begründer und Namensgeber der booleschen Algebra ist der englische Mathematiker Ge-orge Boole. Boole wurde am 2. November 1815 in Lincoln geboren und starb am 18. Dezember 1864 in Ballintemple. Ursprünglich war er als Lehrer tätig, ehe er 1848 Ma-thematikprofessor am Queens College in Cork wurde. Boole begründete die moderne mathematische Logik, in dem er durch seine Algebra der Logik die klassische philosophische Logik formalisierte. Die Grundgedanken Booles wurden durch verschiedene Mathematiker, wie beispielsweise Ernst Schröder oder Giuseppe Peano, schließlich zu dem modifiziert was

heute unter boolesche Algebra verstanden wird. 1

Die boolesche Algebra findet im Alltag Anwendung beim Entwerfen von elektronischen Schaltungen bis hin zu Computern.

Dabei wird in der booleschen Algebra zunächst von den zwei Zuständen „wahr“ und „falsch“ ausgegangen. Diese entsprechen in einem elektronischen Schaltkreis den beiden möglichen Zuständen „Strom fließt“ und „Strom fließt nicht“ . Dieser Sachverhalt wird nun folgen-

dermaßen mathematisch modelliert ² :

Grundsätzlich wird von der Menge {0,1} ausgegangen. Es stehen also lediglich die Elemente 0 und 1 zur Verfügung. Nun wird der Zustand „Strom fließt“ durch die Zahl 1 und der Zustand „Strom fließt nicht“ durch die Zahl 0 modelliert. Darauf aufbauend sind in der booleschen Algebra die drei Operationen Konjunktion, Disjunktion und Negation definiert. Diese sollen im nächsten Kapitel ausführlich behandelt werden.

2 Grundlegende Operationen und Gesetze

2.1 Die Konjunktion

Die Konjunktion ist eine binäre Verknüpfung, die somit also von genau zwei Argumenten abhängig ist. Die Konjunktion wird auch die „Und-Verknüpfung“ genannt und durch das

mathematische Symbol ∧ in der Form a ∧ b ausgedrückt. Die Konjunktion ist per De-

finition genau dann 1, wenn das erste und das zweite Argument 1 ist. In jedem anderen Fall ist sie 0. Veranschaulichen lässt sich die Konjunktion anhand einer sogenannten Verknüpfungstafel (vgl. Abbildung 1). Hier werden alle Verknüpfungsmöglichkeiten der beiden Argumente bezüglich einer Konjukntion dargestellt. Sie verdeutlicht, dass eine Konjunktion tatsächlich nur dann 1 ist, wenn beide Argumente ebenfalls 1 sind.

¹ vgl. http://teacher.schule.at/schaltalgebra/boole.htmlbiogr

² vgl. Beutelspacher, 2007, S.191

2

Die Konjunktion lässt sich im Hinblick auf ihre praktische Anwendung leicht anhand einer Reihenschaltung verdeutlichen (vgl. Abbildung 2).

Die Argumente a und b stellen hier eine Reihenschaltung in einem Schaltkreis dar. Logischerweise kann in diesem Schaltkreis nur Strom fließen, wenn beide Schalter, also die Argumente a und b geschlossen sind. Strom fließt also nur dann, wenn beide Schalter auf „Strom fließt“ gestellt sind. In allen anderen Fällen ist der Stromkreis unterbrochen, Strom könnte somit nicht fließen. Dieser Sachverhalt wird durch eine Konjunktion ausgedrückt.

2.2 Die Disjunktion

Die Disjunktion ist ebenfalls eine binäre Verknüpfung. Sie wird auch die „Oder-Verknüpfung“

genannt und durch das mathematische Symbol ∨ in der Form a ∨ b dargestellt. Das „Oder“

dieser Disjunktion ist hier allerdings als „einschließendes Oder“ und nicht im Sinne von „entweder oder“ zu verstehen. Die Disjunktion ist per Definition genau dann 1, wenn das erste oder das zweite Argument 1 ist. Die Disjunktion ist also nur dann 0, wenn beide

verknüpften Argumente ebenfalls 0 sind Fall. Auch diese Verknüpfung lässt sich wieder anhand einer Verknüpfungstafel verdeutlichen (vgl. Abbildung 3):

Auch bei der Disjunktion wird der Alltagsbezug deutlich, wenn man sich eine Parallelschaltung vorstellt (vgl. Abbildung 4).

³ http://www.oldenbourg-wissenschaftsverlag.de/fm/694/3-486-58370-p.pdf

3

Die Argumente a und b stellen hier eine Parallelschaltung in einem Schaltkreis dar. In diesem Schaltkreis kann nur Strom fließen, wenn ein oder beide Schalter geschlossen sind. Strom fließt also nur dann, wenn mindestens ein Schalter beziehungsweise Argument auf „Strom fließt“ gestellt ist. Sind beide Schalter geöffnet ist der Stromkreis unterbrochen und kein Strom fließt. Genau dieser Sachverhalt wird durch eine Disjunktion ausgedrückt.

2.3 Die Negation

Die Negation ist keine binäre Verknüpfung, verlangt somit also lediglich ein Argument. Sie

wird auch Nicht-Operator genannt und durch das mathematische Symbol ¬ in der Form ¬a ausgedrückt. Die Negation ist 0, wenn das Argument 1 ist und 1 wenn das Argument

0 ist. Die Negation lässt sich ebenfalls anhand einer Verknüpfungstafel veranschaulichen (vgl. Abbildung 5).

Die drei vorgestellten Operationen können nun mehrfach hintereinander ausgeführt werden, so dass komplexere boolesche Ausdrücke erzeugt werden können. Die Operationen besitzen allerdings unterschiedliche Prioritäten. In einem booleschen Ausdruck wird nach einer festgelegten Reihenfolge zunächst die Negation, dann die Konjunktion und abschließend die Disjunktion ausgeführt. Höchste Priorität besitzt in der booleschen Algebra die Klammersetzung. Dank der Klammersetzung können also Teilausdrücke entgegen der festgelegten Priorität bevorzugt werden.

Neben den definierten Operationen gelten eine Reihe von Rechengesetzen, die nun genauer

in Satz 1 vorgestellt werden ⁵ .

⁴ http://www.oldenbourg-wissenschaftsverlag.de/fm/694/3-486-58370-p.pdf

⁵ vgl. Beutelspacher, 2007, S.191

4