Implicant

An implicant of a Boolean function $f$ is a product of literals that, whenever it equals $1$, forces $f=1$. Equivalently: an implicant is a product term whose 1-set is a subset of $f$‘s 1-set.

Geometrically on a Karnaugh Map, an implicant is a rectangular group of $1$s — every cell in the rectangle is a $1$ of the function. Algebraically, the term implies $f$: the term being true is a sufficient condition for $f$ being true.

Examples

For $f(x_1,x_2,x_3)=x_1\overline{x_3}+\overline{x_2}{x}_3$:

• $x_1\overline{x_2}\overline{x_3}$ is an implicant — wherever it’s $1$ (only minterm 4), $f$ is $1$.
• $x_1\overline{x_3}$ is an implicant — wherever it’s $1$ (minterms 4 and 6), $f$ is $1$.
• $\overline{x_2}{x}_3$ is an implicant — wherever it’s $1$ (minterms 1 and 5), $f$ is $1$.
• $x_2{x}_3$ is not an implicant — at minterm 3 ($x_1=0,x_2=1,x_3=1$) the term is $1$ but $f$ is $0$.

A single minterm of $f$ is always an implicant — the minimal one. Larger implicants combine multiple minterms by dropping variables that don’t affect the value (the K-map adjacency principle: $\overline{x}y+xy=y$).

Why implicants matter

Logic minimisation is the search for the cheapest sum-of-products that equals $f$. Every term in any SOP for $f$ must be an implicant — otherwise the term would be $1$ at some point where $f$ is $0$, making the SOP wrong.

So the search space for SOP minimisation is “the set of implicants of $f$.” Bigger implicants (covering more minterms) cost fewer literals; smaller ones cost more. The minimisation problem becomes: pick a small set of implicants whose union of $1$-cells covers every $1$ of $f$.

The two refinements that make this tractable:

• A Prime implicant — an implicant that can’t be combined with any other to form a larger implicant. Only primes need to be considered for the minimum cover.
• An Essential prime implicant — a prime implicant that uniquely covers some $1$. Essentials are mandatory in any minimum cover.

The full cover-search procedure, after reducing to primes and essentials, is what algorithms like Quine-McCluskey and Espresso solve.

Cube terminology

In some references, an implicant is called a cube — because in $n$-variable space the implicant’s $1$-cells form a $k$-dimensional sub-cube (a vertex if $k=0$, an edge if $k=1$, a face if $k=2$, and so on). The size of the implicant is $2^k$ minterms; it has $n-k$ literals.

This is the geometric way to see “doubling the group size drops a literal”: each step up in dimension halves the literal count.

In context

Implicants are the search-space objects of K-map and tabular minimisation. See Karnaugh Map for the visual side, Prime implicant for the maximality refinement, Essential prime implicant for the uniqueness refinement, and Sum-of-products for what implicants combine into.