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


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

Самодвойственная функция - булева функция, двойственная сама к себе. Функцией, двойственной к функции 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

Wikimedia Foundation. 2010.


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.