Двойственные функции. Теорема о суперпозиции двойственных функций. Принцип двойственности

Определение: Двойственной функцией для f(x1, x1,…,xn) называется функция f* = ¬f(¬x1, ¬x2,…,¬xn)

Замечание: (f¬(x1, x2,…,xn))* = (¬f(¬x1, ¬x2,…,¬xn))* = ¬f(¬¬x1, ¬¬x2,…,¬¬xn) = f(x1, x2,…,xn) ⇒ (f*) = f.

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

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

(f(g1,…,gm))* = ¬f(g1(¬x1,1, ¬x1,2,…,¬x1,n1),…,gm(¬xm,1, ¬xm2,1,…,¬xm,nm)) =
=¬f(¬¬g1(¬x1,1,¬x2,1,…,¬x1,n1),…,¬¬gm(¬xm,1,¬xm,2,…,¬xm,nm))=¬f(¬g1*,…,¬gm*)=f*(g1*,…,gm*)

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

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


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





Статистика

Рейтинг@Mail.ru