For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
An Improved Lower Bound on the Maximum Number of Prime Implicants
IEICE TRANSACTIONS (1976-1990)
Publication Date: 1979/06/25
Print ISSN: 0000-0000
Type of Manuscript: PAPER
Category: Mathematics, Physics
Full Text: PDF>>
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.