Алгоритмы построения полинома Жегалкина
Рассмотрим алгоритмы построения полинома Жегалкина булевой функции, заданной различными способами, а именно: совершенной ДНФ, произвольной ДНФ, формулой и таблицей истинности.
Алгоритм построения полинома Жегалкина по СовДНФ (основан на доказательстве теоремы о существовании полинома Жегалкина).
Начало. Задана совершенная ДНФ функции f(x1, …, xn).
Шаг 1. Заменяем каждый символ дизъюнкции на символ дизъюнкции с исключением.
Шаг 2. Заменяем каждую переменную с инверсией x равносильной формулой x 
1.
Шаг 3. Раскрываем скобки.
Шаг 4. Вычеркиваем из формулы пары одинаковых слагаемых.
Конец. Получен полином Жегалкина функции f(x1, …, xn).
Пример. Найдем полином Жегалкина мажоритарной булевой функции по ее совершенной ДНФ.
Алгоритм построения полинома Жегалкина по ДНФ (основан на равносильности K1 
K2= K1 K2 K1K2).
Начало. Задана произвольная ДНФ функции f(x1, …, xn).
Шаг 1. Разбиваем ДНФ на пары конъюнкций, предпочтительно ортогональных (если число конъюнкций нечетно, одна из них остается без пары).
Шаг 2. Заменяем дизъюнкцию каждой пары конъюнкций K1 K2 формулой K1 K2 K1K2 или формулой K1 K2, если K1 и K2 ортогональны.
Шаг 3. В полученной формуле находим очередную дизъюнкцию A1 A2и заменяем ее формулой A1 A2 A1A2. Повторяем шаг 3 до тех пор, пока это возможно.
Шаг 4. Заменяем каждую переменную с инверсией x равносильной формулой x 1.
Шаг 5. Раскрываем скобки.
Шаг 6. Вычеркиваем из формулы пары одинаковых слагаемых.
Конец. Получен полином Жегалкина функции f(x1, …, xn).
Пример. Найдем полином Жегалкина мажоритарной функции по ДНФ.
Отметим, что полиномы мажоритарной функции, полученные в двух последних примерах, совпадают с точностью до порядка конъюнкций, и это естественно (по теореме о единственности полинома Жегалкина).
Алгоритмы построения полинома Жегалкина по формуле.
Способ 1 основан на предварительном преобразовании формулы в ДНФ (любым известным нам способом). Затем ДНФ преобразуется в полином Жегалкина по только что изученному алгоритму.
Примеры. Получим полиномы Жегалкина двух элементарных булевых функций: импликации и эквивалентности, представив их предварительно кратчайшими ДНФ.
Аналогично можно получить полиномы Жегалкина всех элементарных булевых функций (оставим читателю их вывод).
Константы 0 и 1, тождественная функция, а также конъюнкция ab и дизъюнкция с исключением a b уже являются полиномами Жегалкина. Полином Жегалкина инверсии a =1 a.
Заметим, что некоторые из приведенных полиномов могут быть получены гораздо проще, в частности,
Способ 2. Если булева функций задана произвольной формулой, то ее полином Жегалкина можно получить подстановкой в формулу вместо элементарных булевых функций их полиномов.
Пример. Найдем полином Жегалкина мажоритарной функции, заданной формулой:
F=x 
y 
z /(x 
y)= ((x y) z) /(x y)=
[ подставим в формулу полином Жегалкина штриха Шеффера 1 ab при a=(x y) z, b=x y ]
= 1 ((x y) z) (x y)=
[ подставим полиномы Жегалкина обратной импликации 1 b ab при a=x y, b=z и импликации 1 a ab при a=x, b=y ]
= 1 (1 z (x y)z) (1 x xy)=
[ подставим полином Жегалкина эквивалентности 1 x y, раскроем скобки, и вычеркнем появившиеся при этом пары одинаковых слагаемых ]
[заменим инверсию ее полиномом Жегалкина, раскроем скобки и вычеркнем пары одинаковых слагаемых ]
Полином, естественно, совпадает с полученными ранее по совершенной и произвольной ДНФ.
Способ 3. Если булева функций задана произвольной формулой, то ее полином Жегалкина можно получить, используя специальное разложение функции.
Определение. Разложением Дэвио называется следующее разложение булевой функции f(x1, …, xn по переменной xi:
f(x1, …, xn) = xif(x1, …, xi –1,1,xi+1, …, xn)
(1 xi)f(x1, …, xi –1,0,xi+1, …, xn).
Разложение Дэвио непосредственно следует из разложения Шеннона, если учесть, что слагаемые в последнем ортогональны, и что x i=xi 1.
Пример. Найдем разложение Дэвио по переменной x мажоритарной булевой функции, заданной формулой.
F = ((x y) z) /(x y)=
=x[((1 y) z) /(1 y)] (1 x) [((0 y) z) /(0 y)]=
=x[(y z) /y ] (1 x)[y 
z].
Для получения полинома Жегалкина необходимо продолжить разложение подформул, не являющихся дизъюнкцией с исключением элементарных конъюнкций, пока не получится формула над { , 
, –}. Если в такой формуле заменить инверсии x на x 1, раскрыть скобки и вычеркнуть пары одинаковых слагаемых, то получится полином Жегалкина.
Пример. Продолжив предыдущий пример, получим полином Жегалкина мажоритарной функции. Для этого разложим подформулы (y z) /y и y z по переменной y:
Полином Жегалкина, естественно, совпадает с полученными ранее.
Алгоритм построения полинома Жегалкина по таблице истинности (основан на методе неопределенных коэффициентов).
Продемонстрируем идею метода на примере произвольной булевой функции двух аргументов f(x,y). Представим ее полиномом Жегалкина в форме с коэффициентами
Pf = c0 c1y c2x c3x y.
Подставив в данное равенство наборы значений аргументов, получим систему из четырех линейных уравнений с четырьмя неизвестными коэффициентами: c0, c1 c2, c3.
f(0,0) = c0 c10 c20 c30 0 = c0
f(0,1) = c0 c11 c20 c30 1 = c0 c1
f(1,0) = c0 c10 c21 c31 0 = c0 c2
f(1,1) = c0 c11 c21 c31 1 = c0 c1 c2 c3
Заметим, что наборы подставлены в равенство в естественном порядке, и система имеет треугольный вид: в первом уравнении обратились в ноль все слагаемые, следующие за c0, во втором – следующие за c1 и так далее. Значит, коэффициент c0 можно получить из первого уравнения и подставить его в остальные. Тогда c1 можно получить из второго уравнения, и так далее.
В общем случае для функции n аргументов получается система треугольного вида из 2 n линейных уравнений с 2 n неизвестными – коэффициентами полинома Жегалкина.
Пример. Найдем полином Жегалкина мажоритарной булевой функции, заданной таблицей истинности, последовательно вычисляя коэффициенты полинома и подставляя их в остальные уравнения.
Из первого уравнения следует, что c0=0. Из второго и третьего уравнений следует, что c1=0 и c2=0, значит, c1z и c2y тождественно равны нулю. Из четвертого уравнения получаем c3=1, значит, надо вычислять значения конъюнкции c3yz в остальных уравнениях. Аналогично получаем c4=0, c5=1, c6=1 и c7=0. Найден вектор коэффициентов полинома Жегалкина мажоритарной функции π=00010110, и сам полином P=yz xz xy, который, естественно, совпадает с полученными ранее. •