Boolesche Algebra

Der englische Mathematiker George Boole hat um 1850 eine Algebra entwickelt, die mit nur zwei Werten auskommt: 0 und 1. Aus dieser Idee ist später die mathematische Grundlage geworden, auf der die gesamte Digitaltechnik aufbaut.

Im Unterschied zur gewohnten Algebra, bei der Variablen beliebige Zahlenwerte annehmen, hat eine Variable in der Booleschen Algebra immer genau einen von zwei Zuständen:

• 0 — falsch, aus, kein Signal, kein Strom
• 1 — wahr, ein, Signal, Strom

Welche reale Bedeutung 0 und 1 haben, hängt vom Anwendungsfall ab. Bei einem Endschalter ist 1 das gedrückte Signal, bei einem Druckwächter das Erreichen einer Schwelle, bei einer SPS-Verriegelung die Erfüllung einer Bedingung. Die Rechenregeln bleiben in allen Fällen dieselben.

Aus der Algebra mit nur zwei Werten lassen sich zwei Dinge ableiten: Erstens kann man logische Bedingungen als mathematische Ausdrücke schreiben. Zweitens kann man diese Ausdrücke mit klaren Regeln umformen — etwa um eine Schaltung mit weniger Kontakten umzusetzen oder einen SPS-Code übersichtlicher zu machen.

Mit drei Grundverknüpfungen lässt sich jede beliebige boolesche Funktion aufbauen.

UND-Verknüpfung (Konjunktion)

Eine UND-Verknüpfung ist genau dann 1, wenn alle Eingänge 1 sind.

Statt des Multiplikationspunkts wird oft die Schreibweise A ∧ B oder einfach AB verwendet. Im Beitrag bleiben wir beim Punkt.

ODER-Verknüpfung (Disjunktion)

Eine ODER-Verknüpfung ist 1, sobald mindestens ein Eingang 1 ist.

Das + ist hier kein gewöhnliches Plus — es bedeutet ODER, nicht Addition. Eine alternative Schreibweise ist A ∨ B.

NICHT-Verknüpfung (Negation)

Die NICHT-Verknüpfung kehrt den Wert um. Aus 0 wird 1, aus 1 wird 0.

Geschrieben wird die Negation als Querstrich über der Variablen (Ā), als ¬A oder als !A. Wir verwenden den Querstrich.

Wahrheitstabelle — das Standardwerkzeug

Die Wahrheitstabelle ist die wichtigste Darstellungsform für boolesche Funktionen. In den linken Spalten stehen alle möglichen Eingangskombinationen, in der rechten Spalte das Ergebnis. Bei zwei Eingängen gibt es genau 2² = 4 Kombinationen, bei drei Eingängen 2³ = 8.

Für die drei Grundverknüpfungen sieht das so aus:

Und für die Negation mit einem Eingang:

Wichtig: Die Eingangskombinationen werden systematisch durchnummeriert wie eine Binärzahl. In der ersten Zeile steht 00, dann 01, 10, 11. So ist sichergestellt, dass keine Kombination vergessen wird. Wie man Wahrheitstabellen für mehr Eingänge systematisch aufbaut und zur grafischen Minimierung mit KV-Diagrammen einsetzt, ist ein eigenes Thema; hier reicht uns die Tabelle als Werkzeug, um die Verknüpfungen zu beschreiben und später die Normalformen abzuleiten.

Die elektronische Umsetzung der Verknüpfungen — also die Schaltsymbole und Bauformen der einzelnen Gatter, einschließlich NAND, NOR und XOR — gehört in den eigenen Beitrag zu den Logikgattern. Hier interessiert nur die mathematische Verknüpfung.

Boolesche Ausdrücke lassen sich mit festen Regeln umformen — ähnlich wie in der gewohnten Algebra, aber mit eigenen Besonderheiten. Wer die Regeln kennt, kann lange Bedingungen kürzer formulieren, ohne ihren Sinn zu verändern.

Kommutativgesetz — die Reihenfolge der Operanden ist egal:

A · B = B · A
A + B = B + A

Assoziativgesetz — bei gleichartigen Verknüpfungen ist die Klammerung beliebig:

(A · B) · C = A · (B · C)
(A + B) + C = A + (B + C)

Distributivgesetz — UND verteilt sich über ODER und umgekehrt:

A · (B + C) = (A · B) + (A · C)
A + (B · C) = (A + B) · (A + C)

Die zweite Form fällt aus der gewohnten Algebra heraus — sie gilt für Zahlen nicht, für boolesche Ausdrücke schon.

Idempotenzgesetz — eine Variable verknüpft mit sich selbst ergibt sich selbst:

