Diskretnaya_matematika_1_semestr

Двойственные функции. Принцип двойственности

Функция f*(x1,x2,…,xn)=¬f(¬x1,¬x2,…,¬xn-)двойственная функция для функции f(x1,x2,…,xn).

(x&y)*=¬(¬x&¬y)=xÙy

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

х*=¬¬(х)=х 0*=1

(¬х)*=(¬¬¬х)=(¬х) 1*=0

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

По таблице истинности f* строится следующим образом: значения функции изменяются на противоположное (0 на 1;1 на 0), столбец значений переворачивается симметрично относительно середины таблицы.

f**=(f*)*=f

Теорема двойственности.Пусть даны ф-ции f0(y1,y2,…,yk), f1(x1,x2,…x1i1),…,fk(xk1,xk2,…,xkik).

Пусть Ф(х1,х2,…,хn)-элементарная суперпозиция ф-ции f0,f1,…,fk

Ф(х1,х2,…,хn)=f0(f1(х1,х2,…,х1i1),…,fk(хk1,…,хkik)), тогда Ф*(х1,х2,…,хn)=f0*(f1*(х1,х2,…,х1i1),…,fk*(хk1,…,хkik))

Доказательство.По определению двойственной ф-ции Ф*(х1,х2,…,хn)= =¬f0(¬f1(¬х1,¬х2,…,¬х1i1),…,¬fk(¬хk1,…,¬хkik))= Ф*(х1,х2,…,хn)= ¬f0(¬¬f1(¬х1,¬х2,…,¬х1i1),…,¬¬fk(¬хk1,…,¬хkik))= ¬f0(¬f1*(х1,х2,…,х1i1),…,¬fk*(хk1,…,хkik))= f0*(z1,…,zk)= f0*(f1*(х1,х2,…,х1i1),…,fk*(хk1,…,хkik))

Из этой теоремы следует принцип двойственности, использую который можно получать новые тождества.

Принцип двойственности. Если U=C(1, 2,…, k) реализует ф-ю f, то ф-я f* реализуется ф-лой U*=C(1*, 2*,…, k*) (U*- ф-ла двойстквенная к U).

U* - двойственная U

Следствие: если функция φ реализуется формулой над множеством функций L, то двойственная к ней функция φ* реализуется формулой над этим же множеством функций.

=(x1&¬x2)Ù(x1Ù(x2&1))

*=(x1Ù¬x2)&(x1&(x2Ù0))

¬(x1&x2)=¬x1Ù¬x2

¬x1Ù¬x2=¬x1&¬x2

Содержание