Implicates#
Definition: Implicate
An implicate of a Boolean function \(f(x_1, \dotsc, x_n)\) is any clause \(C\) such that if the value of \(f\) is \(1\), then the value of \(C\) is also \(1\):
Definition: Prime Implicate
A prime implicate is an implicate such that removing any literal from it no longer results in an implicate.
Example
Consider \(f(x, y, z) = (x + y + \overline{z})(\overline{x} + y + \overline{z})(\overline{x} + \overline{y} + \overline{z})\). Here, \(x + y + \overline{z}\) is an implicate of \(f\), but it is not a prime implicate, since removing \(x\) results in \(y + \overline{z}\), which is still an implicate.
However, \(y + \overline{z}\) is a prime implicate because removing either \(y\) or \(\overline{z}\) results in something which is no longer an implicate.
Definition: Covering
We say that an implicate \(C\) covers a maxterm \(M\) if the literals in \(C\) are a subset of the literals in \(M\).
Example
Consider \(f(x, y, z) = (x + \overline{y} + z)(x + \overline{y} + \overline{z})(\overline{x} + y + z)(\overline{x} + \overline{y} + z)\).
The implicate \(x + \overline{y}\) covers both \((x + \overline{y} + z)\) and \((x + \overline{y} + \overline{z})\).
The implicate \(\overline{x} + y + z + \overline{x}\) covers only \(\overline{x} + y + z\).
Definition: Essential Prime Implicate
A prime implicate \(C\) of a conjunctive normal form is essential if there exists a maxterm \(M\) in the CNF such that \(C\) is the only prime implicate which covers \(M\).
Example
Consider \(f(x, y, z) = (x + \overline{y} + z)(x + \overline{y} + \overline{z})(\overline{x} + y + z)(\overline{x} + \overline{y} + z)\).
Its prime implicates are \((x + \overline{y})\), \((\overline{y} + z)\) and \((\overline{x} + z)\). Of these, \((x + \overline{y})\) and \((\overline{x} + z)\) are essential because \(x + \overline{y} + \overline{z}\) is only covered by \((x + \overline{y})\) and \(\overline{x} + y + z\) is only covered by \((\overline{x} + z)\).
Algorithm: Implicates 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 implicates of \(f\).
- Group the cells according to the following rules:
- Each group must contain only \(0\)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. - Each group constructed in the above way corresponds to a single implicate of \(f\). This implicate is obtained as follows:
- If a variable remains a constant \(0\) at all cells in the group, then include it in the implicate.
- If a variable remains a constant \(1\) at all cells in the group, then include its negation in the implicate.
- If a variable is a \(1\) at some cells in the group and a \(0\) at others, then ignore it. - Do this until all possible groups have been examined to obtain all implicates of \(f\).
- If we are specifically looking for prime implicates, then we can speed up the process by first looking at the largest possible groups.
Tip: Prime implicates
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 implicate.
Tip: Essential Prime implicates
If a cell is contained in only a single group and this group corresponds to a prime implicate, then this group corresponds to an essential prime implicate.
Example
Consider the function \(f(x,y,z,w)\) with the following Karnaugh Maps:
Here are some possible 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 implicate \(y + z + w\). However, this is not a prime implicate because we can merge the four corners into a single group.
The red group corresponds to the implicate \(\overline{x} + \overline{y} +\overline{w}\) because \(x\), \(y\) and \(w\) are always \(1\) within the group. However, this is not a prime implicate 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 implicate \(\overline{z} + w\) because \(z\) is always \(1\) within the group and \(\overline{w}\) is always \(0\) within the group. Furthermore, this is a prime implicate because the group cannot be merged into a new group with any other group of the same size. Moreover, this is an essential prime implicate because it is impossible to construct another group which corresponds to a prime implicate and also contains the cell at the last row and second column.
Note
These are not all of \(f\)'s implicates, since these are just three possible groups.