Двойственная булева функция к булевой функции — функция , определяемая соотношением
Понятие «двойственной функции» является очень важным в теории булевых функций и широко используется в ней: при помощи понятия двойственной функции определяется принцип двойственности для булевых функций; при помощи понятия двойственной функции определяется класс самодвойственных функций, который является одним из пяти предполных классов булевых функций.
Функция, двойственная к двойственной, совпадает с исходной функцией, то есть . Функция, двойственная к которой совпадает с ней собой, называется самодвойственной.
Примеры Константы двойственны друг к другу:
Тождественная функция самодвойственна:
Отрицание самодвойственно:
Дизъюнкция двойственна к конъюнкции:
Исключающее или двойственно к эквиваленции:
Импликация двойственна к обратной коимпликации:
Обратная импликация двойственна к коимпликации:
Штрих Шеффера двойственен к стрелке Пирса:
Функция голосования самодвойственна:
Принцип двойственности Введём понятие двойственной булевой формулы. Пусть — булева формула. Двойственная к ней формула индуктивно определяется следующим образом: Если имеет вид , где — переменная, то ; Если имеет вид , где — функция арности , — некоторые формулы, то
Принцип двойственности: если формула задаёт относительно набора переменных функцию , то формула задаёт относительно набора переменных функцию .
Из принципа двойственности следует следующее: если верно некоторое тождество , то двойственное к нему тождество тоже верно. Это позволяет выводить новые тождества из известных, просто заменив все функции в тождестве на двойственные. Пример: Возьмём верное тождество . Заменив левую и правую формулы на двойственные получим — тоже верное тождество. Такое тождество называют двойственным тождеством.
Для различных нормальных форм можно получать двойственные к ним формы. Например, каждая функция представляется в виде дизъюнктивной нормальной формы. Представим в ДНФ двойственную к ней функцию , а затем по принципу двойственности получим представление . Мы получили другую нормальную форму, перейдя к двойственной формуле. Такая нормальная форма называется двойственной нормальной формой к исходной нормальной форме. Двойственная нормальная форма к ДНФ — конъюнктивная нормальная форма. Аналогично можно получить, например, двойственную форму к полиному Жегалкина, которая также будет выглядеть как многочлен, но роль умножения в ней будет играть дизъюнкция, а роль сложения — эквиваленция. Такая нормальная форма называется кополином Жегалкина.
Двойственные системы функций Понятие двойственности распространяется на системы функций. Пусть — система булевых функций. Двойственная система определяется следующим образом:
Примером двойственных систем является, например, класс функций, сохраняющих , и класс функций, сохраняющих . Классы линейных, самодвойственных, монотонных и всех булевых функций — самодвойственны.
Для операции дуализации систем верны следующие соотношения:
если , то если , то Из третьего соотношения непосредственно следует, что двойственная система к замкнутому классу — замкнутый класс; если система полна в замкнутом классе , то и полна в замкнутом классе ; если система базис в замкнутом классе , то и базис в замкнутом классе . Поэтому для самодвойственных замкнутых классов двойственная к базису система тоже является базисом. Примеры двойственных базисов в : и ; и ; и ;
Примечания
Литература
Категория:Теория дискретных функций