Abstract:
For any finite system $A$ of functions of $k$-valued logic taking values in the set $E_s={\{0,1,\ldots, s-1\}}$, $k\geq s\geq2$, 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 exists constants $c$ and $d$ such that for an arbitrary function $f \in [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) \leq c\log_2 L_A(f)+d}$.