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

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

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

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

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

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

Примеры

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

$c=0$

$c^{*}=1$

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

$f(x)=x$

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

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

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

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

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

$f(x,y)=x\lor y$

$f^{*}(x,y)=x\land y$

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

$f(x,y)=x\oplus y$

$f^{*}(x,y)=x\leftrightarrow y$

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

$f(x,y)=x\rightarrow y$

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

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

$f(x,y)=x\leftarrow y$

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

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

$f(x,y)=x\,|\,y$

$f^{*}(x,y)=x\downarrow y$

Принцип двойственности

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

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

$\Phi ^{*}=x$;

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

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

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

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

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

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

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

Двойственные системы функций

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

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

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

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

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

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

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

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

• $\{\lnot ,\lor \}$ и $\{\lnot ,\land \}$;
• $\{\oplus ,\land ,1\}$ и $\{\leftrightarrow ,\lor ,0\}$;
• $\{|\}$ и $\{\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 с.