Prime Implicants, Minimum Covers, and the Complexity of Logic Simplification

1 August 1986

journal article
Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers

Vol. C-35 (8) , 761-762
https://doi.org/10.1109/tc.1986.1676828

Abstract

We show that any Boolean function f which can be expressed in a sum-of-products form using m product terms can contain as many as 2^m− 1 implicants but no more.

Keywords

BOOLEAN FUNCTION
PRIME IMPLICANTS
MINIMUM COVERS
LOGIC SIMPLIFICATION
M PRODUCT TERM

This publication has 2 references indexed in Scilit:

Characteristic measures of switching functions
Information Sciences, 1977
Average Values of Quantities Appearing in Boolean Function Minimization
IEEE Transactions on Electronic Computers, 1964