Boolesche Funktionen: Wahrheitstabellen verstehen

Stell dir eine Schaltung vor: Ein Schalter ist AN (1) oder AUS (0), und eine Lampe leuchtet (1) oder nicht (0). So etwas beschreibt eine Boolesche Funktion. Sie bekommt Eingaben, und jede Eingabe ist 0 oder 1. Dazu gibt sie einen Wert aus, der ebenfalls 0 oder 1 ist. Wir benutzen hier die wichtigste boolesche Algebra, die nur die zwei Elemente 0 und 1 hat. Dabei steht 0 für „falsch“ und 1 für „wahr“. Das Eingangs-Ausgangs-Verhalten jeder möglichen digitalen Schaltung kann durch einen booleschen Ausdruck modelliert werden.

Eine Wahrheitstafel (auch Wahrheitstabelle) listet für jede mögliche Eingabe den Ausgang auf. Wie viele Zeilen sie hat, hängt von der Zahl der Eingangsvariablen ab: Anzahl Zeilen = 2 hoch (Anzahl der Eingangsvariablen). Mit jeder weiteren Variablen verdoppelt sich also die Zeilenzahl. Damit du keine Zeile vergisst oder doppelt schreibst, fängst du mit lauter Nullen an. Dann zählst du wie im Dualsystem aufwärts, bis nur noch Einsen dastehen.

Auch die Zahl der möglichen Funktionen ist begrenzt. Mit einer Eingangsvariablen gibt es nur 4 verschiedene Funktionen, mit zwei Eingangsvariablen schon 16. Allgemein gibt es 2 hoch (2 hoch n) Funktionen mit n Eingängen. Bei 4 Eingängen sind das 2 hoch 16 = 65.536 verschiedene Funktionen.

Ein Boolescher Term verknüpft Variablen mit drei Bausteinen. Sie heißen NICHT (Zeichen ¬), UND (Zeichen ∧) und ODER (Zeichen ∨). In Programmiersprachen heißen sie auch NOT, AND und OR.

So rechnest du: NICHT dreht den Wert um, aus 0 wird 1 und aus 1 wird 0. UND ergibt nur dann 1, wenn alle verknüpften Werte 1 sind. Ist ein Wert 0, ist das Ergebnis 0. ODER ist das nicht ausschließende ODER: Es ergibt 1, wenn mindestens eines von beiden wahr ist.

Ohne Klammern hat in der Schaltalgebra UND immer Vorrang vor ODER. Oft wird das UND-Zeichen weggelassen: ¬x1 x2 bedeutet ¬x1 ∧ x2. Um einen Term für alle Eingaben auszuwerten, gehst du jede Zeile der Wahrheitstafel durch. Setze die Werte ein, rechne erst NICHT und dann UND und zuletzt ODER.

Das XOR (EXCLUSIVE OR) gibt 1 aus, wenn die beiden Eingänge unterschiedlich sind. Als Term mit den Eingängen x1 und x2 schreibst du es so: (¬x1 ∧ x2) ∨ (x1 ∧ ¬x2).

Aus jeder Wahrheitstafel kannst du einen Term bauen. Dazu brauchst du ein paar Wörter. Eine Konjunktion ist eine UND-Verknüpfung, eine Disjunktion ist eine ODER-Verknüpfung.

KDNF (kanonische disjunktive Normalform): Für jede Zeile mit Ergebnis 1 bildest du einen Minterm. Das ist eine UND-Verknüpfung aller Variablen. Variablen mit Wert 1 bleiben, wie sie sind. Variablen mit Wert 0 werden negiert. Dann verbindest du alle Minterme mit ODER. Jede Variable kommt in jedem Minterm genau einmal vor. Jede Boolesche Funktion hat genau eine KDNF, bis auf die Reihenfolge der Minterme.

KKNF (kanonische konjunktive Normalform): Für jede Zeile mit Ergebnis 0 bildest du einen Maxterm. Das ist eine ODER-Verknüpfung aller Variablen mit der invertierten Belegung. Eine Variable mit Wert 0 bleibt also, eine mit Wert 1 wird negiert. Dann verbindest du alle Maxterme mit UND. Beide Normalformen sind in der Regel keine minimale Formel, also nicht die kürzeste mögliche.

Umformen: Die Gesetze der Booleschen Algebra erlauben, einen Term durch einen gleichwertigen Term zu ersetzen. Die De Morganschen Gesetze lauten ¬(a ∧ b) = ¬a ∨ ¬b und ¬(a ∨ b) = ¬a ∧ ¬b. Außerdem gilt ¬(¬a) = a. Wegen der De Morganschen Regel reichen grundsätzlich auch zwei der drei Grundfunktionen aus, zum Beispiel NICHT zusammen mit UND. Du kannst jede Umformung mit der Wahrheitstafel prüfen. Ausgedachter Test für das erste Gesetz mit a = 1 und b = 0: ¬(1 ∧ 0) = ¬0 = 1 und ¬1 ∨ ¬0 = 0 ∨ 1 = 1.