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

Самодвойственная функция — булева функция, двойственная сама к себе. Более развёрнуто, булева функция $f(x_1,\dots ,x_n)$ называется самодвойственной, если для любых значений $x_1,\dots ,x_n$ верно

$\overline{f({\stackrel{‾}{x}}_1,\dots ,{\stackrel{‾}{x}}_n)}=f(x_1,\dots ,x_n)$

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

Каждую самодвойственную функцию $f(x_1,\dots ,x_n)$ арности $n$ можно представить в виде

$f(x_1,\dots ,x_n)=x_1\wedge g(x_2,\dots ,x_n)\vee \overline{x_1}\wedge g^{\ast }(x_2,\dots ,x_n)$,

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

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

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

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

Класс всех самодвойственных функций является замкнутым классом, предполным в $P_2$. Класс самодвойственных функций обозначается символом $S$Шаблон:Sfn или $D_3$Шаблон:Sfn (обозначение Поста). Базисами класса самодвойственных функций являются, например:

• $x\bar{y}\vee x\bar{z}\vee \bar{y}\bar{z}=x(y|z)\vee \bar{x}(y\downarrow z)$;
• $\bar{x},xy\vee xz\vee yz$ — отрицание и функция голосования;
• $\overline{xy\vee xz\vee yz}=x(y\downarrow z)\vee \bar{x}(y|z)$ — отрицание функции голосования.Шаблон:Sfn

Порядок класса самодвойственных функций равен $3$Шаблон:Sfn.

Самодвойственные функции, сохраняющие $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$ (класс самодвойственных функций, сохраняющих константы)Шаблон:Sfn. Верен аналог малой теоремы Поста: система самодвойственных функций полна в $S$ тогда и только тогда, когда она содержит нелинейную и не сохраняющую константы функцию.

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

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

Из несамодвойственной функции и отрицание при помощи суперпозиции можно получить константу.Шаблон:Sfn

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

Есть также более общее свойство, используемое в доказательствах различных свойств классов в $P_2$:

Из несамодвойственной функции можно получить несамодвойственную функцию от двух переменных $f$ такую, что $f(1,0)=f(0,1)$.Шаблон:Sfn

Литература

• Шаблон:Книга
• Шаблон:Книга
• Марченков С.С. Замкнутые классы булевых функций. — М.: Физматлит. - 2000