Класс S. Теорема о замкнутости класса 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)$. В свою очередь конъюнкция, дизъюнкция и константы самодвойственными не являются.