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 n ) prime implicants, and that there exist expressions with ω( 3 n n prime implicants. |
Year | DOI | Venue |
---|---|---|
1978 | 10.1016/0012-365X(78)90168-1 | DISCRETE MATHEMATICS |
Field | DocType | Volume |
Discrete mathematics,Combinatorics,Expression (mathematics),Disjunctive normal form,Implicant,Boolean expression,Mathematics,Propositional variable | Journal | 24 |
Issue | ISSN | Citations |
1 | 0012-365X | 45 |
PageRank | References | Authors |
4.45 | 2 | 2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Ashok K. Chandra | 1 | 3116 | 1215.02 |
George Markowsky | 2 | 658 | 353.44 |