RUS  ENG
Полная версия
ЖУРНАЛЫ // Вестник Московского университета. Серия 1: Математика. Механика // Архив

Вестн. Моск. ун-та. Сер. 1. Матем., мех., 2012, номер 4, страницы 20–26 (Mi vmumm508)

Эта публикация цитируется в 2 статьях

Математика

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

Д. В. Трущин

Московский государственный университет имени М. В. Ломоносова, механико-математический факультет

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

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

УДК: 519.95

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


 Англоязычная версия: Moscow University Mathematics Bulletin, Moscow University Mеchanics Bulletin, 2012, 67:4, 158–163

Реферативные базы данных:


© МИАН, 2024