Abstract:
Realization of Boolean functions by circuits is considered over an arbitrary infinite complete basis. The depth of a circuit is defined as the greatest number of functional elements constituting a directed path from an input of the circuit to its output. The Shannon function of the depth is defined for a positive integer $n$ as the minimal depth $D_B(n)$ of the circuits sufficient to realize every Boolean function on $n$ variables over a basis $B$. It is shown that, for each infinite basis $B$, either there exists a constant $\beta\geqslant 1$ such that $D_B(n)=\beta$ for all sufficiently large $n$ or there exist an integer constant $\gamma\geqslant 2$ and a constant $\delta$ such that $\log_\gamma n\geqslant D_B(n)\geqslant\log_\gamma n+\delta$ for all $n$.