Лекции по Дискретной математике - Лекция 8. Продолжение темы «Многочлены Жегалкина»

Теорема.
Любая булева функция представима в виде многочлена Жегалкина (МЖ).
Продолжение темы «Многочлены Жегалкина»
Доказательство
1. Существование
F = ДНФ = F{&,V, NOT}

X V Y = XY+X+Y
NOT(X) = X+1

Из этого следует, что функция представима в виде МЖ.

2. Единственность
Сосчитаем МЖ
ЭК без отрицания 2n – 1 + 1

Всего разных многочленов Жегалкина 2N – 1, где N = 2n
Это число совпадает с числом разных булевых функций, отличных от нуля.
Отсюда следует, что любой булевой функции соответствует единственный многочлен Жегалкина. Теорема доказана полностью.

Классы функций. Замкнутые и незамкнутые классы. Получение констант и элементарных булевых функций из заданной системы функций
Определение. Функция называется линейной, если ее многочлен Жегалкина не содержит ни одной конъюнкции переменных.

Замкнутые классы функций.

Определение.
Пусть дан класс функций B (т.е. конечное или бесконечное множество функций),объединенных по общему признаку. Замыканием этого класса (обозначение – [B]) будем называть множество всех суперпозиций функций из класса B.
Класс B будем называть замкнутым, если его замыкание совпадает с ним самим.

B = [B]

Теорема 1
Класс всех линейных функций замкнут.
Доказательство.
Пусть L – класс линейных функций (так и будем обозначать в дальнейшем).
L = {a0+a1x1+a2x2+…+anxn}
Подставим вместо переменной x в одну из функций функцию y такого же вида.
Получим
L = [L].

Утверждение (теорема 2)
Необходимое условие линейности.
Если функция линейна и не равна некоторой постоянной, то на половине своих наборов она равна 1.
Если в векторе значений функции число 0 и 1 различно, то функция обязательно нелинейна, а если число нулей совпадает с числом единиц, то эта функция может быть линейной, а может быть и нелинейной. В таком случае, чтобы это проверить, нужно выписать для нее многочлен Жегалкина.

Функция называется самодвойственной, если двойственная к ней функция является самой этой функцией. F* = F.

S – класс всех самодвойственных функций.
Класс S является функционально замкнутым.
Доказательство следует из принципа двойственности.
У самодвойственной функции на противоположных наборах противоположны значения.

Функция называется монотонной, если из условия следует, что f()f().
Теорема.
Класс M монотонных функций замкнут.
Свойство.
У монотонных функций сокращенная ДНФ не содержит отрицаний переменных, то есть все простые импликанты не содержат отрицаний.

Другие замкнутые классы
T0 – константа 0 (класс функций, обращающихся на нулевом векторе в 0).
Т1 – константа 1 (класс функций, обращающихся на единичном векторе в 1)

Теорема
Классы Т0 и Т1 функционально замкнуты.

Лемма о несамодвойственной функции.
Если функция несамодвойственна, то путем подстановки вместо аргументов переменной x или not(x) можно получить константу.

011 – нарушена самодвойственность

f(not(x),x,x) = const = 1 при любом x.
001 – нарушена самодвойственность
Если 0, то х с отрицанием, если 1, то без отрицания.

Доказательство _ _ _ _ _ _ _ _
F  S   : F*()  F()  F*() = F() F() = F()  F() = F()

(x) = {x1, x22, … xnn}
(0) = {0, 02, … 0n}

Путем подстановки получаем, что (x) = const.

Лемма о немонотонной функции
Путем подстановки вместо аргументов-констант и переменной х можно получить not(x).

000 
F(000) = 1 F(001) = 0
F(00X) = NOT(X)
F(100) = 1
F(110) = 0
100 < 110
F(1,x,0) = NOT(X)

Лемма о нелинейной функции
Если F(X) нелинейна, то из нее путем подстановки вместо аргументов-констант переменных (x, y, not x, not y) иожно получить: конъюнкцию этих переменных, дизъюнкцию этих переменных, отрицание конъюнкции, отрицание дизъюнкции.

F = 1 + x1+x3+x1x3+x1x2x3 = x1x3(1+x2) +x3+x1+1
F(x1,0,x3) = x1x3+x3+1
___
F(x0y) = (xy)