Some sufficient conditions for uniformness of systems of multi-valued logic functions / P. B. Tarasov. //Vestnik Moskovskogo Universiteta. Seriya 1. Matematika. Mekhanika. 2013. № 5. P. 41-46 [Moscow Univ. Math. Bulletin. Vol. 68, N 5, 2013.].
For any finite system A of functions of k-valued logic taking values in the set Es={0,…,s-1}, k ≥ s ≥ 2, such that the closed class generated by restriction of functions from A on the set Es contains a near-unanimity function, it is proved that there exists constants c and d such that for an arbitrary function f ∈ [A] the depth DA(f) and the complexity LA(f) of f in the class of formulas over A satisfy the relation DA(f) ≤ c log2 LA(f) + d.
Key words: uniform systems, many-valued logic, polynomially equivalent, near-unanimity function.