On the number of prime implicants

Abstract

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 2 k 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. © 1978.