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

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

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

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

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

${\displaystyle 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})}$,

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

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

Класс всех самодвойственных функций является замкнутым классом, предполным в ${\displaystyle P_{2}}$. Класс самодвойственных функций обозначается символом ${\displaystyle S}$^[4] или ${\displaystyle D_{3}}$^[1] (обозначение Поста). Базисами класса самодвойственных функций являются, например:

• ${\displaystyle x{\overline {y}}\lor x{\overline {z}}\lor {\overline {y}}{\overline {z}}=x(y\,|\,z)\lor {\overline {x}}(y\downarrow z)}$;
• ${\displaystyle {\overline {x}},{xy\lor xz\lor yz}}$ — отрицание и функция голосования;
• ${\displaystyle {\overline {xy\lor xz\lor yz}}}$ — отрицание функции голосования.^[5]

Порядок класса самодвойственных функций равен ${\displaystyle 3}$^[2].

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

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

Лемма о несамодвойственной функции:

Из несамодвойственной функции и отрицание при помощи суперпозиции можно получить константу.^[2]

Данная лемма используется в одном из доказательств малой теоремы Поста.

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