Implicants and Minterms

In Boolean algebra, an implicant is an elementary product that, if evaluated as true (i.e., equals 1), ensures that the Boolean function also returns true.

An elementary product consists of literals that are multiplied together. For example, $x \cdot \overline{y}$ is one such product, typically written without the multiplication sign as $x\overline{y}$.

Essentially, an implicant is a term which, when true, guarantees that the Boolean function it belongs to will output true, though the reverse may not necessarily hold.

Implicants are categorized as follows:

Prime implicants
A prime implicant is an irreducible implicant that doesn't allow for further simplification without altering the output of the function. Such implicants cannot be completely replaced by a simpler equivalent. Notably, prime implicants may not include every variable of the function, which distinguishes them from minterms.
Essential implicants
These are a subset of prime implicants that uniquely determine one or more outputs of the truth table and are critical for achieving the minimal form of the function.
Minterms
Minterms are a special kind of implicant that include every variable of a Boolean function, each appearing either in its original or negated form. They represent every possible combination of variables that results in a true function output.

In the disjunctive canonical form, also known as the sum of products, a Boolean function can be expressed as the logical OR of all its minterms, representing the input combinations that yield a true output.

Example

Consider a Boolean function $ f $ with three variables: $ A $, $ B $, and $ C $. Let’s examine how to pinpoint implicants, prime implicants, and minterms using this function.

The truth table for $ f $ is as follows:

$$
\begin{array}{|c|c|c|c|}
\hline
A & B & C & f(A, B, C) \\
\hline
0 & 0 & 0 & 0 \\
0 & 0 & 1 & 1 \\
0 & 1 & 0 & 0 \\
0 & 1 & 1 & 1 \\
1 & 0 & 0 & 1 \\
1 & 0 & 1 & 1 \\
1 & 1 & 0 & 0 \\
1 & 1 & 1 & 1 \\
\hline
\end{array}
$$

This table clearly delineates all the viable combinations of $ A $, $ B $, and $ C $, alongside the function's output for each set.

Each row where $ f $ is 1 defines a minterm for the Boolean function.

Here, the minterms include:

$ \overline{A} \overline{B} C $ for the scenario where A = 0, B = 0, C = 1
$ \overline{A} B C $ where A = 0, B = 1, C = 1
$ A \overline{B} \overline{C} $ where A = 1, B = 0, C = 0
$ A \overline{B} C $ where A = 1, B = 0, C = 1
$ A B C $ where A = 1, B = 1, C = 1

The function $ f $ is thereby expressed as a sum of its minterms.

This configuration is known as Disjunctive Normal Form (DNF).

$$ f = \overline {A} \overline{B} C + \overline{A} B C + A \overline{B} \overline{C} + A \overline{B} C + A B C $$

To identify prime implicants, we seek terms that can no longer be reduced without changing the outcome.

We find that certain minterms can be merged to simplify the overall expression:

$ \overline{A} \overline{B} C $ and $ \overline{A} B C $ can be consolidated into $ \overline{A} C $ by eliminating $ B $
In the sum, $ B $ appears in both direct and complement forms, creating an identity. $ B + \overline{B} = 1 $, allowing for its removal $$ \overline{A} \color{red}{\overline{B}} C + \overline{A} \color{red}B C = \overline{A} C $$
$ A \overline{B} \overline{C} $, $ A \overline{B} C $, and $ A B C $ merge into $ A $ by excluding $ B $ and $ C $
Here, $ B $ and $ C $ appear in all their states, leading to two identities. $ \overline{B} + B + B = 1 $ and $ \overline{C} + C + C = 1 $, thus they can be omitted $$ A \color{red}{ \overline{B} } \color{blue}{ \overline{C} } + A \color{red}{ \overline{B}} \color{blue}C + A \color{red}B \color{blue}C = A $$

The prime implicants for this Boolean function are:

$ \overline{A} C $
$ A $

With these prime implicants, we can streamline the Boolean function effectively.

$$ f = \underbrace{ \overline{A} \overline{B} C + \overline{A} B C }_{ \overline{A} C } + \underbrace{ A \overline{B} \overline{C} + A \overline{B} C + A B C }_{ A } $$

The function $ f $, simplified using prime implicants, appears as:

$$ f = \overline{A} C + A $$

This illustrates how implicants, especially prime implicants, can be instrumental in streamlining a Boolean function starting from its minterms.