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

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

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

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

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

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

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

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

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

Доказательство: пусть f(x1, x2,…,xn) – несамодвойственна. Тогда ∃ набор (a1, a2,…,an) из 0 и 1 для которого f(a1, a2,…,an) = f(¬a1,¬a2,…,¬an). Построим функцию h(x), заменив единицы в f(a1, a2,…,an) на x, а нули на ¬x. Т.к. ¬x = x0 , x =x1 то h(x) = f(xa1, xa2,…,xan). Заметим, что 0ai =¬ai, 1ai = ai.
Тогда h(1)= f(1a1, 1a2,…,1an) = f(a1, a2,…,an) = f(¬a1, ¬a2,…,¬an) = f(0a1, 0a2,…,0an) = h(0) ⇒ (0) =h(1) ⇒ h(x) =const


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





Статистика

Рейтинг@Mail.ru