В работе рассматривается задача о соотношении глубины и сложности формул, реализующих функции из предполных классов k-значной логики. Для всех предполных классов типов E, B, L, P, а также некоторых предполных классов типов O и C в P_k, k ≥ 3, показано, что любая конечная система функций A, порождающая один из этих классов, удовлетворяет следующему условию: найдутся такие константы c и d, что для любой функции f из [A] глубина D(f) и сложность L(f) функции f в классе формул над A связаны соотношением D(f) ≤ c log₂ L(f) + d. Также доказано существование конечных порождающих систем, удовлетворяющих этому условию, для всех предполных классов в P_k, 2 ≤ k ≤ 7, и для всех предполных классов типа C в P_k, k ≥ 2.

предполные классы k-значной логики, глубина и сложность формул

Математические вопросы и теория численных методов