Определение: Двойственной функцией для f(x₁, x₁,…,x_n) называется функция f* = ¬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*) = f.

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

Доказательство:

(f(g₁,…,g_m))* = ¬f(g₁(¬x_1,1, ¬x_1,2,…,¬x_1,n1),…,g_m(¬x_m,1, ¬x_m2,1,…,¬x_m,nm)) =
=¬f(¬¬g₁(¬x_1,1,¬x_2,1,…,¬x_1,n1),…,¬¬g_m(¬x_m,1,¬x_m,2,…,¬x_m,nm))=¬f(¬g₁*,…,¬g_m*)=f*(g₁*,…,g_m*)

Принцип двойственности.

Если функция f задана формулой, построенной с помощью &,∨,¬,0,1 и переменных, то по теореме о суперпозиции двойственных функций и ввиду того, что для функций x&y, ¬x, ,1,0 двойственными являются x∨y ,x ,0,1 соответственно, то f* получается из f заменой & на ∨, 0 на 1 и т.д. при сохранении исходной расстановки скобок.

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