We evaluate the upper and lower bounds on the number of disjunctive (normal) forms of an n-variable Boolean function (for our purpose it is sufficient to take the constant 1 function which always takes the value 1). We use a one-to-one correspondence between the disjunctive forms and the antichains in the ternary n-cube which is isomorphic to the partially ordered set formed by all terms of the given function. For the upper bound we use a newly invented decomposition of the partially ordered set into chains (we introduce trees which span the cube). For the lower bounds, we evaluate the number of anticains in the cube by analyzing the dependency among the three consecutive layers instead of two. Put DF(1) the number of different disjunctive forms for the constant 1 function. We obtain newly improved upper and lower bounds.
['Hisayuki Tatsumi', 'Masahiro Miyakawa', 'Masao Mukaidono']
Upper and Lower Bounds on the Number of Disjunctive Forms