Самодвойственная функция: различия между версиями
| [непроверенная версия] | [отпатрулированная версия] |
Содержимое удалено Содержимое добавлено
Arseniqum (обсуждение | вклад) Вернул описание двойственных функций. Было удалено при предыдущей правки |
|||
Строка 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_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> также является самодвойственной: <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 является [[предполные классы|предполным классом]].
| |||