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

Статья в сборнике "Математические вопросы кибернетики" №19, Москва, 2019
Авторы: Акулов Я.В.
О классах булевых функций, выразимых относительно расширенной суперпозиции
Аннотация:
В данной статье рассматривается задача о реализации булевых функций формулами специального вида, в которых в качестве тривиальных формул выступают функции из некоторого множества. Для данного способа реализации функций вводится понятие операции расширенной суперпозиции. Для рассматриваемой операции получен критерий выразимости булевых функций, а также критерий разложимости пополнений всех замкнутых классов булевых функций относительно расширенной суперпозиции в пересечение пополнений других замкнутых классов, и критерий полноты операции расширенной суперпозиции для класса P2 и всех предполных классов булевых функций. В работе приведено полное описание множества всех пополнений замкнутых классов булевых функций, содержащих неконстантные функции, относительно друг друга.
Ключевые слова:
булева функция, расширенная суперпозиция, замкнутый класс, критерий полноты
Язык публикации: русский,  страниц: 76 (с. 123-198)
Направление исследований:
Математические вопросы и теория численных методов
Полный текст на русском языке: Сведения об авторах:
  • Акулов Ярослав Викторович,  ,  МГУ им. М. В. Ломоносова, механико-математический факультет