О РАВНОМЕРНОСТИ НЕКОТОРЫХ СИСТЕМ ФУНКЦИЙ МНОГОЗНАЧНОЙ ЛОГИКИ

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

• Тарасов П.Б.

• Прикладные науки. Медицина. Технология

• Естественные науки