NUMBER OF PRIME IMPLICANTS

被引：55

作者：

CHANDRA, AK

MARKOWSKY, G

机构：

[1] Computer Sciences Department, IBM Thomas J. Watson Research Center, Yorktown Heights, NY 10598

来源：

DISCRETE MATHEMATICS | 1978年 / 24卷 / 01期

关键词：

D O I：

10.1016/0012-365X(78)90168-1

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

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.

引用

页码：7 / 11

页数：5