The Full Wiki

More info on Prime implicant

Prime implicant: Wikis

Advertisements

Note: Many of our articles have direct quotes from sources you can cite, within the Wikipedia article! This article doesn't yet, but we're working on it! See more info or our list of citable articles.

Encyclopedia

(Redirected to Implicant article)

From Wikipedia, the free encyclopedia

In Boolean logic, an implicant is a "covering" (sum term or product term) of one or more minterms in a sum of products (or maxterms in a product of sums) of a boolean function. Formally, a product term P in a sum of products is an implicant of the Boolean function F if P implies F. More precisely:

P implies F (and thus is an implicant of F) if F also takes the value 1 whenever P equals 1.

where

This means that P = > F with respect to the natural ordering of the Boolean space. For instance, the function

f(x,y,z,w) = xy + yz + w

is implied by xy, by xyz, by xyzw, by w and many others; these are the implicants of f.

Contents

Prime implicant

A prime implicant of a function is an implicant that cannot be covered by a more general (more reduced - meaning with fewer literals) implicant. W.V. Quine defined a prime implicant of F to be an implicant that is minimal - that is, if the removal of any literal from P results in a non-implicant for F. Essential prime implicants are prime implicants that cover an output of the function 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. [1]

The sum of all prime implicants of a Boolean function is called the complete sum of that function.

See also

References

  1. ^ De Micheli, Giovanni. Synthesis and Optimization of Digital Circuits. McGraw-Hill, Inc., 1994

External links

Advertisements

Advertisements






Got something to say? Make a comment.
Your name
Your email address
Message