Pull to refresh

Что нам стоит полином Жегалкина построить…

Reading time 2 min
Views 146K
Думаю, каждый, кто изучал или изучает в университете дискретную математику, знаком с понятием многочлена Жегалкина.

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

Чаще всего для построения полиномов Жегалкина студентам предлагаются два метода построения таких полиномов: метод неопределенных коэффициентов и метод эквивалентных преобразований.

Расчеты с использованием данных методов часто оказываются громоздкими. По невнимательности допустить ошибку не составляет труда.

Под катом приведен один удобный алгоритм, для построения полиномов Жегалкина, который студенты воспринимают «на ура», т.к. требует только выполнение «механических действий» без применения каких-либо умственных усилий. Краткое описание метода можно найти в Википедии, но на мой взгляд по нему не совсем понятно, как быстро проводить вычисления. Мне метод известен под названием «метод треугольника Паскаля».

Порядок проведения вычислений проще показать на примере. Далее я буду по шагам показывать, как должен выглядеть расчет на бумаге (или как его удобно проводить).

Метод треугольника Паскаля


Требуется построить полином Жегалкина для функции f. Для примера, в качестве функции f возьмем функцию голосования f(x_1, x_2, x_3)=x_1x_2\vee x_2x_3\vee x_1x_3 = (00010111).

Шаг 1. Строим таблицу значений функции (строки в таблице идут в порядке возрастания двоичных кодов). Таблицу лучше разместить в левой части листа.

Таблица значений функции

Шаг 2. Построение треугольника.

Для этого берем вектор значения функции и выписываем его напротив первой строки таблицы:

Выписываем вектор значений функции

Далее заполняем треугольник, складывая попарно соседние значения по модулю 2, результат сложения выписываем ниже.

Строим треугольник

Продолжаем вычисления, пока в строке не останется лишь одна цифра.

Завершили построение треугольника

Шаг 3. Построение полинома Жегалкина.

Нас интересует левая сторона треугольника (значения выделены жирным):

Левая сторона треугольника

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

Теперь выпишем для наглядности эти конъюнкции. Конъюнкции выписываем по двоичным наборам в левой части таблицы по следующему принципу: если напротив переменной xi стоит 1, то переменная входит в конъюнкцию; в противном случае переменная отсутствует в конъюнкции. Набору (0,0,0) соответствует константа 1.

Формирование мономов

Если принцип получения конъюнкций понятен, то столбец с ними можно (даже лучше) не выписывать, а сразу переходить к построению полинома.

Для построения полинома нужны только конъюнкции из строк с единицами на левой стороне треугольника.

Выбор конъюнкций для полинома

Это и есть конъюнкции, входящие в состав полинома Жегалкина. Осталось лишь выписать сам полином:
f({{x}_{1}},{{x}_{2}},{{x}_{3}})={{x}_{1}}{{x}_{2}}\oplus {{x}_{2}}{{x}_{3}}\oplus {{x}_{1}}{{x}_{3}}.

Если переменных в функции не 3, а 4 или больше, то метод работает без изменений, только увеличатся размеры таблиц. Тем не менее, в отличие от метода неопределенных коэффициентов, расчеты можно без особых усилий выполнить на листе бумаги.

Литература


К сожалению, мне не удалось найти и посмотреть источник, указанный в Википедии:
В.П. Супрун Табличный метод полиномиального разложения булевых функций // Кибернетика. — 1987. — № 1. — С. 116-117.
Tags:
Hubs:
+29
Comments 20
Comments Comments 20

Articles