Определение: Функция, совпадающая со своей двойственной функцией, называется самодвойственной.

Замечание: Если функция f(x₁, x₂,…,x_n) самодвойственна, то функция ¬f также самодвойственна, то есть
(⌈f(x₁, x₂,…,x_n))*=⌈(⌈f(⌈x₁,…, ⌈x_n))= [функция самодвойственна f=f*] = ⌈f(x₁, …, x_n).

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

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

Определение: Наборы a=(a₁, a₂,…,a_n), a*=(¬a₁, ¬a₂,…,¬a_n) из 0 и 1 называется противоположными.

Следствие: Чтобы функция была самодвойственной необходимо и достаточно, чтобы на всяких двух противоположных наборах она принимала разные значения.

Доказательство: f(x₁, x₂,…,x_n) самодвойственна ⇔ f(x₁, x₂,…,x_n) = f(x₁, x₂,…,x_n) ⇔ ¬f(¬x₁, ¬x₂,…,¬x_n) = f(x₁, x₂,…,x_n) ⇔ f(x₁,…x_n) = ⌈⌈f(⌈x₁,…,⌈x_n) ⇔ ⌈f(x₁,…x_n)=f(⌈x₁,…,⌈x_n) ⇔ f(¬x₁, ¬x₂,…,¬x_n) ≠ f(x₁, x₂,…,x_n) ⇔ функция на двух противоположных наборах принимает различные значения.

Лемма (о несамодвойственной функции): Подстановкой функций x и ¬x в несомодвойственную функцию можно получить одну из констант.

Доказательство: пусть f(x₁, x₂,…,x_n) – несамодвойственна. Тогда ∃ набор (a₁, a₂,…,a_n) из 0 и 1 для которого f(a₁, a₂,…,a_n) = f(¬a₁,¬a₂,…,¬a_n). Построим функцию h(x), заменив единицы в f(a₁, a₂,…,a_n) на x, а нули на ¬x. Т.к. ¬x = x₀ , x =x₁ то h(x) = f(x^a1, x^a2,…,x^an). Заметим, что 0^ai =¬a_i, 1^ai = a_i.
Тогда h(1)= f(1^a1, 1^a2,…,1^an) = f(a₁, a₂,…,a_n) = f(¬a₁, ¬a₂,…,¬a_n) = f(0^a1, 0^a2,…,0^an) = h(0) ⇒ (0) =h(1) ⇒ h(x) =const

Комментарии запрещены.