Asymptotic behavior of the Shannon function for a class of circuits of functional elements. (Q1284339)

The author investigates the particular case of so called transistor circuits of functional elements (c.f.e.) in which every functional element corresponds to some circuit with a single delay and implements the Boolean function which is everywhere determined. The transistor circuits of functional elements are constructed on the basis \(B(m)\) of all functional elements, every element has the complexity (weight) which is not more than m. The author considers Shannon's function \[ L_{B(m)} (n)\,=\,\max \min\, L(s), \] in which \(L(s)\) is the total weight of all functional elements of the circuit and which is minimized on the set of all c.f.e., implementing the Boolean function \(f\) of \(n\) variables, and is maximized on the set of all such functions \(f\). The major result is the asymptotic approximation of Shannon's function \[ L_{B(m)} (n)\,\sim \, 2^{n+1}/n, \] that does not depend on \(m\).