A · A = A
A + A = A

Damit gibt es in der Booleschen Algebra keine Quadrate und keine Verdopplungen — A · A ist eben nicht A², sondern wieder A.

Neutralitätsgesetz — 0 und 1 sind die neutralen Elemente:

A · 1 = A           A + 0 = A
A · 0 = 0           A + 1 = 1

Beachtenswert ist A + 1 = 1: Eine ODER-Verknüpfung mit einer konstanten 1 macht den ganzen Ausdruck zu 1.

Komplementärgesetz — eine Variable mit ihrer Negation:

A · Ā = 0
A + Ā = 1

Eine Bedingung und ihr Gegenteil können nicht gleichzeitig erfüllt sein, aber eine von beiden ist immer erfüllt.

Absorptionsgesetz — kürzt überflüssige Teile heraus:

A + (A · B) = A
A · (A + B) = A

Wenn A bereits in einem Ausdruck steht und gleichzeitig in einer Erweiterung mit B auftaucht, dominiert das einfache A.

Doppelte Negation — zweimal verneint ergibt das Original:

A̿ = A

Die beiden De-Morgan-Gesetze sind das mächtigste Werkzeug, um Negationen umzuformen. Sie verbinden UND und ODER über die Negation und lauten:

A · B = Ā + B̄         (Querstrich über dem gesamten Produkt)
A + B = Ā · B̄         (Querstrich über der gesamten Summe)

In Worten: Wer ein UND negiert, bekommt ein ODER der einzelnen Negationen — und umgekehrt. Der lange Querstrich bricht beim Anwenden des Gesetzes in zwei kurze Querstriche auf, gleichzeitig kippt der Operator: aus · wird +, aus + wird ·.

Die Regel gilt auch für mehr als zwei Variablen:

A · B · C = Ā + B̄ + C̄
A + B + C = Ā · B̄ · C̄

Warum das in der Praxis wichtig ist

Ein typischer Fall: Eine Bedingung ist negativ formuliert, soll aber positiv ausgewertet werden. Statt „Anlage NICHT (in Störung ODER im Handbetrieb)“ lässt sich mit De Morgan schreiben „Anlage NICHT in Störung UND NICHT im Handbetrieb“ — der gleiche Gedanke, aber mit zwei sauberen Bedingungen statt einer großen Negation.

In Hardware-Schaltungen spielen die Gesetze eine zentrale Rolle, weil sich aus NAND-Bausteinen (negiertem UND) jede beliebige Funktion aufbauen lässt — Gleiches gilt für NOR (negiertes ODER). Die Begründung steckt direkt in den De-Morgan-Gesetzen.

Vereinfachen bedeutet: Einen Ausdruck so umformen, dass er mit weniger Variablen, weniger Operationen oder kürzerer Schreibweise dieselbe Wahrheitstabelle liefert. Der Sinn ist ganz praktisch — weniger Gatter in der Schaltung, weniger Kontakte im Schaltschrank, weniger Anweisungen im SPS-Programm, weniger Fehlerquellen.

Das Vorgehen

Es gibt kein starres Schema, aber eine bewährte Reihenfolge:

1. Klammern auflösen oder ausklammern (Distributivgesetz)
2. Doppelte Negationen entfernen (A̿ = A)
3. De Morgan anwenden, wenn lange Querstriche stören
4. Idempotenz nutzen (A · A = A, A + A = A)
5. Komplementärterme erkennen (A + Ā = 1, A · Ā = 0)
6. Absorption anwenden, wo möglich

Wer mit einer komplexen Funktion arbeitet und keinen Weg findet, kann die grafische Minimierung mit KV-Diagrammen anwenden. Das ist ein eigenes Thema und wird im zugehörigen Beitrag zu Wahrheitstabellen und KV-Diagrammen behandelt. Solange die Variablenanzahl überschaubar bleibt, kommt man algebraisch gut zurecht.

Beispiel Schritt für Schritt

Gegeben: Y = A · B + A · B̄ + Ā · B

Schritt 1: A aus den ersten beiden Termen ausklammern
Y = A · (B + B̄) + Ā · B

Schritt 2: Komplementärgesetz B + B̄ = 1
Y = A · 1 + Ā · B

Schritt 3: Neutralitätsgesetz A · 1 = A
Y = A + Ā · B

Schritt 4: zweites Distributivgesetz (A + Ā) · (A + B)
Y = (A + Ā) · (A + B)

Schritt 5: Komplementärgesetz A + Ā = 1
Y = 1 · (A + B)

Schritt 6: Neutralität
Y = A + B

