Essential prime implicant

An essential prime implicant of a Boolean function $f$ is a Prime implicant that covers at least one minterm not covered by any other prime implicant. Because that minterm has only one prime over it, every minimum-cost SOP for $f$ must contain this essential — there is no alternative.

Spotting essentials is the first concrete step in K-map and Quine-McCluskey minimisation: include all of them automatically, then worry about the rest.

How to spot them

Walk every $1$ on the Karnaugh Map. If exactly one prime implicant covers that $1$ (i.e., that $1$ is inside only one maximal rectangle), then that prime is essential, and the $1$ is its distinguishing minterm.

Some primes have no distinguishing minterm — every $1$ they cover is also covered by some other prime. Those primes are non-essential. They might still appear in the minimum cover, but their inclusion is a choice rather than forced.

Worked example

Continuing the four-variable function from Prime implicant with primes:

• $\overline{x_2}\overline{x_3}$ covering $\{0,1,8,9\}$.
• $\overline{x_2}\overline{x_4}$ covering $\{0,2,8,10\}$.
• $x_3\overline{x_4}$ covering $\{2,6,10,14\}$.
• $\overline{x_1}{x}_2{x}_4$ covering $\{5,7\}$.

Per-minterm coverage (which primes cover each $1$):

Minterm	Covered by primes
0	$\overline{x_2}\overline{x_3}$, $\overline{x_2}\overline{x_4}$
1	$\overline{x_2}\overline{x_3}$
2	$\overline{x_2}\overline{x_4}$, $x_3\overline{x_4}$
5	$\overline{x_1}{x}_2{x}_4$
6	$x_3\overline{x_4}$
7	$\overline{x_1}{x}_2{x}_4$
8	$\overline{x_2}\overline{x_3}$, $\overline{x_2}\overline{x_4}$
9	$\overline{x_2}\overline{x_3}$
10	$\overline{x_2}\overline{x_4}$, $x_3\overline{x_4}$
14	$x_3\overline{x_4}$

Distinguishing minterms (covered by only one prime):

• Minterm 1 → only $\overline{x_2}\overline{x_3}$. So $\overline{x_2}\overline{x_3}$ is essential.
• Minterm 5 → only $\overline{x_1}{x}_2{x}_4$. Essential.
• Minterm 6 → only $x_3\overline{x_4}$. Essential.

The fourth prime $\overline{x_2}\overline{x_4}$ has no distinguishing minterm — every $1$ it covers (0, 2, 8, 10) is also covered by an essential. So it is not essential.

After including the three essentials $\overline{x_2}\overline{x_3}+x_3\overline{x_4}+\overline{x_1}{x}_2{x}_4$, every minterm of $f$ is already covered. The non-essential $\overline{x_2}\overline{x_4}$ is redundant; drop it.

Result: $f=\overline{x_2}\overline{x_3}+x_3\overline{x_4}+\overline{x_1}{x}_2{x}_4$ — a 7-literal SOP.

Minimisation procedure

The full procedure once primes and essentials are known:

1. Identify all prime implicants. (K-map by inspection; Quine-McCluskey for larger functions.)
2. Identify all essential primes (each one covers at least one distinguishing minterm). Add all to the cover automatically.
3. Check what’s left uncovered. If essentials together cover every $1$, you’re done.
4. Cover the remainder with non-essential primes. Choose the cheapest combination — usually pick the prime covering the most uncovered $1$s, repeat.

Step 4 can be hard in pathological cases — it’s the set cover problem, NP-hard in general. For real circuits the input is small enough that greedy heuristics (used by Espresso) produce near-optimum results quickly.

Why “essential” is the term

The word captures the algebraic fact: omitting an essential prime would leave its distinguishing minterm uncovered, making the SOP wrong. There is no substitution. By contrast, removing a non-essential prime might or might not break the cover — depending on whether the minterms it covers are also covered by what remains.

In context

EPIs are step 2 of K-map / Quine-McCluskey minimisation — see Karnaugh Map for the diagrammatic workflow, Implicant for the basic concept, Prime implicant for the maximality refinement that EPIs further refine.