Д. А. Дагаев, “О сложности функций из некоторых классов трехзначной логики”, Вестн. Моск. ун-та. Сер. 1. Матем., мех., 2011, номер 3,страницы 60

Краткие сообщения

О сложности функций из некоторых классов трехзначной логики

Д. А. Дагаев

Национальный исследовательский университет "Высшая школа экономики", г. Москва

Аннотация: Рассматривается задача о сложности реализации функций трехзначной логики, принимающих значения из множества $\{0,1\}$, формулами в неполных базисах. Получены верхние и нижние асимптотические оценки для соответствующих функций Шеннона.

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

УДК: 519.714

Поступила в редакцию: 18.02.2011