Wahrheitstabellen und KV-Diagramme

Eine Wahrheitstabelle listet für eine logische Funktion alle möglichen Eingangskombinationen auf — und gibt zu jeder den zugehörigen Ausgangszustand an. Sie ist die einfachste und vollständigste Art, eine digitale Schaltung zu beschreiben.

Aufbau:

• Links die Eingangsspalten, üblicherweise A, B, C, …
• Rechts die Ausgangsspalten, üblicherweise Y, Z, …
• Eine Zeile pro Kombination

Bei n Eingängen hat die Tabelle 2^n Zeilen. Zwei Eingänge ergeben 4 Zeilen, drei Eingänge 8, vier Eingänge 16. Die Zeilenzahl wächst exponentiell — ab fünf Eingängen wird die Tabelle unübersichtlich, ab sechs ist sie kaum noch zu überblicken.

Die Reihenfolge folgt der binären Zählung: die Eingangsspalten werden wie die Ziffern einer Dualzahl gelesen, beginnend mit 0 und aufsteigend bis zum Maximum. Bei drei Eingängen also 000, 001, 010, 011, 100, 101, 110, 111.

Ein Beispiel mit zwei Eingängen A und B und drei häufigen Grundfunktionen:

Mehrere Ausgangsspalten in derselben Tabelle sind problemlos möglich. Ein Volladdierer — ein digitales Rechenwerk, das zwei Bits und einen Übertrag addiert — hat etwa drei Eingänge (zwei Summanden-Bits plus Übertrag-Eingang) und zwei Ausgänge: Summe und Übertrag-Ausgang.

Jede Wahrheitstabelle beschreibt genau eine logische Funktion vollständig. Zwei Schaltungen mit identischer Wahrheitstabelle sind logisch gleichwertig — egal wie sie intern aufgebaut sind.

Eine Wahrheitstabelle lässt sich direkt in eine boolesche Funktion übersetzen — und damit in eine Schaltung aus Gattern. Es gibt zwei systematische Verfahren, die immer funktionieren: die disjunktive Normalform (DNF) und die konjunktive Normalform (KNF).

Disjunktive Normalform. Man sieht sich alle Zeilen an, in denen der Ausgang Y = 1 ist. Jede solche Zeile liefert einen Minterm: ein UND-Produkt aller Eingangsvariablen, wobei jede Variable in negierter oder nicht-negierter Form vorkommt — abhängig davon, ob sie in dieser Zeile 0 oder 1 ist. Eine 1 → Variable normal, eine 0 → Variable negiert. Alle Minterme werden dann mit ODER verknüpft.

Schreibweise:

• UND: A · B oder einfach AB
• ODER: A + B
• NOT: /A (Schrägstrich vor der Variable)

Beispiel mit drei Eingängen:

Einsen liegen in den Zeilen mit ABC = 001, 011, 110, 111. Daraus ergeben sich die Minterme:

• Zeile ABC=001 → /A · /B · C
• Zeile ABC=011 → /A · B · C
• Zeile ABC=110 → A · B · /C
• Zeile ABC=111 → A · B · C

Die DNF lautet:

Y = /A·/B·C + /A·B·C + A·B·/C + A·B·C

Konjunktive Normalform. Man geht spiegelbildlich vor: alle Zeilen mit Y = 0 betrachten. Jede liefert einen Maxterm — eine ODER-Summe aller Variablen, diesmal genau umgekehrt: 0 → Variable normal, 1 → Variable negiert. Alle Maxterme werden mit UND verknüpft.

Im obigen Beispiel sind die Zeilen mit Y = 0 die Zeilen 000, 010, 100, 101. Daraus ergeben sich die Maxterme:

• Zeile ABC=000 → (A + B + C)
• Zeile ABC=010 → (A + /B + C)
• Zeile ABC=100 → (/A + B + C)
• Zeile ABC=101 → (/A + B + /C)

Die KNF lautet:

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

Welche Form wählen? DNF und KNF beschreiben dieselbe Funktion und liefern dasselbe Ergebnis. Welche kompakter ist, hängt vom Anteil der Einsen ab:

• Wenige Einsen → DNF kürzer
• Wenige Nullen → KNF kürzer
• Etwa gleichviele → beide ähnlich lang

In der Praxis arbeitet man weit überwiegend mit der DNF, weil sie sich direkter in Gatter-Logik übersetzen lässt (Produkte unten, Summe oben — entsprechend AND-Gatter mit nachgeschaltetem OR-Gatter).

Wichtig: DNF und KNF sind systematische Verfahren, aber meist nicht die kürzeste mögliche Funktion. Genau dort setzt das KV-Diagramm an.

Eine Wahrheitstabelle enthält alle Informationen, aber sie verrät auf den ersten Blick nichts darüber, welche Minterme sich vereinfachen lassen. Das KV-Diagramm (Karnaugh-Veitch-Diagramm) ordnet dieselben Daten räumlich neu — und macht Vereinfachungspotenzial direkt sichtbar.

Die Idee: gleiche Information wie in der Wahrheitstabelle, aber so angeordnet, dass benachbarte Felder sich genau in einer Variable unterscheiden. Dadurch erkennt man auf einen Blick, welche Variablen für die Funktion „egal“ sind und sich kürzen lassen.

Größen je nach Variablenzahl:

Bei 5 Variablen werden zwei 4×4-Diagramme übereinander gelegt — möglich, aber unhandlich. Bei mehr Variablen verwendet man andere Verfahren.

Gray-Code-Anordnung. Die Beschriftung der Spalten und Zeilen folgt nicht der normalen Dualzählung, sondern dem Gray-Code:

Reihenfolge: 00, 01, 11, 10

