Skip to content

Implicants#

Definition: Implicant

An implicant of a Boolean function \(f(x_1, \dotsc, x_n)\) is any product term \(P\) such that if the value of \(P\) is \(1\), then the value of \(f\) is also \(1\):

\[ P = 1 \implies f = 1 \]

Example

Consider \(f(x, y, z) = \overline{x}\overline{y}\overline{z} + \overline{x}yz + xyz\).

The product terms \(\overline{x}\overline{y}\overline{z}\), \(\overline{x}yz\) and \(xyz\) are obviously implicants of \(f\). The product term \(yz\) is also an implicant of \(f\).

Theorem: Implicant Tests

A product term \(P\) is an implicant of a Boolean function \(f(x_1, \dotsc, x_n)\):

  • if and only if \(P \land F = P\);
  • if and only if \(P \land \overline{F} = 0\).
Proof

TODO

Definition: Prime Implicant

A prime implicant is an implicant such that removing any literal from it no longer results in an implicant.

Example

Consider \(f(x, y, z) = \overline{x}\overline{y}\overline{z} + \overline{x}\overline{y}z + x\overline{y}z\).

We see that \(\overline{x}\overline{y}\overline{z}\) is an implicant. If we remove \(\overline{z}\), we obtain \(\overline{x}\overline{y}\), which is also an implicant. Therefore, \(\overline{x}\overline{y}\overline{z}\) is not a prime implicant.

If we try to remove either \(\overline{x}\) or \(\overline{y}\) from \(\overline{x}\overline{y}\), we get something which is no longer an implicant. Therefore, \(\overline{x}\overline{y}\) is a prime implicant.

Definition: Covering

We say that an implicant \(P\) covers a minterm \(m\) if every literal in \(P\) is also present in \(m\).

Example

Consider \(f(x, y, z) = \overline{x} \overline{y}z + \overline{x}yz + xyz\). The implicant \(yz\) covers both \(\overline{x}yz\) and \(xyz\). The implicant \(\overline{x} \overline{y} z \overline{x}\) covers only \(\overline{x} \overline{y}z\).

Theorem: Covering Test

An implicant \(P\) covers a minterm \(m\) if and only if \(P \land m = m\).

Proof

TODO

Definition: Essential Prime Implicant

Suppose that \(f\) is given by a disjunctive normal form.

A prime implicant \(P\) of a disjunctive normal form is essential if there exists a minterm \(m\) in this DNF such that \(P\) is the only prime implicant which covers \(m\).

Example

Consider the following \(f\):

\[ f(x,y,z,w) = \overline{x}\overline{y}\overline{z}\overline{w} + \overline{x}\overline{y}z\overline{w} + \overline{x}y\overline{z}w + \overline{x}yzw + x\overline{y}\overline{z}w + x\overline{y}z\overline{w} + xy\overline{z}w + xyzw \]

The prime implicants are \(\overline{x}yw\), \(y\overline{z}w\), \(yzw\), \(xyw\) and \(\overline{y}\overline{w}\). Of these, \(\overline{y}\overline{w}\) is essential, since \(\overline{x}\overline{y}\overline{z}\overline{w}\), \(\overline{x}\overline{y}z\overline{w} + \overline{x}y\overline{z}w\), \(x\overline{y}\overline{y}\overline{z}\) and \(x\overline{y}z\overline{w}\) are not covered by any other prime implicants.

Algorithm: Implicants from Karnaugh Maps

We are given a Karnaugh map for a Boolean function \(f: \{0,1\}^n \to \{0,1\}\) and want to find the essential prime implicants of \(f\).

  1. Group the cells according to the following rules:
    - Each group must contain only \(1\)s.
    - The total number of cells in a group must be a power of \(2\).
    - The shape of a group must be rectangular. For the purposes of this, the top and bottom row are considered adjacent and so are the left-most and right-most column.
  2. Each group constructed in the above way corresponds to a single implicant of \(f\). This implicant is obtained as follows:
    - If a variable remains a constant \(1\) at all cells in the group, then include it in the implicant.
    - If a variable remains a constant \(0\) at all cells in the group, then include its negation in the implicant.
    - If a variable is a \(1\) at some cells in the group and a \(0\) at others, then ignore it.
  3. Do this until all possible groups have been examined to obtain all implicants of \(f\).
    - If we are specifically looking for prime implicants, then we can speed up the process by first looking at the largest possible groups.

Tip: Prime Implicants

If it is not possible to combine a group with an adjacent group with the same number of cells and still obtain a valid group, then this group corresponds to a prime implicant.

Tip: Essential Prime Implicants

If a cell is contained in only a single group and this group corresponds to a prime implicant, then this group corresponds to an essential prime implicant.

Example

Consider the function \(f(x,y,z,w)\) with the following Karnaugh Maps:

Implicants from Karnaugh Map Example

Here are some possible groups:

Karnaugh Map Example Groups

The blue group can be formed thanks to the rule adjacency rule. In this group, \(y\), \(z\) and \(w\) are always zero, so this group corresponds to the implicant \(\overline{y}\overline{z}\overline{w}\). However, this is not a prime implicant because we can merge the four corners into a single group.

The red group corresponds to the implicant \(xyw\) because \(x\), \(y\) and \(w\) are always \(1\) within the group. However, this is not a prime implicant because we can combine this group with a group obtained by the cell above and the cell below to obtain a new valid group.

The green group corresponds to the implicant \(z\overline{w}\) because \(z\) is always \(1\) within the group and \(\overline{w}\) is always \(0\) within the group. Furthermore, this is a prime implicant because the group cannot be merged into a new group with any other group of the same size. Moreover, this is an essential prime implicant because it is impossible to construct another group which corresponds to a prime implicant and also contains the cell at the last row and second column.

Note

These are not all of \(f\)'s implicants, since these are just three possible groups.