|
Depth of Functions of the k-Valued Logic in Infinite Bases / Kochergin A.V. // Vestnik Moskovskogo Universiteta. Seriya 1. Matematika. Mekhanika. 2011. № 1. P. 22-26 [Moscow Univ. Math. Bulletin. Vol. 66, No 1, 2011. P. 20-24]. The realization of functions of the k-valued logic by circuits is considered over an arbitrary infinite complete basis B. The Shannon function DB(n) of the circuit depth over B is examined (for any positive integer n the value DB(n) is the minimal depth sufficient to realize every function of the k-valued logic of n variables by a circuit over B). It is shown that for each fixed k ≥ 2 and for any infinite complete basis B either there exists a constant α ≥ 1 such that DB(n) = α for all sufficiently large n, or there exist constants β (β > 0), γ, δ such that β log2n ≤ DB(n) ≤ γ log2n + δ for all n.
Key words: k-valued logics, circuit depth, infinite basis.
|