Лекция 08. Продолжение темы «Многочлены Жегалкина»
Теорема.
Любая булева функция представима в виде многочлена Жегалкина (МЖ).
Доказательство
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 является функционально замкнутым.
Доказательство следует из принципа двойственности.
У самодвойственной функции на противоположных наборах противоположны значения.
Функция называется монотонной, если из условия a £ b следует, что f(a) £ f(b).
Теорема.
Класс 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 Þ $a : F*(a) ¹ F(a) Þ F*(a) = F(a)Þ F(a) = F(a) Þ F(a) = F(a)
F(x) = {x1a, x2a2, … xnan}
F(0) = {0a, 0a2, … 0an}
Путем подстановки получаем, что f(x) = const.
Лемма о немонотонной функции
Путем подстановки вместо аргументов-констант и переменной х можно получить Not(X).
000 £ 001
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)
| < Предыдущая | Следующая > |
|---|
