An Improved Lower Bound on the Maximum Number of Prime Implicants

Yoshihide IGARASHI  

Publication
IEICE TRANSACTIONS (1976-1990)   Vol.E62   No.6   pp.389-394
Publication Date: 1979/06/25
Online ISSN: 
DOI: 
Print ISSN: 0000-0000
Type of Manuscript: PAPER
Category: Mathematics, Physics
Keyword: 


Full Text: PDF>>
Buy this Article




Summary: 
We formulate an improved lower bound on the maximum number of prime implicants of n-variable Boolean functions. It is given as n!/(n/3!(n1)/3!(n2)/3!)(n, 0, (n1)/32)(n, O, (n2)/32), where (n, 0, r) is evaluated by the following recursive procedure: (n, 0, r)0 for r0, (n, 0, 0)1 and (n, 0, r)n!/(r/2!(nr)!(r1)/2!)(n, 0, (r1)/2 2) for 1rn. The total logarithm computing time cost and the total uniform computing time cost of this lower bound by a random access machine are O (n (log2n)2) and O (n), respectively. The ratio of this new lower bound to the old lower bound is bounded by 1c (1/2)n/3, where c is a constant independent of n.