УДК 511
О равномерности некоторых систем функций многозначной логики / П. Б. Тарасов. // Вестн. Моск. ун-та. Сер. 1, Математика. Механика. 2013. № 2. С. 61-64.
Рассматривается конечная система A функций многозначной логики, принимающих значения 0 и 1, причем проекция системы A порождает класс всех монотонных булевых функций. Показано, что найдутся константы c и d, такие, что для любой функции f из [A] глубина D(f) и сложность L(f) функции f в классе формул над A связаны соотношением D(f) ≤ c log2L(f) + d.
Ключевые слова: равномерность конечных систем, многозначная логика, монотонные функции, полиномиальная эквивалентность.
Библиогр. 11.
