Depth of functions of the k-valued logics in finite bases / A. V. Kochergin. // Vestnik Moskovskogo Universiteta. Seriya 1. Matematika. Mekhanika. 2013. № 1. P. 56-59 [Moscow Univ. Math. Bulletin. Vol. 72, N 2, 2017. P. 0].

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≥2 and for any finite complete basis B there exists a positive constant α_B such that D_B(n)∼α_Bn for n→∞.

Key words: k-valued logics, circuit depth, finite basis.