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

Самодвойственная функция — булева функция, двойственная сама к себе. Более развёрнуто, булева функция ${\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]

Примечания

1. Яблонский, Гаврилов, Кудрявцев, 1966, с. 22.
2. Яблонский, Гаврилов, Кудрявцев, 1966, с. 25.
3. Яблонский, Гаврилов, Кудрявцев, 1966, с. 23.
4. Яблонский, 1986, с. 34.
5. Яблонский, Гаврилов, Кудрявцев, 1966, с. 24.
6. Яблонский, Гаврилов, Кудрявцев, 1966, с. 112.
7. Яблонский, Гаврилов, Кудрявцев, 1966, с. 41.

Литература

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