Двойственная булева функция

Двойственная булева функция к булевой функции ${\displaystyle f\colon E_{2}^{n}\to E_{2}}$ — функция ${\displaystyle f^{*}\colon E_{2}^{n}\to E_{2}}$, определяемая соотношением

${\displaystyle f^{*}(x_{1},\ldots ,x_{n})={\overline {f({\overline {x_{1}}},\ldots ,{\overline {x_{n}}})}}}$^[1]

Понятие «двойственной функции» является очень важным в теории булевых функций и широко используется в ней:

• при помощи понятия двойственной функции определяется принцип двойственности для булевых функций;
• при помощи понятия двойственной функции определяется класс самодвойственных функций, который является одним из пяти предполных классов булевых функций.

Функция, двойственная к двойственной, совпадает с исходной функцией, то есть ${\displaystyle f^{**}=f}$.^[2] Функция, двойственная к которой совпадает с ней собой, называется самодвойственной.^[3]

• Константы двойственны друг к другу:

${\displaystyle c=0}$

${\displaystyle c^{*}=1}$

• Тождественная функция самодвойственна:

${\displaystyle f(x)=x}$

${\displaystyle f^{*}(x)=x}$

• Отрицание самодвойственно:

${\displaystyle f(x)={\overline {x}}}$

${\displaystyle f^{*}(x)={\overline {x}}}$

• Дизъюнкция двойственна к конъюнкции:

${\displaystyle f(x,y)=x\lor y}$

${\displaystyle f^{*}(x,y)=x\land y}$^[2]

• Исключающее или двойственно к эквиваленции:

${\displaystyle f(x,y)=x\oplus y}$

${\displaystyle f^{*}(x,y)=x\leftrightarrow y}$^[4]

• Импликация двойственна к обратной коимпликации:

${\displaystyle f(x,y)=x\rightarrow y}$

${\displaystyle f^{*}(x,y)=x\not \leftarrow y}$

• Обратная импликация двойственна к коимпликации:

${\displaystyle f(x,y)=x\leftarrow y}$

${\displaystyle f^{*}(x,y)=x\not \rightarrow y}$^[5]

• Штрих Шеффера двойственен к стрелке Пирса:

${\displaystyle f(x,y)=x\,|\,y}$

${\displaystyle f^{*}(x,y)=x\downarrow y}$^[6]

Введём понятие двойственной булевой формулы. Пусть ${\displaystyle \Phi }$ — булева формула. Двойственная к ней формула ${\displaystyle \Phi ^{*}}$ индуктивно определяется следующим образом:

• Если ${\displaystyle \Phi }$ имеет вид ${\displaystyle \Phi =x}$, где ${\displaystyle x}$ — переменная, то

${\displaystyle \Phi ^{*}=x}$;

• Если ${\displaystyle \Phi }$ имеет вид ${\displaystyle \Phi =f(\varphi _{1},\ldots ,\varphi _{n})}$, где ${\displaystyle f}$ — функция арности ${\displaystyle n}$, ${\displaystyle \varphi _{1},\ldots ,\varphi _{n}}$ — некоторые формулы, то

${\displaystyle \Phi ^{*}=f^{*}(\varphi _{1}^{*},\ldots ,\varphi _{n}^{*})}$

Принцип двойственности: если формула ${\displaystyle \Phi }$ задаёт относительно набора переменных ${\displaystyle x_{1},\ldots ,x_{n}}$ функцию ${\displaystyle f(x_{1},\ldots ,x_{n})}$, то формула ${\displaystyle \Phi ^{*}}$ задаёт относительно набора переменных ${\displaystyle x_{1},\ldots ,x_{n}}$ функцию ${\displaystyle f^{*}(x_{1},\ldots ,x_{n})}$.^[7]

Из принципа двойственности следует следующее: если верно некоторое тождество ${\displaystyle \Phi (x_{1},\ldots ,x_{n})=\Psi (x_{1},\ldots ,x_{n})}$, то двойственное к нему тождество ${\displaystyle \Phi ^{*}(x_{1},\ldots ,x_{n})=\Psi ^{*}(x_{1},\ldots ,x_{n})}$ тоже верно. Это позволяет выводить новые тождества из известных, просто заменив все функции в тождестве на двойственные. Пример:

