Methode zur Berechnung der Menge der Primimplikanten einer vollständig spezifizierten Booleschen Funktion, die auf dem folgenden Lemma beruht:

Es sei f : {0, 1}ⁿ → {0, 1} eine über den Booleschen Variablenx₁, …, x_ndefinierte Boolesche Funktion. Dann ergibt sich die Menge P(f) der Primimplikanten von f durch\begin{eqnarray}\begin{array}{lll}P(f) & = & {x}_{i}\otimes (P({f}_{{x}_{i}})\backslash P({f}_{{x}_{i}}\wedge {f}_{\overline{{x}_{i}}}))\\ & & \cup \overline{{x}_{i}}\otimes (P({f}_{\overline{{x}_{i}}})\backslash P({f}_{{x}_{i}}\wedge {f}_{\overline{{x}_{i}}}))\\ & & \cup P({f}_{{x}_{i}}\wedge {f}_{\overline{{x}_{i}}})\end{array}\end{eqnarray}aus der Menge \(P({f}_{{x}_{i}})\)der Primimplikanten des positiven Kofaktors \({f}_{{x}_{i}}\), der Menge \(P({f}_{\bar{{x}_{i}}})\)der Primimplikanten des negativen Kofaktors \({f}_{\bar{{x}_{i}}}\), und der Menge \(P({f}_{{x}_{i}}\wedge {f}_{\overline{{x}_{i}}})\)der Primimplikanten der Konjunktion dieser beiden Kofaktoren.

Hierbei beschreibt der Ausdruck l ⊗ M für ein Boolesches Literal l und eine Menge M von Booleschen Monomen die Menge {l ∧ m; m ∈ M}.

Die Methode wird im Rahmen der zweistufigen Logiksynthese eingesetzt. Die jeweiligen Primimplikantenmengen werden implizit (implizite Darstellung einer endlichen Menge) durch BDDs dargestellt, sodaß die Laufzeit der Berechnung der Menge der Primimplikanten einer Booleschen Funktion f nicht mehr direkt von der Anzahl der Implikanten von f, sondern nur noch von der Größe dieser impliziten Darstellungen abhängt.