Аннотация:
Рассматривается конечная система $A$ функций многозначной логики, принимающих значения $0$ и $1$, причем проекция системы $A$ порождает класс всех монотонных булевых функций. Показано, что найдутся константы $c$ и $d$, такие, что для любой функции $f$ из $[A]$ глубина $D(f)$ и сложность $L(f)$ функции $f$ в классе формул над $A$ связаны соотношением $D(f)\leq c\log_2 L(f)+d$.
Ключевые слова:равномерность конечных систем, многозначная логика, монотонные функции, полиномиальная эквивалентность.