George Markowsky
Algebra Universalis
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.
George Markowsky
Algebra Universalis
Ashok K. Chandra
FOCS 1978
Ashok K. Chandra, Martin Tompa
Discrete Applied Mathematics
Ronald V. Book, Ashok K. Chandra
Acta Informatica