RUS  ENG
Full version
JOURNALS // Intelligent systems. Theory and applications // Archive

Intelligent systems. Theory and applications, 2019 Volume 23, Issue 3, Pages 41–55 (Mi ista237)

Part 2. Special Issues in Intellectual Systems Theory

On the weight of functions, defined by read-once AND/OR formulas

A. R. Eremenko, A. D. Yashunskii


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.



© Steklov Math. Inst. of RAS, 2024