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

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

$f^{*}(x_1,\dots ,x_n)=\overline{f(\stackrel{‾}{x_1},\dots ,\stackrel{‾}{x_n})}$Шаблон:Sfn

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

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

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

Примеры

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

$c=0$

$c^{*}=1$

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

$f(x)=x$

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

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

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

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

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

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

$f^{*}(x,y)=x\wedge y$Шаблон:Sfn

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

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

$f^{*}(x,y)=x\leftrightarrow y$Шаблон:Sfn

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

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

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

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

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

$f^{*}(x,y)=x\to ̸y$Шаблон:Sfn

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

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

$f^{*}(x,y)=x\downarrow y$Шаблон:Sfn

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

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

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

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

• Если $\mathrm{\Phi }$ имеет вид $\mathrm{\Phi }=f({\phi }_1,\dots ,{\phi }_n)$, где $f$ — функция арности $n$, ${\phi }_1,\dots ,{\phi }_n$ — некоторые формулы, то

${\mathrm{\Phi }}^{*}=f^{*}({\phi }_1^{*},\dots ,{\phi }_n^{*})$

Принцип двойственности: если формула $\mathrm{\Phi }$ задаёт относительно набора переменных $x_1,\dots ,x_n$ функцию $f(x_1,\dots ,x_n)$, то формула ${\mathrm{\Phi }}^{*}$ задаёт относительно набора переменных $x_1,\dots ,x_n$ функцию $f^{*}(x_1,\dots ,x_n)$.Шаблон:Sfn

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

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

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

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

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

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

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

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

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

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

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

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

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

• $\{\mathrm{\neg },\vee \}$ и $\{\mathrm{\neg },\wedge \}$;
• $\{\oplus ,\wedge ,1\}$ и $\{\leftrightarrow ,\vee ,0\}$;
• $\{|\}$ и $\{\downarrow \}$;

Литература

• Шаблон:Книга
• Шаблон:Cite web
• Шаблон:Cite web
• Шаблон:Cite web
• Шаблон:Книга