Statt der gewohnten Folge 00, 01, 10, 11. Der Unterschied: zwischen jedem Paar benachbarter Werte ändert sich genau ein Bit. Bei 00 → 01 ändert sich das rechte Bit. Bei 01 → 11 ändert sich das left Bit. Bei 11 → 10 ändert sich wieder das rechte. Diese Eigenschaft ist der eigentliche Trick des KV-Diagramms.

Layout eines 4-Variablen-KV-Diagramms:

Die kleinen Zahlen in den Feldecken sind der Zeilenindex der Wahrheitstabelle — etwa Index 7 für die Zeile ABCD = 0111. Sie helfen beim Übertragen aus der Tabelle ins Diagramm.

Befüllen. Für jede Zeile der Wahrheitstabelle wird der zugehörige Y-Wert in das passende Feld eingetragen. Feld in Zeile AB=01, Spalte CD=11 entspricht der Wahrheitstabellen-Zeile ABCD = 0111 (Index 7).

Randwicklung. Das KV-Diagramm muss man sich rollenförmig vorstellen — wie einen aufgeschnittenen Donut. Die linke und die rechte Spalte sind logische Nachbarn, ebenso die oberste und die unterste Zeile. Zwischen ihnen ändert sich auch nur eine Variable: von Spalte CD=00 links zu Spalte CD=10 rechts kippt nur das linke Bit von 0 auf 1. Das Gleiche gilt für die Zeilen AB=00 oben und AB=10 unten. Diese Randwicklung ist ein häufig übersehenes Merkmal.

Im befüllten KV-Diagramm fasst man die Einsen zu Blöcken zusammen. Jeder Block entspricht einem vereinfachten Term in der minimierten Funktion — und je größer der Block, desto kürzer der Term.

Regeln für Blöcke:

• Die Blockgröße ist eine Potenz von 2: 1, 2, 4, 8 oder 16 Felder
• Der Block ist rechteckig — keine L-, T- oder Treppenformen
• Blöcke werden so groß wie möglich gewählt
• Ränder dürfen überlaufen (Randwicklung nutzen)
• Blöcke dürfen sich überlappen
• Jede Eins muss in mindestens einem Block enthalten sein
• So wenige Blöcke wie möglich verwenden

Was bedeutet ein Block für den Term? Innerhalb eines Blocks bleiben einige Variablen konstant, andere wechseln zwischen 0 und 1. Die Regel lautet:

• Variable bleibt konstant → kommt in den Term
• Variable wechselt → fällt weg
• Konstanter Wert 1 → Variable normal
• Konstanter Wert 0 → Variable negiert

Daraus folgt direkt:

• 1er-Block: keine Variable fällt weg → alle 4 Variablen im Term (Minterm)
• 2er-Block: 1 Variable fällt weg → 3 Variablen im Term
• 4er-Block: 2 Variablen fallen weg → 2 Variablen im Term
• 8er-Block: 3 Variablen fallen weg → 1 Variable im Term
• 16er-Block: alle Variablen fallen weg → konstant 1

Beispiel mit der Funktion Y = A · B + C · D:

Im Beispiel:

• Roter Block (4 Einsen in der Zeile AB=11): A und B bleiben konstant 1, C und D wechseln durch alle Werte. Der Term lautet A · B.
• Blauer Block (4 Einsen in der Spalte CD=11): C und D bleiben konstant 1, A und B wechseln durch alle Werte. Der Term lautet C · D.

Die minimierte Funktion ist die ODER-Verknüpfung der Blockterme:

Y = A·B + C·D

Zum Vergleich: Die DNF derselben Funktion hätte 7 Minterme mit jeweils 4 Variablen. Die minimierte Form hat 2 Terme mit jeweils 2 Variablen — deutlich kompakter.

Bis hierher liegt das Werkzeug vollständig auf dem Tisch. Der typische Arbeitsablauf in der Praxis besteht aus sechs Schritten:

1. Anforderung formulieren — wann genau soll der Ausgang 1 werden?
2. Wahrheitstabelle aufstellen
3. KV-Diagramm aus der Tabelle befüllen
4. Blöcke einzeichnen, möglichst groß, möglichst wenige
5. Minimierten Ausdruck ablesen
6. Als Schaltung oder Programmcode umsetzen

Don’t-Care-Belegungen. In vielen praktischen Fällen gibt es Eingangskombinationen, die nie auftreten oder deren Ausgangszustand egal ist. Solche Felder bekommen im KV-Diagramm ein X (für „don’t care“, auch „d“ oder „—“ geschrieben).

Bei der Minimierung darf jedes X frei als 0 oder 1 interpretiert werden — abhängig davon, ob es die Blockbildung größer macht. Hilft das X einem Block, größer zu werden, wird es als 1 gewertet und in den Block aufgenommen. Bringt es nichts, lässt man es weg (wertet es als 0).

Typisches Beispiel: Ein Decoder für BCD-Ziffern verarbeitet vier Eingangsbits und gibt Steuerinformationen für die Ziffern 0 bis 9 aus. Die Bitkombinationen 1010 bis 1111 (entspricht 10 bis 15) treten bei korrekter BCD-Codierung nie auf. Diese sechs Felder im KV-Diagramm sind don’t care und können zur Vergrößerung von Blöcken benutzt werden.

Grenzen der KV-Methode. Das Verfahren funktioniert gut bis 4 Variablen. Mit 5 Variablen wird mit zwei übereinandergelegten 4×4-Diagrammen gearbeitet — das geht noch, ist aber unübersichtlich. Ab 6 Variablen wird das KV-Diagramm so umfangreich, dass es kaum noch hilft. Für solche Fälle gibt es das Quine-McCluskey-Verfahren (tabellarisch, systematisch, gut programmierbar) oder Software-Tools, die die Minimierung automatisch durchführen.