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

Самодвойственная функция — булева функция, двойственная сама к себе. Функцией, двойственной к функции $\text{[math]}$ $\text{[math]}$ $f(x_{1},\ldots ,x_{n})$ $f(x_{1},\ldots ,x_{n})$ , называется функция $\text{[math]}$ $\text{[math]}$ $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})$ . Значит, функция $\text{[math]}$ $\text{[math]}$ $f(x_{1},\ldots ,x_{n})$ $f(x_{1},\ldots ,x_{n})$ является самодвойственной, если $\text{[math]}$ $\text{[math]}$ ${\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})$ . Другими словами самодвойственная функция на противоположных друг другу наборах значений аргументов принимает противоположные значения.

Множество самодвойственных функций обозначается символом $\text{[math]}$ $\text{[math]}$ $S$ $S$ . Множество $\text{[math]}$ $\text{[math]}$ $S$ $S$ является замкнутым классом. Действительно, если функции $\text{[math]}$ $\text{[math]}$ $f(x_{1},\ldots ,x_{n}),f_{1}(x_{1},\ldots ,x_{n}),\ldots ,f_{k}(x_{1},\ldots ,x_{n})$ $f(x_{1},\ldots ,x_{n}),f_{1}(x_{1},\ldots ,x_{n}),\ldots ,f_{k}(x_{1},\ldots ,x_{n})$ являются самодвойственными, то функция $\text{[math]}$ $\text{[math]}$ $g(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})=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}}

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

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

ЛитератураПравить

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