Самодвойственная функция: различия между версиями
| [отпатрулированная версия] | [отпатрулированная версия] |
Содержимое удалено Содержимое добавлено
Нет описания правки |
Koliz (обсуждение | вклад) мНет описания правки |
||
Строка 1:
'''Самодвойственная функция''' - [[булева функция]], двойственная сама к себе. Функцией, двойственной к функции <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>. Другими словами самодвойственная функция на противоположных друг другу наборах значений аргументов принимает противоположные значения.
Множество самодвойственных функций обозначается символом S. Множество S является [[замкнутые классы булевых функций|замкнутым классом]]. Действительно, если функции <math>f(x_1,\ldots,x_k),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> также является самодвойственной: <br><math>\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)</math>.<br> S является [[предполные классы|предполным классом]].
Примеры самодвойственных функций: <math>x, \overline x, (x\wedge y)\vee(x\wedge z)\vee(y\wedge z)</math>. В свою очередь [[конъюнкция]], [[дизъюнкция]] и константы самодвойственными не являются.
| |||