Minimierung mit Hilfe von KV-Diagrammen

Für KV-Diagramme mit höchstens vier Variablen ermittelt der folgende Algorithmus die minimale Funktion.

Algorithmus zur Bestimmung minimaler Funktionen

1. Erzeuge das KV-Diagramm.
2. Trage die Funktion in das Diagramm ein.
3. Zeichne Rechtecke mit der Kantenlänge 1, 2 oder 4 in das Diagramm ein, die möglichst viele Felder umschließen und ausschließlich Felder mit Einsen enthalten. Dabei dürfen sich die Rechtecke über den Rand hinaus auf die gegenüberliegende Seite erstrecken, das heißt, der rechte und linke Rand sowie der obere und untere Rand sind miteinander verbunden.
4. Suche ein nichtschraffiertes Feld, das eine 1 enthält und von möglichst wenigen Rechtecken überdeckt wird.

   Schraffiere das größte dieser Rechtecke. (Einschließlich der Teile, die eventuell auf der gegenüberliegenden Seite liegen und noch zu dem Rechteck gehören!)

   Wiederhole den letzten Schritt, bis alle Felder, die eine 1 enthalten, schraffiert sind.

5. Für jedes schraffierte Rechteck wird ein Konjunktionsterm gebildet. In diesem Term werden die Variablen konjunktiv zusammengefaßt, die eindeutig eine der beiden Kanten bezeichnen. Hat eine der Kanten die maximale Länge, dann besteht der Term nur aus der Bezeichnug für die andere Kante. (Haben beide Kanten die maximale Länge, dann ist die Funktion konstant 1, also eine Tautologie.)
6. Alle Konjunktionsterme, die sich aus dem vorangegangenen Schritt ergeben haben, werden disjunktiv zusammengefaßt. Das Ergebnis ist die Disjunktive Normalform der gesuchten minimalen Funktion.

• Beispiel zur Minimierung