Uniformity of some systems of multivalued logic functions / P. B. Tarasov. // Vestnik Moskovskogo Universiteta. Seriya 1. Matematika. Mekhanika. 2013. № 2. P. 61-64 [Moscow Univ. Math. Bulletin. Vol. 72, N 2, 2017. P. 0].

{For any finite system A of functions of many-valued logic taking values in the set {0,1} such that a projection of A generates the class of all monotone boolean functions, it is prooved that there exists constants c and d such that for an arbitrary function f ∈ [A] the depth D(f) and the complexity L(f) of f in the class of formulas over A satisfy the relation D(f) ≤ c log2 L(f) + d.

Key words: uniform systems, many-valued logic, monotone functions, polynomially equivalent.

№ 2/2013