Title

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 2k/2 prime implicants. It is also shown that any Boolean expression on n distinct propositional variables can have at most O(3nn) prime implicants, and that there exist expressions with Ω(3n/n) prime implicants.

Department(s)

Computer Science

International Standard Serial Number (ISSN)

0012-365X

Document Type

Article - Journal

Document Version

Citation

File Type

text

Language(s)

English

Rights

© 1978 Elsevier, All rights reserved.

Share

 
COinS