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

Пусть f =f(x1, x2, …xn). Двойственной к ней ф-ей наз. ф-я f *=f(x1,  x2, …xn).

Ф-я двойственная к себе наз. самодвойственной f* = f .

Таблица двойственных ф-й:

0*=1.

1*=0.

x*=x.

(x)*= x.

(x&y) *=xy.

(xy) *=x&y.

(f *)*= f.

Принцип двойственности в бул алгебре: Если в формуле (должна быть записана с использование кон-кции или диз-кции, т. е. КНФ или ДНФ) реализующей ф -ю f все знаки операций заменить на двойственные к ним(см выше в таблице), то получим формулу реализующую двойственную ф-ю. Тогда таблица истинности при переходе к двойственной ф-и преобразуется следующим образом: столбец значений "переворачивается" отностиельно середины таблицы(это соответствует инвертированию переменных), в перевернутом столбце значений инвертировать значения ф-и, это соответствует инвертированию ф-и.

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

Если U=W и в этих ф-лах подформулы заменить на двойственные, то результатом будут эквивалентные ф-лы.

Если U=C(,&,), то U* =C(,&,).

При переходе от f в f* значение f изменяется на противоположный и столбец “переварачивается “ относительно середины таблицы .

х1 х2 х3 f f*

0 0 0 1 1

0 0 1 0 1

0 1 0 1 0

0 1 1 1 1

1 0 0 0 1

1 0 1 1 0

1 1 0 1 1

1 1 1 0 0

Теорема: класс самодвойственных ф-й явл замкнутым.

Т* = {f| f(х1,х2...хп)=f*(х1,х2...хп)}

пусть f0, f1, f2 …. fk e T*, сформируем изх суперпозицию: f(f1, f2, …fn)-элементарная суперпозиция ф-й f0, f1,… fl ,покажем что она тоже принадлежит этому классу:

f0*(f1*, f2*, …fn*)= f0(f1,f2,…, fn)=

f0*(f1*, f2*,....fn*) = f0*(f1, f2, …..fn) = f0(f1,f2,...fn) => класс замкнутый

17.Класс монотонных ф-ций:

Тм – класс монотонных ф-ций.

Пусть =(1,…,n) и =(1,…, n).

Набор  меньше набора  (<), если 11, 22,…,nn. Например: (1001)<(1011).

< – рефликсивно, транзитивно, антисиметрично, т.е. это отношение частичного порядка, но в общем случае не линейного порядка. Ф-ция п-переменных f наз. монотонной, если для любых двух двоичных наборов =(1,…,n) и =(1,…, n) таких что: < следует f()f().

входят: 0, 1, x, &, .

невходят: x, , , .

Для проверки ф-ции на монотонность необходимо проверить, что f()f() для всевозможных пар сравнимых наборов.

Теорема: Класс мон. ф-ций замкнут: [M]=M.

Рассмотрим f0, f1, f2 ….fn e Tm покажем что: f0(f1, f2....fn) e Tm

Рассмотрим два набора <=:

f0(f1(a), f2(a)....fn(a)) <= f0(f1(b), f2(b)....fn(b))

f1(a) <= f1(b)

f2(a) <= f2(b)

f3(a) <= f3(b)

…...

fn(a) <= fn(b)

т. к. ф0 не выходит за приделы Тм следватльно, Тм — замкнутый класс.

18. Класс L

L – класс ленейных ф-ций.

Ф-ция f(x1,…xn) наз. линейной, если ее представление в виде полинома Жегалкина имеет вид:

f(x1,…xn)=a0a1x1a2x2…anxn. В котором ai є {0,1}

Слогаемые aixi наз. линейными, а все остальные – нелинейными.

линейные: 0, 1, x, x=x1, .

нелинейные: &, , , , .

Функция называется линейной, если она не содержит конъюнкции переменных.

Каждая линейная ф-ция однозначно определяется своими коэфициэнтами, поэтому количество линейных ф-й - 2^n+1.

т.к. суперпозиция линейных ф-ций – линейная ф-ция, то класс линейных ф-ций замкнут:

док-во сфоткаете с конспекта