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

Самодвойственная функция — булева функция, двойственная сама к себе. Более развёрнуто, булева функция $f(x_{1},\ldots ,x_{n})$ называется самодвойственной, если для любых значений $x_{1},\ldots ,x_{n}$ верно

${\overline {f({\overline {x}}_{1},\ldots ,{\overline {x}}_{n})}}=f(x_{1},\ldots ,x_{n})$

Другими словами самодвойственная функция на противоположных друг другу наборах значений аргументов принимает противоположные значения. Примеры самодвойственных функций: $x$, ${\overline {x}}$, $x\land y\lor x\land z\lor y\land z$, $x\oplus y\oplus z$. Самодвойственных функций с двумя существенными переменными нет.

Каждую самодвойственную функцию $f(x_{1},\ldots ,x_{n})$ арности $n$ можно представить в виде

$f(x_{1},\ldots ,x_{n})=x_{1}\land g(x_{2},\ldots ,x_{n})\lor {\overline {x_{1}}}\land g^{*}(x_{2},\ldots ,x_{n})$,

для некоторой $g$ арности $n-1$, причём $g$ определяется однозначно. Обратно, для любой функции $g$ арности $n-1$ функция $f$, определяемая указанным выше соотношением, самодвойственна. Самодвойственных функций арности $0$ нет. Таким образом, между любыми булевыми функциями арности $n-1$ и самодвойственными функциями арности $n$ есть взаимо-однозначное соответствие. Поэтому, количество самодвойственных функций арности $n>0$ равно количеству всех булевых функций арности $n-1$, которое в свою очередь равно $2^{2^{n-1}}$.

Аналогичное представление получится, если выносить не переменную $x_{1}$, а любую другую.

Класс самодвойственных функций

Решётка замкнутых классов самодвойственных функций

Класс всех самодвойственных функций является замкнутым классом, предполным в $P_{2}$. Класс самодвойственных функций обозначается символом $S$ или $D_{3}$ (обозначение Поста). Базисами класса самодвойственных функций являются, например: $\{x\land {\overline {y}}\lor y\land {\overline {z}}\lor {\overline {y}}\land {\overline {z}}\}$, $\{{\overline {x\land y\lor y\land z\lor y\land z}}\}$, $\{{\overline {x}},{x\land y\lor y\land z\lor y\land z}\}$. Порядок класса самодвойственных функций равен $3$.

Самодвойственные функции, сохраняющие $0$, будут сохранять и $1$; обратное тоже верно. Таким образом, $S\cap T_{0}=S\cap T_{1}=S\cap T$ (где $T=T_{0}\cap T_{1}$). Монотонная самодвойственная функция всегда сохраняет константы, при этом есть немонотонные сохраняющие константы самодвойственные функции ($S\cap M\subset S\cap T$).

Даже если не требовать в определении замкнутого класса, чтобы он обязательно содержал функцию $x$, любой замкнутый класс самодвойственных функций всё равно будет её содержать. Любой замкнутый класс самодвойственных функций можно расширить до предполного в $S$. Предполными в $S$ являются следующие два класса: $S\cap L$ (класс самодвойственных линейных функций) и $S\cap T$ (класс самодвойственных функций, сохраняющих константы). Верен аналог малой теоремы Поста: система самодвойственных функций полна в $S$ тогда и только тогда, когда она содержит нелинейную и не сохраняющую константы функцию.

Литература

• Яблонский С. В. Введение в дискретную математику. — М.: Наука, 1986. — 384 с.
• Яблонский С. В., Гаврилов Г. П., Кудрявцев В. Б. Функции алгебры логики и классы Поста. — М.: Наука, 1966. — 120 с.
• Марченков С.С. Замкнутые классы булевых функций. — М.: Физматлит. - 2000