Aus drei UND-Termen mit insgesamt sechs Variablenauftritten ist eine schlichte ODER-Verknüpfung von zwei Variablen geworden.

Jede beliebige boolesche Funktion lässt sich in zwei standardisierten Schreibweisen darstellen. Diese Normalformen sind eindeutig zu jeder Wahrheitstabelle ableitbar und bilden den Ausgangspunkt jeder weiteren Minimierung.

Disjunktive Normalform (DNF)

Eine Summe von UND-Termen. Jeder UND-Term enthält alle Eingangsvariablen — entweder direkt oder negiert. Such vollständige UND-Terme heißen Minterme.

Allgemein:

Y = Minterm1 + Minterm2 + Minterm3 + …

Aufstellen aus der Wahrheitstabelle: Jede Zeile mit Y = 1 liefert einen Minterm. In diesem Minterm steht jede Variable, die in dieser Zeile 1 ist, direkt; jede Variable, die 0 ist, negiert.

Konjunktive Normalform (KNF)

Ein Produkt von ODER-Termen. Jeder ODER-Term enthält alle Eingangsvariablen direkt oder negiert. Diese vollständigen ODER-Terme heißen Maxterme.

Allgemein:

Y = Maxterm1 · Maxterm2 · Maxterm3 · …

Aufstellen aus der Wahrheitstabelle: Jede Zeile mit Y = 0 liefert einen Maxterm. In diesem Maxterm steht jede Variable, die in dieser Zeile 0 ist, direkt; jede Variable, die 1 ist, negiert. (Das wirkt zunächst verdreht, ergibt sich aber direkt aus De Morgan.)

Beispiel

Gegeben sei diese Wahrheitstabelle:

DNF — aus den Zeilen mit Y = 1:

• Zeile 2 (0,0,1) → Ā · B̄ · C
• Zeile 4 (0,1,1) → Ā · B · C
• Zeile 6 (1,0,1) → A · B̄ · C
• Zeile 7 (1,1,0) → A · B · C̄
• Zeile 8 (1,1,1) → A · B · C

Y_DNF = Ā · B̄ · C + Ā · B · C + A · B̄ · C + A · B · C̄ + A · B · C

KNF — aus den Zeilen mit Y = 0:

• Zeile 1 (0,0,0) → A + B + C
• Zeile 3 (0,1,0) → A + B̄ + C
• Zeile 5 (1,0,0) → Ā + B + C

Y_KNF = (A + B + C) · (A + B̄ + C) · (Ā + B + C)

Beide Ausdrücke beschreiben dieselbe Funktion. Die DNF hat drei Variablen mal fünf Terme, die KNF drei mal drei. Welche Form schlanker ist, hängt von der Funktion ab: Sind in der Wahrheitstabelle wenige Einsen, ist die DNF kürzer; sind wenige Nullen vorhanden, ist die KNF kürzer.

Wann nimmt man welche?

• DNF wird häufiger verwendet, weil sich Summen von Produkten gut in SPS-Logik und in Schaltungen mit AND-OR-Struktur abbilden lassen.
• KNF ist nützlich, wenn die Funktion über die wenigen Fälle definiert ist, in denen das Ergebnis 0 sein soll (typisch bei Sperrbedingungen).

Beide Normalformen sind in der Regel noch nicht minimal. Die Minimierung erfolgt entweder algebraisch (Kapitel 5) oder grafisch mit dem KV-Diagramm (eigener Beitrag).

Die Verbindung zwischen Boolescher Algebra und der realen Technik wird besonders im Begriff der Schaltalgebra deutlich: Eine Reihenschaltung von Kontakten verhält sich wie eine UND-Verknüpfung, eine Parallelschaltung wie eine ODER-Verknüpfung.

Auf der linken Seite muss der Strom durch beide Kontakte fließen — beide Schalter müssen geschlossen sein, damit die Lampe leuchtet. Auf der rechten Seite reicht ein geschlossener Schalter aus.

Die Übertragung auf SPS-Programme

Dasselbe Prinzip steckt in jedem SPS-Programm. Eine UND-Verknüpfung im Funktionsplan (FUP) bedeutet: Alle Eingänge müssen 1 sein, damit der Ausgang 1 wird. Im Kontaktplan (KOP) sind das wie im elektrischen Schaltplan Kontakte in Reihe. Eine ODER-Verknüpfung sind Kontakte in Parallel. Die Boolesche Algebra bleibt das mathematische Werkzeug, mit dem sich diese Verknüpfungen sauber formulieren und vereinfachen lassen — unabhängig davon, ob am Ende eine Verdrahtung oder ein SPS-Code steht.