High-Accuracy Bounds of the Shannon Function for Formula Complexity in Bases with Direct and Iterative Variables

Аннотация

We consider the realization of Boolean functions by formulas with restrictions on superpositions of basis functions such that superposition is allowed only by iterative variables. For a number of special symmetrical bases, we establish new high-accuracy bounds of the Shannon function L(n) for the complexity of realization of Boolean functions dependent on n direct variables.