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

Самодвойственная функция — булева функция, двойственная сама к себе. Более развёрнуто, булева функция ${\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\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}}=x(y\downarrow z)\lor {\overline {x}}(y\,|\,z)}$ — отрицание функции голосования.^[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]

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

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

Из несамодвойственной функции можно получить несамодвойственную функцию от двух переменных ${\displaystyle f}$ такую, что ${\displaystyle f(1,0)=f(0,1)}$.^[7]

Обобщения

Функция k-значной логики ${\displaystyle f:E_{k}^{n}\to E_{k}}$ называется самодвойственной относительно перестановки ${\displaystyle \sigma$ :\in S_{k}} , если для любых значений ${\displaystyle x_{1},\ldots ,x_{n}\in E_{k}}$ выполнено

${\displaystyle f(\sigma (x_{1}),\ldots ,\sigma (x_{n}))=f(x_{1},\ldots ,x_{n})}$.

Обычная самодвойственность булевых функций соответствует самодвойственности относительности перестановки ${\displaystyle {\overline {x}}}$. Класс всех самодвойственных относительно перестановки ${\displaystyle \sigma }$ функций является предполным в ${\displaystyle P_{k}}$ тогда и только тогда, когда перестановка ${\displaystyle \sigma }$ разлагается в произведение независимых циклов одной и той же простой длины.^[8]