Abstract:
We consider the set of functions defined by read-once formulas with binary conjunction (logical AND) and disjunction (logical OR) operations. For the functions defined by formulas with a fixed number of operations we investigate the weights of functions, i.e. the number of tuples on which the function has value 1. We establish asymptotic bounds on the number of read-once formulas that define functions with specific weights, in particular on the number of formulas, that define functions with no more than a quarter of ones among their values.
Keywords:Boolean function, read-once formula, function weight, asymptotic bound.