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

Самодвойственная функция - булева функция, двойственная сама к себе. Функцией, двойственной к функции $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))$ также является самодвойственной:
$\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)$.
S является предполным классом.

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

Литература

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