In this paper we consider the relation between depth and complexity of formulas in precomplete classes of k-valued logic. For all precomplete classes of types E, B, L, P and some precomplete classes of types O and C in P_k, k ≥ 3, we show that any finite system of functions A generating any of these classes satisfies the following condition: there exist constants c and d such that for any function f from [A] the depth D(f) and the complexity L(f) of function f in the class of formulas over A satisfy the relation D(f) ≤ c log₂ L(f) + d. We also show the existence of finite generating systems satisfying this condition for all precomplete classes in P_k, 2 ≤ k ≤ 7, and for all precomplete classes of type C in P_k, k ≥ 2.

precomplete classes of k-valued logic, depth and complexity of formulas

Mathematical problems and theory of numerical methods