Двойственные функции

• Определение. Двойственной для функции f(x1, x2, …, xn) называется функция$f^*(x_1, x_2,..., x_n)=\overline{f\left ( \bar{x_1}, \bar{x_2},... \bar{x_n} \right )}$

Пример. Построить функцию, двойственную данной:

$1.\,  f=x\vee y;$
$2. \, f=x\rightarrow y.$

Решение.

$1. f^*=\overline{\bar{x}\vee \bar{y}}=\bar{\bar{x}}\wedge\bar{\bar{y}} ;$
$2. f^*=\overline{\bar{x}\rightarrow \bar{y}}=\overline{\bar{\bar{x}} \vee  \bar{y}}=\bar{\bar{\bar{x}}}\wedge \bar{\bar{y}}=\bar{x}\wedge y.$

• Определение. Функция, совпадающая со своей двойственной, называется самодвойственной.
• Утверждение. Если функция f(x1, x2, …, xn) самодвойственна, то функция $\bar{f}  тоже самодвойственна.
• Утверждение. Чтобы функция была самодвойственной необходимо и достаточно, чтобы на всяких двух противоположных наборах она принимала разные значения.
• Противоположными называются те наборы, которые в сумме дают двоичный код числа (2ⁿ-1).

Пример. Выяснить являются ли функции самодвойственными:

$1.\,  f=\left ( \bar{x} \approx y\right )\rightarrow \bar{z};$
$2\, f=01110010.$

Решение.
1. Строим таблицу истинности для данной функции  $f=\left ( \bar{x} \approx y\right )\rightarrow \bar{z}$ (табл. 1)

Так как наборы (0, 0, 0) и (1, 1, 1) являются противоположными, а f(0, 0, 0) = f(1, 1, 1), то данная функция не является самодвойственной.

2. Строим таблицу значений для функции f = 01110001 (табл. 2).

Перечислим пары противоположных наборов: (0, 7), (1, 6), (2, 5), (3, 4). Легко убедиться по таблице, что на всяких двух противоположных наборах функция принимает разные значения. Следовательно, функция является самодвойственной.

• Теорема. Класс $S =\left \{ f \mid  f = f* \right \}$  самодвойственных функций замкнут относительно суперпозиций.