Prime implicant

A prime implicant of a Boolean function $f$ is an implicant of $f$ that cannot be enlarged. Removing any literal from it would either make it not an implicant any more (it would cover a $0$ of $f$ ) or — equivalently on a Karnaugh Map — it would no longer be a rectangle of $1$ s.

A prime implicant is the maximal rectangle of $1$ s on the K-map. There’s no bigger group it fits inside.

Why only primes matter

Any minimum-cost SOP for $f$ uses only prime implicants. The argument: if a non-prime implicant $T$ is in the cover, $T$ can be enlarged to some prime $T^{'}$ by dropping a literal. $T^{'}$ has fewer literals than $T$ and covers a superset of $T$ ‘s 1-cells, so swapping $T$ for $T^{'}$ never increases the cost and may shrink it. Repeat until every term is prime.

So the search for a minimum SOP can be restricted to prime implicants without losing optimality. This is the foundational reduction that makes K-map minimisation manageable.

Identifying primes on a K-map

Walk every $1$ on the map. For each, find the largest rectangle of $1$ s (in powers of two, possibly wrapping around the toroidal edges) that contains it. That rectangle is a prime implicant. Distinct $1$ s may produce the same prime — so the set of primes is found by unioning all maximal rectangles.

Primes can overlap. A single $1$ can be inside more than one prime — that’s how you get non-essential primes.

Worked example

Consider the function with 1-cells at minterms ${0, 1, 2, 5, 6, 7, 8, 9, 10, 14}$ on a 4-variable K-map (variables $x_{1} x_{2} x_{3} x_{4}$ ).

Maximal rectangles (each is a prime implicant):

${0, 1, 8, 9}$ — a $2 \times 2$ block. Variables that stay constant: $x_{2} = 0, x_{3} = 0$ . Prime: $\overline{x_{2}} \overline{x_{3}}$ .
${0, 2, 8, 10}$ — a $2 \times 2$ block. Variables constant: $x_{2} = 0, x_{4} = 0$ . Prime: $\overline{x_{2}} \overline{x_{4}}$ .
${2, 6, 10, 14}$ — a column. Variables constant: $x_{3} = 1, x_{4} = 0$ . Prime: $x_{3} \overline{x_{4}}$ .
${5, 7}$ — an adjacent pair. Variables constant: $x_{1} = 0, x_{2} = 1, x_{4} = 1$ . Prime: $\overline{x_{1}} x_{2} x_{4}$ .

Each is maximal — none can be doubled while staying inside the $1$ -set. So these four are the prime implicants.

A non-prime implicant like ${0, 1}$ — variables constant $x_{1} = 0, x_{2} = 0, x_{3} = 0$ , term $\overline{x_{1}} \overline{x_{2}} \overline{x_{3}}$ — is not prime because it sits inside the larger ${0, 1, 8, 9}$ , which drops $x_{1}$ to give $\overline{x_{2}} \overline{x_{3}}$ . The bigger one wins.

Quine-McCluskey

For more than 4 variables, K-maps stop being practical. The Quine-McCluskey algorithm finds prime implicants tabularly: list all minterms in binary, group by number of $1$ s, repeatedly merge pairs that differ in exactly one bit (replacing the differing bit with $-$ ), and keep going until no more merges are possible. Anything that can’t be merged further is prime.

Quine-McCluskey is exact but exponential; for many variables, heuristic minimisers like Espresso are used in practice.

What primes don’t tell you

Knowing the prime implicants doesn’t immediately give the minimum cover — you still have to choose which primes to include. That’s the role of essential prime implicants (mandatory) and the cover-selection step that picks among the rest.

Two examples of why the choice matters:

A function might have many primes but only a few essentials, with the remainder optional. The minimum cover uses essentials plus the cheapest selection of non-essentials that covers anything left.
Two different sets of primes can both produce minimum covers — minimisation is not always uniquely solvable.

In context

Prime implicants live in the K-map workflow described at Karnaugh Map and in the tabular workflow of Quine-McCluskey. See Implicant for the broader concept and Essential prime implicant for the next refinement.

Idriss Rami — Notes

Explorer