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

Рассмотрим алгоритмы построения полинома Жегалкина булевой функции, заданной различными способами, а именно: совершенной ДНФ, произвольной ДНФ, формулой и таблицей истинности.

Алгоритм построения полинома Жегалкина по СовДНФ (основан на доказательстве теоремы о существовании полинома Жегалкина).

Начало. Задана совершенная ДНФ функции f(x₁, …, x_n).

Шаг 1. Заменяем каждый символ дизъюнкции на символ дизюнкции с исключением.

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

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

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

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

Пример. Найдем полином Жегалкина мажоритарной булевой функции по ее совершенной ДНФ.

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

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

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

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

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

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

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

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

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

Пример. Найдем полином Жегалкина мажоритарной функции по ДНФ.

Отметим, что полиномы мажоритарной функции, полученные в двух последних примерах, совпадают с точностью до порядка конъюнкций, и это естественно (по теореме о единственности полинома Жегалкина).