loading...
Upper and Lower Bounds on the Number of Disjunctive Forms
Singapore May 17-May 20
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/ISMVL.2006.4436th International Symposium on Multi ...
 This Article 
 
PDF
HTML
 
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
Hisayuki TATSUMI, Tsukuba University of Technology, Japan
Masahiro MIYAKAWA, Tsukuba University of Technology, Japan
Masao MUKAIDONO, Meiji University, Japan
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.
Citation:
Hisayuki TATSUMI, Masahiro MIYAKAWA, Masao MUKAIDONO, "Upper and Lower Bounds on the Number of Disjunctive Forms," ismvl, pp.8, 36th International Symposium on Multiple-Valued Logic (ISMVL'06), 2006
Usage of this product signifies your acceptance of the Terms of Use.