Класс $S$. Теорема о замкнyтости класса $S$

Самодвойственная функция - булева функция, двойственная сама к себе.

Функция называется самодвойственной, если на противоположных наборах она принимает противоположные значения, то есть для самодвойственной функции $~f(x_1, x_2,\dots,x_n)$ выполняется тождество $f (x_1,x_2,\dots,x_n)=\overline { f(\bar { x } _1,\bar { x } _2,\dots,\bar { x } _n) } $. Обозначают, что $f \in S$.

Функцией, двойственной к функции $f(x_1,\ldots,x_n)$, называется функция $f^*(x_1,\ldots,x_n)=\overline f(\overline x_1,\ldots,\overline x_n)$. Значит, функция $f(x_1,\ldots,x_n)$ является самодвойственной, если $\overline f(\overline x_1,\ldots,\overline x_n)=f(x_1,\ldots,x_n)$. Другими словами самодвойственная функция на противоположных друг другу наборах значений аргументов принимает противоположные значения.

Теорема: Класс самодвойственных функций замкнут относительно суперпозиции.

Доказательство: Пусть функции $f, g_1, g_2,…,g_m$ самодвойственны. Тогда $f^*=f, g_i^* = g_i~i=1 ... m$. Суперпозиция $h=f(g_1, g_2, ..., g_m)$ самодвойственна, ибо $h^* = (f(g_1, g_2, ..., g_m))^* =$\ { по теореме о суперпозиции двойственной ф-ции\ } $ = hf^*(g_1*, g_2*, ...,g_ { m } ^*) = h$

Построение двойственных функций.

Введём стандартное обозначение. Булеву функцию, двойственную $f$ будем обозначать как $f^*$.

Пусть ф-ция $f$ задана таблицей со стандартным упорядочением строк. Покажем, как по этой таблице для $f$ можно построить так же упорядоченную таблицу для $f^*$.

Алгоритм прост.

1. Развернуть столбец значений $f_n$ вокруг центральной его точки на $180^\circ$ { последнее значение в столбце станет 1-м, предпоследнее – 2-м и т.д. } ;
2. Выполнить поразрядное отрицание значений развёрнутого столбца { т.е. заменить в нём нули на единицы, а единицы на нули } ;
3. Полученный в результате указанных выше действий столбец записать в стандартно упорядоченную таблицу как столбец значений функции $f^*$.

Множество самодвойственных функций обозначается символом $S$. Множество $S$ является замкнутым классом. Действительно, если функции $f(x_1,\ldots,x_n),f_1(x_1,\ldots,x_n),\ldots,f_k(x_1,\ldots,x_n)$ являются самодвойственными, то функция $g(x_1,\ldots,x_n)=f(f_1(x_1,\ldots,x_n),\ldots,f_k(x_1,\ldots,x_n))$ также является самодвойственной: $\overline g(\overline x_1,\ldots,\overline x_n) = \overline f(f_1(\overline x_1,\ldots,\overline x_n),\ldots,f_k(\overline x_1,\ldots,\overline x_n)) = \overline f(\overline f_1(x_1,\ldots,x_n),\ldots,\overline f_k(x_1,\ldots,x_n)) = $ $ = f(f_1(x_1,\ldots,x_n),\ldots,f_k(x_1,\ldots,x_n)) = g(x_1,\ldots,x_n)$.

$S$ является предполным классом.

Примеры самодвойственных функций: $x, \overline x, (x\wedge y)\vee(x\wedge z)\vee(y\wedge z)$. В свою очередь конъюнкция, дизъюнкция и константы самодвойственными не являются.