Implicant

{{anchor|Essential prime implicant}}Prime implicant ==

A prime implicant of a function is an implicant (in the above particular sense) that cannot be covered by a more general (more reduced, meaning with fewer literals) implicant. W. V. Quine defined a prime implicant to be an implicant that is minimal—that is, the removal of any literal from P results in a non-implicant for F. An essential prime implicant (also known as core prime implicant) is a prime implicant that covers an input combination, for which the function is true (i.e. outputs 1), that no combination of other prime implicants is able to cover.

Using the example above, one can easily see that while xy (and others) is a prime implicant, xyz and xyzw are not. From the latter, multiple literals can be removed to make it prime:

• x, y and z can be removed, yielding w.
• Alternatively, z and w can be removed, yielding xy.
• Finally, x and w can be removed, yielding yz.

The process of removing literals from a Boolean term is called expanding the term. Expanding by one literal doubles the number of input combinations for which the term is true (in binary Boolean algebra). Using the example function above, we may expand xyz to xy or to yz without changing the cover of f.

The sum of all prime implicants of a Boolean function is called its complete sum, minimal covering sum, or Blake canonical form.

References

References

1. "Lecture 8".
2. "What are the essential prime implicants?".
3. De Micheli, Giovanni. ''Synthesis and Optimization of Digital Circuits''. McGraw-Hill, Inc., 1994