Certain sufficient conditions of uniformity for systems of functions of many-valued logic
P. B. Tarasov · Moscow University Mathematics Bulletin · 2013
For any finite system A of functions of the k-valued logic taking values in the set E s = {0,1,…, s − 1}, k ≥ s ≥ 2, such that the closed class generated by restriction of functions from A on the set E s contains a near-unanimity function, it is proved that there exist constants c and d such that for an arbitrary function f ∈ [A] the depth D A (f) and the complexity L A (f) of f in the class of formulas over A satisfy the relation D A (f) ≤ clog2 L A (f) + d.