Abstract:
Realization of functions of $k$-valued logic by circuits is considered over an arbitrary finite complete basis $B$. Asymptotic behaviour of the Shannon function $D_B(n)$ of the circuit depth over $B$ is examined. The value $D_B(n)$ is the minimal depth sufficient to realize every function of $k$-valued logic on $n$ variables by a circuit over $B$. It is shown that for each natural $k\ge2$ and for any finite complete basis $B$ there exists a positive constant $\alpha_B$ such that $D_B(n)\sim\alpha_B n$ for $n\to\infty$.