Самодвойственная функция

Самодвойственная функция — булева функция, двойственная сама к себе. Функцией, двойственной к функции $f(x_{1},\ldots ,x_{n})$, называется функция $f^{*}(x_{1},\ldots ,x_{n})={\overline {f}}({\overline {x}}_{1},\ldots ,{\overline {x}}_{n})$. Значит, функция $f(x_{1},\ldots ,x_{n})$ является самодвойственной, если ${\overline {f}}({\overline {x}}_{1},\ldots ,{\overline {x}}_{n})=f(x_{1},\ldots ,x_{n})$. Другими словами самодвойственная функция на противоположных друг другу наборах значений аргументов принимает противоположные значения.

Множество самодвойственных функций обозначается символом $S$. Множество $S$ является замкнутым классом. Действительно, если функции $f(x_{1},\ldots ,x_{n}),f_{1}(x_{1},\ldots ,x_{n}),\ldots ,f_{k}(x_{1},\ldots ,x_{n})$ являются самодвойственными, то функция $g(x_{1},\ldots ,x_{n})=f(f_{1}(x_{1},\ldots ,x_{n}),\ldots ,f_{k}(x_{1},\ldots ,x_{n}))$ также является самодвойственной:

$${\begin{alignedat}{2}{\overline {g}}({\overline {x}}_{1},\ldots ,{\overline {x}}_{n})&={\overline {f}}(f_{1}({\overline {x}}_{1},\ldots ,{\overline {x}}_{n}),\ldots ,f_{k}({\overline {x}}_{1},\ldots ,{\overline {x}}_{n}))\\&={\overline {f}}({\overline {f}}_{1}(x_{1},\ldots ,x_{n}),\ldots ,{\overline {f}}_{k}(x_{1},\ldots ,x_{n}))\\&=f(f_{1}(x_{1},\ldots ,x_{n}),\ldots ,f_{k}(x_{1},\ldots ,x_{n}))\\&=g(x_{1},\ldots ,x_{n})\end{alignedat}}$$

$S$ является предполным классом.

Примеры самодвойственных функций: $x,{\overline {x}},(x\wedge y)\vee (x\wedge z)\vee (y\wedge z)$. В свою очередь конъюнкция, дизъюнкция и константы самодвойственными не являются.

Литература

• Яблонский С.В. Введение в дискретную математику. — М.: Наука. — 1986
• Марченков С.С. Замкнутые классы булевых функций. — М.: Физматлит. - 2000