УДК 511
О некоторых достаточных условиях равномерности систем функций многозначной логики / П. Б. Тарасов. // Вестн. Моск. ун-та. Сер. 1, Математика. Механика. 2013. № 5. С. 41-46.
Для произвольной конечной системы A функций k-значной логики, принимающих значения из множества Es={0,…,s-1}, k ≥ s ≥ 2, такой, что замкнутый класс, порожденный ограничением функций из A на множество Es, содержит мажоритарную функцию, доказано существование констант c и d, таких, что для любой функции f ∈ [A] глубина DA(f) и сложность LA(f) функции f в классе формул над A связаны соотношением DA(f) ≤ c log2 LA(f) + d. }
Ключевые слова: равномерность конечных систем, многозначная логика, полиномиальная эквивалентность, мажоритарная функция.
Библиогр. 22.
