Abstract:
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\in [A]$ the depth $D(f)$ and the complexity $L(f)$ of $f$ in the class of formulas over $A$ satisfy the relation $D(f)\leq c\log_2 L(f)+d$.