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

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Самодвойственная функция — булева функция, двойственная сама к себе. Функцией, двойственной к функции <math>f(x_1,\ldots,x_n)</math>, называется функция <math>f^*(x_1,\ldots,x_n)=\overline f(\overline x_1,\ldots,\overline x_n)</math>. Значит, функция <math>f(x_1,\ldots,x_n)</math> является самодвойственной, если <math>\overline f(\overline x_1,\ldots,\overline x_n)=f(x_1,\ldots,x_n)</math>. Другими словами самодвойственная функция на противоположных друг другу наборах значений аргументов принимает противоположные значения.

Множество самодвойственных функций обозначается символом <math>S</math>. Множество <math>S</math> является замкнутым классом. Действительно, если функции <math>f(x_1,\ldots,x_n),f_1(x_1,\ldots,x_n),\ldots,f_k(x_1,\ldots,x_n)</math> являются самодвойственными, то функция <math>g(x_1,\ldots,x_n)=f(f_1(x_1,\ldots,x_n),\ldots,f_k(x_1,\ldots,x_n))</math> также является самодвойственной:

<math display="block">\begin{alignat}{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{alignat}</math>

<math>S</math> является предполным классом.

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

Литература

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