Презентация: Полином Жегалкина

Полином Жегалкина

План

1. Полином Жегалкина

2. Алгоритмы построения полинома Жегалкина

1. Полином Жегалкина

Примеры функционально полных систем

• Многочленом Жегалкина называется многочлен, являющийся суммой константы 0 или 1 и различных одночленов, в которые все переменные входят не выше, чем в первой степени: при чем на каждом наборе

• Представление логической функции многочленом Жегалкина единственно

Примеры представления различных функций многочленом Жегалкина

2. Алгоритмы построения полинома Жегалкина

Алгоритм построения полинома Жегалкина по СовДНФ  

• Начало . Задана совершенная ДНФ функции f(x 1 , …, x n ).
• Шаг 1 . Заменяем каждый символ дизъюнкции на символ дизъюнкции с исключением.
• Шаг 2 . Заменяем каждую переменную с инверсией x равносильной формулой x   1.
• Шаг 3 . Раскрываем скобки.
• Шаг 4 . Вычеркиваем из формулы пары одинаковых слагаемых.
• Конец . Получен полином Жегалкина функции f(x 1 , …, x n ).

Пример

Алгоритм построения полинома Жегалкина по ДНФ  (основан на равносильности K 1 K 2 = K 1 K 2 K 1 K 2 ).

Начало . Задана произвольная ДНФ функции f(x 1 , …, x n ).

Шаг 1 . Разбиваем ДНФ на пары конъюнкций, предпочтительно ортогональных (если число конъюнкций нечетно, одна из них остается без пары).

Шаг 2 . Заменяем дизъюнкцию каждой пары конъюнкций K 1 K 2  формулой K 1 K 2 K 1 K 2  или формулой K 1 K 2 , если K 1  и K 2  ортогональны.

Шаг 3 . В полученной формуле находим очередную дизъюнкцию A 1 A 2 и заменяем ее формулой A 1 A 2 A 1 A 2 . Повторяем шаг 3 до тех пор, пока это возможно.

Шаг 4 . Заменяем каждую переменную с инверсией x равносильной формулой x1.

Шаг 5 . Раскрываем скобки.

Шаг 6 . Вычеркиваем из формулы пары одинаковых слагаемых.

Конец . Получен полином Жегалкина функции f(x 1 , …, x n ).

Пример

Алгоритм построения полинома Жегалкина по таблице истинности  (основан на методе неопределенных коэффициентов).

• Продемонстрируем идею метода на примере произвольной булевой функции двух аргументов f(x,y). Представим ее полиномом Жегалкина в форме с коэффициентами

• Заметим, что наборы подставлены в равенство в естественном порядке, и система имеет треугольный вид: в первом уравнении обратились в ноль все слагаемые, следующие за c 0 , во втором – следующие за c 1  и так далее. Значит, коэффициент c 0  можно получить из первого уравнения и подставить его в остальные. Тогда c 1  можно получить из второго уравнения, и так далее.
• В общем случае для функции  n  аргументов получается система треугольного вида из 2 n  линейных уравнений с 2 n  неизвестными – коэффициентами полинома Жегалкина.

Пример.  Найдем полином Жегалкина мажоритарной булевой функции, заданной таблицей истинности, последовательно вычисляя коэффициенты полинома и подставляя их в остальные уравнения.

Из первого уравнения следует, что c 0 =0. Из второго и третьего уравнений следует, что c 1 =0 и c 2 =0, значит, c 1 z и c 2 y тождественно равны нулю.

Из четвертого уравнения получаем c 3 =1, значит, надо вычислять значения конъюнкции c 3 yz в остальных уравнениях.

Аналогично получаем c 4 =0, c 5 =1, c 6 =1 и c 7 =0.

Найден вектор коэффициентов полинома Жегалкина мажоритарной функции π=00010110, и сам полином который,

естественно, совпадает с полученными ранее.

Вопросы

• Какая функция называется двойственной? Самодвойственной? Приведите примеры.
• Что называется функционально полной системой логических функций?
• Что такое многочлен Жегалкина? Запишите многочлен Жегалкина в общем виде для функции 3-х аргументов.