Schaltalgebra: von der Wahrheitstabelle zur Schaltung

Stell dir vor, du sollst eine Schaltung bauen, die bei drei Sensoren genau dann Alarm auslöst, wenn mindestens zwei davon anschlagen.

Man könnte anfangen zu probieren. Man muss aber nicht: Es gibt ein Verfahren, das aus der Wahrheitstabelle einer beliebigen Aufgabe eine funktionierende Schaltung erzeugt, ohne jeden Einfall.

Das ist das eigentliche Ergebnis dieses Kapitels. Der zweite Teil beantwortet die Anschlussfrage, denn die so entstandene Schaltung ist zwar richtig, aber meist unnötig groß, und Gatter kosten Platz, Strom und Zeit.

Vorausgesetzt werden AND, OR, NOT, XOR, NAND, NOR mit ihren Wahrheitstabellen und Schaltzeichen aus Logische Grundbausteine.

Neu ist die umgekehrte Richtung: Bisher war eine Schaltung gegeben und die Tabelle gesucht. Jetzt ist die Tabelle gegeben und die Schaltung gesucht.

In der Schaltalgebra schreibt man kurz:

Das OR ist dabei immer das einschließende Oder: $a \lor b$ ist auch dann wahr, wenn beide wahr sind. Das ausschließende Oder ist XOR und muss eigens hingeschrieben werden.

Hier ist das Verfahren. Gegeben sei diese Tabelle:

Schritt 1: Nur die Zeilen mit $y = 1$ betrachten. Alle anderen sind uninteressant.

Schritt 2: Für jede solche Zeile einen UND-Term bilden, der genau für diese Zeile wahr ist. Eine Variable mit Wert 1 kommt unverändert vor, eine mit Wert 0 negiert.

• Zeile 2 ($a=0$, $b=1$): $\bar{a} \land b$
• Zeile 3 ($a=1$, $b=0$): $a \land \bar{b}$

Schritt 3: Alle Terme mit ODER verbinden:

Fertig. Das ist die disjunktive Normalform, kurz DNF.

🔴 Warum das immer funktioniert, lässt sich in zwei Sätzen begründen. Jeder UND-Term ist genau für seine eine Zeile wahr und für jede andere falsch, denn in jeder anderen Zeile hat mindestens eine Variable den anderen Wert und macht den Term falsch. Die ODER-Verknüpfung ist damit genau dann wahr, wenn eine der ausgewählten Zeilen vorliegt, und das sind genau die Zeilen mit $y = 1$.

Beachte, was das bedeutet: Es gibt keine Wahrheitstabelle, für die man keine Schaltung bauen kann. Das Verfahren braucht keinen Einfall und liefert immer ein Ergebnis.

Übrigens: Der Term oben ist die Definition von XOR. Das erklärt, warum XOR kein eigenständiges Grundgatter sein muss, sondern sich aus AND, OR und NOT zusammensetzen lässt.

Ein Sonderfall bleibt: Steht in der Tabelle überall $y = 0$, gibt es keinen einzigen Term. Dann ist die Funktion konstant null, und man braucht gar kein Gatter.

Die Übersetzung ist unmittelbar:

• Jede negierte Variable → ein NOT-Gatter.
• Jeder UND-Term → ein AND-Gatter mit so vielen Eingängen wie der Term Variablen hat.
• Die Verbindung der Terme → ein OR-Gatter mit so vielen Eingängen wie es Terme gibt.

a ──┬──────────────┐
    │              │
    └─[NOT]─┐   ┌──┴──┐
            ├───┤ AND ├──┐
b ──┬───────┘   └─────┘  │   ┌────┐
    │                    ├───┤ OR ├── y
    └─[NOT]─┐   ┌─────┐  │   └────┘
            ├───┤ AND ├──┘
a ──────────┘   └─────┘

Die Schaltung hat immer drei Ebenen: erst die Negationen, dann die UND-Gatter, dann das eine ODER-Gatter. Genau deshalb heißt sie auch „Zweistufenschaltung", wenn man die Negationen nicht mitzählt.

Die DNF ist richtig, aber selten sparsam. Ein Beispiel mit drei Variablen, „mindestens zwei von drei":

DNF mit vier Termen:

Das sind vier UND-Gatter mit je drei Eingängen, drei NOT-Gatter und ein ODER-Gatter mit vier Eingängen. Vereinfacht ergibt sich (die Rechnung steht im Beispielteil):

Jetzt sind es drei UND-Gatter mit je zwei Eingängen, kein NOT-Gatter und ein ODER-Gatter mit drei Eingängen. Der Term ist außerdem sofort lesbar: „irgendwelche zwei stimmen überein".

Jedes gesparte Gatter bedeutet weniger Fläche auf dem Chip, weniger Stromverbrauch und eine kürzere Signallaufzeit. Bei Millionen von Gattern in einem Prozessor summiert sich das erheblich.

Vieles davon kennst du aus der Mathematik. Zwei Dinge sind aber anders, und sie werden am häufigsten falsch gemacht:

$a \lor a = a$, nicht $2a$. Es gibt keine Vielfachen, weil es nur die Werte 0 und 1 gibt.

De Morgan. Beim Hineinziehen einer Negation wechselt der Operator. Das ist keine Formalität, sondern der Kern der Regel. Anschaulich: „Nicht (beide)" heißt „mindestens einer nicht", und „nicht (mindestens einer)" heißt „keiner", also „beide nicht".

Der häufigste Fehler ist $\overline{a \land b} = \bar{a} \land \bar{b}$. Prüfe ihn an $a = 1$, $b = 0$: links steht $\overline{0} = 1$, rechts $0 \land 1 = 0$. Die Behauptung ist also widerlegt, und eine einzige Zeile der Wahrheitstabelle genügte dafür.

Dieser Abschnitt gehört zum erhöhten Anforderungsniveau.

Erstaunlich, aber leicht zu zeigen: Jede Schaltfunktion lässt sich allein mit NAND-Gattern bauen.

Der Nachweis ist kurz. Es genügt, NOT, AND und OR aus NAND zu bauen, denn mit diesen dreien ergibt sich über die DNF jede beliebige Funktion.

NOT: Beide Eingänge des NAND zusammenlegen.

AND: NAND, danach die Negation, also ein zweites NAND als NOT.

OR: Beide Eingänge zuerst negieren, dann NAND. Der Nachweis ist De Morgan:

Damit sind alle drei Grundverknüpfungen aus NAND aufgebaut, und da jede Schaltfunktion über die DNF aus diesen dreien entsteht, ist die Behauptung bewiesen. Man nennt NAND deshalb funktional vollständig; für NOR gilt dasselbe.

Der praktische Nutzen ist groß: Eine Fertigung, die nur einen Gattertyp beherrschen muss, ist einfacher, billiger und gleichmäßiger in ihren Eigenschaften. In der Praxis bezahlt man das mit mehr Gattern pro Funktion, und deshalb baut man nicht wirklich alles aus NAND. Das Ergebnis zeigt aber, wie wenig im Kern nötig ist.