WikiSort.ru - Не сортированное

Самодвойственная функция — булева функция, двойственная сама к себе. Функцией, двойственной к функции ${\displaystyle f(x_{1},\ldots ,x_{n})}$ , называется функция ${\displaystyle f^{*}(x_{1},\ldots ,x_{n})={\overline {f}}({\overline {x}}_{1},\ldots ,{\overline {x}}_{n})}$ . Значит, функция ${\displaystyle f(x_{1},\ldots ,x_{n})}$ является самодвойственной, если ${\displaystyle {\overline {f}}({\overline {x}}_{1},\ldots ,{\overline {x}}_{n})=f(x_{1},\ldots ,x_{n})}$ . Другими словами самодвойственная функция на противоположных друг другу наборах значений аргументов принимает противоположные значения.

Множество самодвойственных функций обозначается символом S. Множество S является замкнутым классом. Действительно, если функции ${\displaystyle f(x_{1},\ldots ,x_{n}),f_{1}(x_{1},\ldots ,x_{n}),\ldots ,f_{k}(x_{1},\ldots ,x_{n})}$ являются самодвойственными, то функция ${\displaystyle g(x_{1},\ldots ,x_{n})=f(f_{1}(x_{1},\ldots ,x_{n}),\ldots ,f_{k}(x_{1},\ldots ,x_{n}))}$ также является самодвойственной:
${\displaystyle {\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 является предполным классом.

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

Литература

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