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

Самодвойственная функция — булева функция, двойственная сама к себе. Функцией, двойственной к функции ${\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)}$. В свою очередь конъюнкция, дизъюнкция и константы самодвойственными не являются.