Das Ziel ist, eine Summe von Produkttermen zu finden, die die gleiche Ausgangsfunktion beschreibt und möglichst wenig Implikanten und Literale enthält, um die Kosten zu minimieren.
Für die Minimierung zweistufiger Logik gibt es exakte Verfahren und Heuristiken.
Für wenige Eingänge lässt sich eine exakte Lösung mit dem Karnaugh-Diagramm finden. Dies ist eine 2-dimensionale Anordnung einer Funktionstabelle. Jedes Feld enthält genau einen Implikanten (Minterm). Bei benachbarten Feldern ändert sich die dazugehörige Eingangskombination nur bei einer Eingangsvariablen. Dadurch lassen sich benachbarte Felder zu einfacheren Implikanten zusammenfassen. Die Erklärung liefert das Absorptionsgesetz:
Das exakte Verfahren nach Quine und McCluskey lässt sich leichter in einem Programm implementieren als die Karnaugh-Diagramm-Minimierung. Es garantiert zwar ein Minimum, hat aber eine exponentielle Komplexität (O(n) = (3^n)/n) und ist daher nur für wenige Eingänge praktikabel. Im Wesentlichen basiert es auf zwei Schritten:
- Berechnung aller Primimplikanten: Zwei Implikanten lassen sich zusammenfassen, wenn sie sich an nur einer Position unterscheiden (wie beim Karnaugh-Diagramm).
- Extraktion der minimalen disjunktiven Form der Funktion.