In
Boolean logic, the term implicant has either a generic or a particular meaning. In the generic use, it refers to the hypothesis of an implication (
implicant). In the particular use, a
product term In Boolean logic, a product term is a conjunction of literals, where each literal is
either a variable or its negation.
Examples
Examples of product terms include:
:A \wedge B
:A \wedge (\neg B) \wedge (\neg C)
:\neg A
Origin
The terminology come ...
(i.e., a conjunction of literals) ''P'' is an implicant of a Boolean function ''F'', denoted
, if ''P'' implies ''F'' (i.e., whenever ''P'' takes the value 1 so does ''F'').
For instance, implicants of the function
:
include the terms
,
,
,
,
as well as some others.
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''. Essential prime implicants (aka core 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
(and others) is a prime implicant,
and
are not. From the latter, multiple literals can be removed to make it prime:
*
,
and
can be removed, yielding
.
*Alternatively,
and
can be removed, yielding
.
*Finally,
and
can be removed, yielding
.
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
to
or to
without changing the cover of
.
[De Micheli, Giovanni. ''Synthesis and Optimization of Digital Circuits''. McGraw-Hill, Inc., 1994]
The sum of all prime implicants of a Boolean function is called its complete sum, minimal covering sum, or
Blake canonical form
In Boolean logic, a formula for a Boolean function ''f'' is in Blake canonical form (BCF), also called the complete sum of prime implicants, the complete sum, or the disjunctive prime form, when it is a disjunction of all the prime implicants of ...
.
See also
*
Quine–McCluskey algorithm
The Quine–McCluskey algorithm (QMC), also known as the method of prime implicants, is a method used for minimization of Boolean functions that was developed by Willard V. Quine in 1952 and extended by Edward J. McCluskey in 1956. As a genera ...
*
Karnaugh map
The Karnaugh map (KM or K-map) is a method of simplifying Boolean algebra expressions. Maurice Karnaugh introduced it in 1953 as a refinement of Edward W. Veitch's 1952 Veitch chart, which was a rediscovery of Allan Marquand's 1881 ''logi ...
*
Petrick's method
In Boolean algebra
In mathematics and mathematical logic, Boolean algebra is a branch of algebra. It differs from elementary algebra in two ways. First, the values of the variables are the truth values ''true'' and ''false'', usually deno ...
References
{{reflist
External links
Slides explaining implicants, prime implicants and essential prime implicants
Boolean algebra