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

Двойственная булева функция к булевой функции $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}}})}}

^[1]

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

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

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

Примеры

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

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

^[2]

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

f(x,y)=x\oplus y

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

^[4]

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

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

^[5]

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

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

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

^[6]

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

Введём понятие двойственной булевой формулы. Пусть $\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})$ .^[7]

Из принципа двойственности следует следующее: если верно некоторое тождество $\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}}$ — тоже верное тождество.^[8]

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

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

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

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

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

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

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

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

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

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