Karnaugh-Veitch Diagramme

Wie bereits erwähnt, kann man aus den Grundelementen UND, ODER und NICHT jeden beliebigen anderen logischen Ausdruck zusammenstellen. Wir haben des weiteren gesehen, wie man aus einer beliebigen Wahrheitstafel zu einer logischen Funktion kommt. Angesichts der doch relativ aufwendigen und vor allem fehleranfälligen Methode der Vereinfachung mit Hilfe der Boole'schen Algebra stellt sich jedoch die Frage, ob es nicht einfachere Methoden gibt, eine möglichst kompakte logische Funktion zu bestimmen. Eine dieser Methoden beruht auf einer graphischen Darstellung der Wahrheitstafel und heißt Karnaugh-Veitch-Diagramm (KV-Diagramm).

Im KV-Diagramm wird die Wahrheitstafel nur in etwas veränderter Form aufgetragen. Das Diagramm hat die Form eines Schachbrettes, wobei jedes Feld des Schachbrettes eine hexadezimale Nummer trägt, die der Bitkombination der Wahrheitstafel entspricht. Die Felder sind so angeordnet, dass sich jedes benachbarte Feld nur durch jeweils eine Variable unterscheidet. Je nachdem, wie viele Eingangsvariablen vorhanden sind, ist das KV-Diagramm unterschiedlich groß. Die Grenzen für 2 bis 6 Eingangsvariablen sind in folgender Abbildung mit stärkeren Linien markiert.

Die Verbindung zwischen KV-Diagramm und Wahrheitstafel ergibt sich wie folgt: Jede Eingangsvariable wird mit einem Buchstaben, beginnend mit a, von rechts nach links benannt. Jede Zeile der Wahrheitstafel entspricht nun jenem Feld des KV-Diagramms, dessen hexadezimale Nummer der Bitkombination der Eingangsvariablen entspricht.

Karnaugh-Veitch-Diagramm für maximal 6 Variable

Die Anwendung des KV-Diagramms zur Reduktion der logischen Gleichung geschieht nun so:

1. Für jede Zeile der Wahrheitstafel, die als Ausgangsgröße eine Eins enthält, wird im KV-Diagramm jenes Feld angekreuzt, dass die Nummer trägt, die sich aus den Eingangsvariablen ergibt. Zeilen der Wahrheitstafel, die als Ausgangsgröße eine Null enthalten, bleiben unberücksichtigt.
2. Es werden die angekreuzten Felder zu zusammenhängenden Blöcken zusammengefasst, wobei die Zahl der Felder eine Potenz von zwei sein muss (2, 4, 8, 16, 32, ...). Dabei muss man sich das KV-Diagramm an den Seiten zusammenhängend vorstellen, das heißt, ein Feld an einer Diagrammgrenze ist zu einem Feld an der gegenüberliegenden Grenze benachbart. Beim Zusammenfassen von Blöcken kann es vorkommen, dass zwei Blöcke sich gegenseitig überdecken. Generell sollte man möglichst große und möglichst wenige Blöcke finden, auch wenn sich diese zum Großteil überlagern.
3. Für jeden dieser Blöcke (dies gilt auch für 'Blöcke', die nur aus einem Feld bestehen) werden nun die logischen Ausdrücke wie folgt ermittelt: Jene Variablen, die für diesen Block sowohl Null als auch Eins sind, werden eliminiert. Die restlichen Variablen werden mit UND zu einem Ausdruck verknüpft, wobei Variablen, deren Wert in der Wahrheitstafel mit Null angegeben ist, invertiert werden müssen, Variablen, die mit Eins angegeben sind, bleiben unverändert.
4. Die logischen Ausdrücke der einzelnen Blöcke werden nun mit ODER zum Gesamtausdruck vereinigt. Dieser logische Ausdruck entspricht nun der Wahrheitstafel und besteht aus einer minimalen Anzahl von Termen.
5. Eventuell kann man durch Anwendung der Boole'schen Algebra für die konkrete Schaltungsrealisierung noch günstigere Ausdrücke erzeugen.

Ein Beispiel soll die eben geschilderte Vorgangsweise verdeutlichen: Es soll eine Schaltung konstruiert werden, deren Funktion der unten abgebilteten Wahrheitstafel entspricht. Es wird dazu im ersten Schritt für jede Zeile, die in der Ausgangsspalte der Wahrheitstafel eine Eins enthält, das entsprechenden Feld des KV-Diagramms angekreuzt (Felder 1, 6, 7, 9, E, und F). Dann werden möglichst große Blöcke gebildet. Für unser Beispiel ergeben sich zwei Blöcke, einer mit vier Feldern und einer mit zwei Feldern. Für diese Blöcke ergeben sich folgende logische Ausdrücke:

b c und a ~b ~c.

Diese werden im letzten Schritt zum Gesamtausdruck

b c v a ~b ~c

zusammengefasst. Man sieht, dass die Eingangsvariable d keinen Einfluss auf die Ausgangsvariable hat und in der Schaltung die Signalleitung d weggelassen werden kann (außer sie wird für andere Zwecke benötigt).

Beispiel für Karnaugh-Veitch-Diagramm