Статья в сборнике "Математические вопросы кибернетики" №19, Москва, 2019
Авторы:Акулов Я.В.
О классах булевых функций, выразимых относительно расширенной суперпозиции
Аннотация:
В данной статье рассматривается задача о реализации булевых функций формулами специального вида, в которых в качестве тривиальных формул выступают функции из некоторого множества. Для данного способа реализации функций вводится понятие операции расширенной суперпозиции. Для рассматриваемой операции получен критерий выразимости булевых функций, а также критерий разложимости пополнений всех замкнутых классов булевых функций относительно расширенной суперпозиции в пересечение пополнений других замкнутых классов, и критерий полноты операции расширенной суперпозиции для класса P2 и всех предполных классов булевых функций. В работе приведено полное описание множества всех пополнений замкнутых классов булевых функций, содержащих неконстантные функции, относительно друг друга.
