InhaltVorheriges Kapitel Nächstes Kapitel

1 Boolesche Algebra und digitale Logik

1.2 Boolesche Algebra


Zur Behandlung mathematischer Probleme, wie sie z.B. bei der Lösung mathematischer Gleichungen auftreten, existieren Hilfsmittel, die unter der Bezeichnung "Algebra" zusammengefaßt werden.
Auch in der Digitaltechnik müssen komplexe Probleme mit geeigneten mathematischen Methoden behandelt werden.

Allerdings reduziert die Digitaltechnik die Anzahl der möglichen Informationszustände auf genau zwei. Obwohl für diese Zustände unterschiedliche Bezeichnungen üblich sind, wie z.B. 0/1, true/false, usw., zeigt sich eine starke Ähnlichkeit mit einem anderen Gebiet der Mathematik, der "formalen Logik".

Glücklicherweise existiert eine Logik, die für das hier vorliegende zweielementige Informationssystem entwickelt wurde. Es handelt sich um eine algebraische Struktur, die von dem englischen Mathematiker George Boole entwickelt und in dessen berühmter Veröffentlichung "An Investigation of the Laws of Thought" beschrieben wurde.

Diese Algebra wird inzwischen nach George Boole als "Boolesche Algebra" bezeichnet. Ihre große Bedeutung beruht auf ihren vielfältigen Anwendungsmöglichkeiten. Sie eignet sich zur Behandlung mengenalgebraischer Probleme, zur algebraischen Darstellung der Aussagenlogik sowie zur algebraischen Beschreibung umd Manipulation von Schaltkreisen.

Die Boolesche Algebra kann heute in vier Gebiete unterteilt werden:


Abb. 1.2: Gebiete der Booleschen Algebra.

Für die Digitaltechnik sind allerdings nur die ersten drei Gebiete von Bedeutung:

George Boole's Arbeiten wurden von anderen Mathematikern ergänzt, wobei insbesondere Hamilton, de Morgan und Shannon zu erwähnen sind.

Das Verdienst Claude E. Shannons ist es, die Anwendungsmöglichkeit der Booleschen Algebra bei der Behandlung von Schaltnetzen erkannt zu haben. Er zeigte, daß die prinzipiellen Eigenschaften von Serien- und Parallelschaltungen von Schaltern und Relais mit der zweielementigen Logik besonders gut beschrieben werden können.

Das von Claude Shannon grundlegend behandelte Spezialgebiet der Booleschen Algebra wird heute als "Schaltalgebra" bezeichnet.



1.2.1 Grundlagen der Booleschen Algebra

Die Boolesche Algebra soll an dieser Stelle in vereinfachter Form als ein System von Regeln (Postulaten und Theoremen) eingeführt werden, in dem die Verknüpfungen zwischen den binär (zweielementig) dargestellten Informationen beschrieben werden. Die zugrundeliegenden Operationen werden algebraisch durch Funktionen vermittelt, die als Boolesche Funktionen bezeichnet werden (abgekürzt: BFkten).

Diese Booleschen Funktionen zeichnen sich (per Definition) durch zwei Eigenschaften aus:

Jedes Funktionsargument (jeder Operand) kann nur den Wert "0" oder "1" annehmen,

Der Funktionswert (d.h. das Ergebnis, das nach Anwendung der Funktion auf die Operanden erhalten wird) kann ebenfalls nur den Wert "0" oder "1" annehmen.

Anmerkung:

Der Begriff der Booleschen Funktion muß ausdrücklich unterschieden werden von dem Begriff der Binäroperation bzw. der Binärfunktion:

Eine uneingeschränkt definierte Funktion kann eine beliebig große Anzahl von Argumenten (Operanden) n haben.

Hat die Funktion n = 1 Operanden, so spricht man von einer "unären Operation". Das bekannteste Beispiel einer unären Operation ist die Vorzeichenoperation ("+","-").

Hat die betrachtete Funktion n = 2 Operanden, so spricht man von einer "binären Operation" (Binäroperation). Beispiele sind die Operationen "Addition", "Subtraktion", etc..

Der gleiche Begriff "Binäroperation" wird auch dann häufig verwendet, wenn die Argumente nur binäre Werte (0/1) annehmen dürfen. Da an dieser Stelle auch Operationen behandelt werden sollen, die eine beliebige Anzahl binärer (dualer) Operanden besitzen können, entsteht offenbar ein Begriffskonflikt.

Zur Vermeidung dieser Mehrdeutigkeit wird für alle n-stelligen Funktionen (n = 1,2, ...), deren Argumente und Resultate binäre Größen sind, der Begriff "Boolesche Funktion" verwendet.


1.2.2 Mengendarstellungen in der Booleschen Algebra

Um die Regeln der Booleschen Algebra anschaulicher einzuführen, können aus der Mengenlehre bekannte Anschaungsformen herangezogen werden. Die grafische Beschreibung durch sogenannte Mengendiagramme erweist sich in diesem Zusammenhang als besonders geeignet.

Definition des Begriffes Menge:

Eine Menge ist die Zusammenfassung bestimmter, unterscheidbarer Objekte zu einem Ganzen.

Diese unterscheidbaren Objekte werden als Elemente der Menge bezeichnet.

Eine Menge kann definiert werden durch die Aufzählung ihrer Elemente.


Beispiele für Mengen:


InhaltVorheriges Kapitel Nächstes Kapitel