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 DB(n) of the circuit depth over B is examined. The value DB(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 DB(n)∼αBn for n→∞.

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

№ 1/2013