Bestimmung der Primimplikanten

1. Die Funktion wird in die Disjunktive Normalform umgewandelt.
2. Alle Konjunktionsterme werden in die Spalte einer Tabelle eingetragen.
3. Für alle Konjunktionsterme wird überprüft, ob es andere Konjunktionsterme in der Spalte gibt, die sich nur in einer Variablen unterscheiden. Dabei muß ein Konjunktionsterm diese Variable einfach, der andere negiert enthalten.

   (Im obigen Beispiel sind abc und ein solches Paar.)

   Solche Konjunktionsterme werden im folgenden als ähnlich bezeichnet.

   Wird für einen Konjunktionsterm ein ähnlicher gefunden, dann werden beide markiert. In der nebenstehenden Spalte wird ein Konjunktionsterm eingetragen, der entsteht, wenn man die Variable wegläßt, die in den beiden gerade betrachteten Termen verschieden ist.

   (Für das Beispiel ergibt sich:

   

   abc und werden als ähnlich erkannt und mit * markiert. Die beiden Terme werden zusammengefaßt:

   

   Der Term ac wird in die nebenstehende Spalte eingetragen.)

   Wurden für einen Konjunktionsterm alle übrigen hinsichtlich ihrer Ähnlichkeit untersucht, dann wird der nächste Konjunktionsterm betrachtet.

   Dies wird solange wiederholt, bis alle Konjunktionsterme der Spalte betrachtet wurden.

   Beim Vergleich der Konjunktionsterme werden immer alle, d.h. auch die bereits durch * markierten, betrachtet. Eine Mehrfachmarkierung von Konjunktionstermen ist nicht notwendig.

4. Falls keine neuen Terme in die neue Spalte eingetragen wurden, wird der Algorithmus beendet.

   Sonst: Streiche in der letzten Spalte alle Mehrfachnennungen eines Terms, so daß jeder Term genau einmal in dieser Spalte enthalten ist.

   Wiederhole ab Schritt 3 den Algorithmus mit dieser neuen Spalte.