16.Принцип двойственности
Пусть f =f(x1, x2, …xn). Двойственной к ней ф-ей наз. ф-я f *=f(x1, x2, …xn).
Ф-я двойственная к себе наз. самодвойственной f* = f .
Таблица двойственных ф-й:
0*=1.
1*=0.
x*=x.
(x)*= x.
(x&y) *=xy.
(xy) *=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).
Набор меньше набора (<), если 11, 22,…,nn. Например: (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)=a0a1x1a2x2…anxn. В котором ai є {0,1}
Слогаемые aixi наз. линейными, а все остальные – нелинейными.
линейные: 0, 1, x, x=x1, .
нелинейные: &, , , , .
Функция называется линейной, если она не содержит конъюнкции переменных.
Каждая линейная ф-ция однозначно определяется своими коэфициэнтами, поэтому количество линейных ф-й - 2n+1.
т.к. суперпозиция линейных ф-ций – линейная ф-ция, то класс линейных ф-ций замкнут:
док-во сфоткаете с конспекта