The depth of Boolean functions realized by circuits over an arbitrary basis
O. M. Kasim-Zade · Moscow University Mathematics Bulletin · 2007
Realization of Boolean functions by circuits of functional elements is considered over arbitrary complete bases (including infinite ones). The depth of a circuit means the maximal number of functional elements forming an oriented chain going from inputs of the circuit to its output. It is shown that for any basis B the growth order of the Shannon function of depth D B (n) for n → ∞ is equal to 1, log2 n, or n, and the latter case appears if and only if the basis B is finite.