Головная страница ИПМ Библиотеки, издания  •  Поиск публикаций  English 
Публикация

№18, Москва, 2013
Авторы: Дагаев Д.А.
О сложности функций многозначной логики, принимающих два значения
Аннотация:
В работе рассматривается задача о сложности реализации формулами функций из P3,2 - множества всех трехзначной логики, принимающих значения 0 или 1. Для каждого конечно-порожденного максимального (в решетке классов с одинаковой проекцией) замкнутого класса функций из P3,2 и некоторой конечной системы, порождающей его, получены верхние и нижние оценки для соответствующих функций Шеннона. Для каждого конечно-порожденного замкнутого класса F функций из P3,2, за исключением максимального, такого, что проекция F совпадает с множеством всех линейных булевых функций, и некоторой конечной порождающей системы такого класса найдены точные формулы для соответствующих функций Шеннона. Выделено некоторое счетное семейство B замкнутых классов булевых функций и показано, что для каждого замкнутого класса F функций из P3,2, проекция которого принадлежит семейству B, и любой конечной системы, порождающей F, функция Шеннона по глубине, соответствующая классу F, имеет линейный порядок роста.
Ключевые слова:
функции многозначной логики, формулы, сложность
Язык публикации: русский, страниц: 88 (с. 35-122)
Направление исследований:
Математические вопросы и теория численных методов
Полный текст: Сведения об авторах:
  • Дагаев Дмитрий Александрович,  ,  НИУ Высшая школа экономики