George Markowsky
Semigroup Forum
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
Semigroup Forum
Ashok K. Chandra, Harry R. Lewis, et al.
STOC 1981
George Markowsky, Robert Endre Tarjan
Discrete Mathematics
Alok Aggarwal, Ashok K. Chandra, et al.
Theoretical Computer Science