On the Number of Prime Implicants

Author

Ashok K. Chandra
George Markowsky, Missouri University of Science and TechnologyFollow

Abstract

It is shown that any Boolean expression in disjunctive normal form having k conjuncts, can have at most 2^k 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(3ⁿ√n) prime implicants, and that there exist expressions with Ω(3ⁿ/n) prime implicants.

Recommended Citation

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 https://doi.org/10.1016/0012-365X(78)90168-1

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.

Publication Date

01 Jan 1978