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

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

$${\displaystyle {\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}}}$$

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

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

Литература

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