Воскресенье, 05.01.2025, 23:15
Мультимедийное пособие по дискретной математике
|
Меню сайта
Лекции
Лекции
|
«Многочлены Жегалкина»Теорема. Любая булева функция представима в виде многочлена Жегалкина (МЖ). Продолжение темы «Многочлены Жегалкина» Доказательство 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 является функционально замкнутым. Доказательство следует из принципа двойственности. У самодвойственной функции на противоположных наборах противоположны значения. Теорема. Класс 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(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) |
Поиск
Счеткич визитов
Друзья сайта
|