• Возьмём верное тождество ${\displaystyle {\overline {x\land y}}={\overline {x}}\lor {\overline {y}}}$. Заменив левую и правую формулы на двойственные получим ${\displaystyle {\overline {x\lor y}}={\overline {x}}\land {\overline {y}}}$ — тоже верное тождество.^[8]

Такое тождество называют двойственным тождеством.

Для различных нормальных форм можно получать двойственные к ним формы. Например, каждая функция ${\displaystyle f}$ представляется в виде дизъюнктивной нормальной формы. Представим в ДНФ двойственную к ней функцию ${\displaystyle f^{*}(x_{1},\ldots ,x_{n})=\Phi (x_{1},\ldots ,x_{n})}$, а затем по принципу двойственности получим представление ${\displaystyle (x_{1},\ldots ,x_{n})=\Phi ^{*}(x_{1},\ldots ,x_{n})}$. Мы получили другую нормальную форму, перейдя к двойственной формуле. Такая нормальная форма называется двойственной нормальной формой к исходной нормальной форме. Двойственная нормальная форма к ДНФ — конъюнктивная нормальная форма. Аналогично можно получить, например, двойственную форму к полиному Жегалкина, которая также будет выглядеть как многочлен, но роль умножения в ней будет играть дизъюнкция, а роль сложения — эквиваленция. Такая нормальная форма называется кополином Жегалкина.^[9]

Понятие двойственности распространяется на системы функций. Пусть ${\displaystyle K\subseteq P_{2}}$ — система булевых функций. Двойственная система ${\displaystyle K^{*}}$ определяется следующим образом:

${\displaystyle K^{*}=\{f^{*}|f\in K\}}$

Примером двойственных систем является, например, класс функций, сохраняющих ${\displaystyle 0}$, и класс функций, сохраняющих ${\displaystyle 1}$.^[5] Классы линейных, самодвойственных, монотонных и всех булевых функций — самодвойственны.

Для операции дуализации систем верны следующие соотношения:

• ${\displaystyle K=K^{**}}$
• если ${\displaystyle K\subseteq L}$, то ${\displaystyle K^{*}\subseteq L^{*}}$
• если ${\displaystyle K=[L]}$, то ${\displaystyle K^{*}=[L^{*}]}$

Из третьего соотношения непосредственно следует, что

• двойственная система к замкнутому классу — замкнутый класс;
• если система ${\displaystyle K}$ полна в замкнутом классе ${\displaystyle L}$, то и ${\displaystyle K^{*}}$ полна в замкнутом классе ${\displaystyle L^{*}}$;
• если система ${\displaystyle K}$ базис в замкнутом классе ${\displaystyle L}$, то и ${\displaystyle K^{*}}$ базис в замкнутом классе ${\displaystyle L^{*}}$.

Поэтому для самодвойственных замкнутых классов двойственная к базису система тоже является базисом. Примеры двойственных базисов в ${\displaystyle P_{2}}$:

• ${\displaystyle \{\lnot ,\lor \}}$ и ${\displaystyle \{\lnot ,\land \}}$;
• ${\displaystyle \{\oplus ,\land ,1\}}$ и ${\displaystyle \{\leftrightarrow ,\lor ,0\}}$;
• ${\displaystyle \{|\}}$ и ${\displaystyle \{\downarrow \}}$;

• Яблонский С. В. Введение в дискретную математику. — М.: Наука, 1986. — 384 с.
• Математическая логика и теория алгоритмов. Лекции 2–4: пропозициональные формулы и булевы функции  (рус.). https://old.mipt.ru/education/chairs/dm/. Дата обращения: 4 мая 2024.
• Колпаков Р. М, Кочергин В. В. Теория дискретных функций  (рус.). https://teach-in.ru/. Дата обращения: 4 мая 2024.
• Подколзин А. С. 2 лекция курса «Теория дискретных функций»  (рус.). http://intsys.msu.ru. Дата обращения: 4 мая 2024.
• Рагимханов В. Р. Дискретная математика. Часть IV. Булевы функции.. — Махачкала: ДГУ, 2019. — 102 с.