On the Number of Prime Implicants
It is shown that any Boolean expression in disjunctive normal form having k conjuncts, can have at most 2k prime implicants. However, there exist such expressions that have 2k/2 prime implicants. It is also shown that any Boolean expression on n distinct propositional variables can have at most O(3n√n) prime implicants, and that there exist expressions with Ω(3n/n) prime implicants.
A. K. Chandra and G. Markowsky, "On the Number of Prime Implicants," Discrete Mathematics, vol. 24, no. 1, pp. 7-11, Elsevier, Jan 1978.
The definitive version is available at http://dx.doi.org/10.1016/0012-365X(78)90168-1
International Standard Serial Number (ISSN)
Article - Journal
© 1978 Elsevier, All rights reserved.