УДК 519.95

О сложности реализации функций из одного класса трехзначной логики формулами специального вида / Д. В. Трущин. // Вестн. Моск. ун-та. Сер. 1, Математика. Механика. 2012. № 4. С. 20-26.

В работе описан некоторый класс функций трехзначной логики, для которого получены верхние оценки функции Шеннона в классе формул специального вида. Приведены также примеры последовательностей функций из рассматриваемого класса, для которых установлены экспоненциальные относительно числа переменных нижние оценки сложности. При этом значения функции Шеннона для рассматриваемого класса найдены с точностью до аддитивной константы.

Ключевые слова: функция трехзначной логики, формула, сложность, глубина.

Библиогр. 10.