Depth of Schemes Embedded in a Unit Cube and Implementing Typical Boolean Functions

Аннотация

A class of schemes of functional elements in the standard basis of conjunction, disjunction, and negation elements is considered. For each scheme Σ from this class, in addition to depth D(Σ), its dimension R(Σ) is determined and found to be equal to the minimum dimension of the unit (Boolean) cube that allows isomorphic embedding Σ. In addition to results obtained earlier, it is proved that within the considered model inequality \(D({\Sigma _f}) \ge n + \frac{n}{{{{\log }_2}n}} - O(\frac{n}{{{{({{\log }_2}n)}^2}}})\) is satisfied for typical function f of n variables and for any scheme of functional elements Σ_f implementing it, such that R(Σ_f) = O(n), n = 1,2,.... New and more accurate lower estimates of the depth of the schemes implementing the typical functions and having linear dimensions are thus obtained.