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

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

Полином был предложен в 1927 году И. И. Жегалкиным (1869-1947 гг.) в качестве удобного средства для представления функций булевой логики. В зарубежной литературе представление в виде полинома Жегалкина обычно называется алгебраической нормальной формой (АНФ).

Определение

Полиномом Жегалкина от n переменных U1,U2,…Un называется сумма по модулю 2 этих переменных, каждое слагаемое которой является либо константой 0 или 1, либо переменной, либо конъюнкцией нескольких переменных.

Общий вид полинома Жегалкина для двух переменных x1 и x2 можно записать как , где C0, C1, C2, C12 - константы 0 или 1.

Теорема

Каждая булева функция от n переменных представима полиномом Жегалкина от этих же переменных.

По теореме Жегалкина, полином Жегалкина от n переменных x1,x2,…xn содержит не более 2n слагаемых и однозначно определяется набором своих коэффициентов.

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

Существует несколько методов построения полинома Жегалкина. Обычно, рассматриваются два таких метода: метод неопределенных коэффициентов и метод эквивалентных преобразований. Но зачастую, расчеты с использованием этих методов оказываются громоздкими. Существуют многообразные способы, упрощающие построение полинома. Одним из этих методов является метод треугольника (метод «треугольника Паскаля»). Он позволяет преобразовать таблицу истинности в полином Жегалкина с помощью построения дополнительной треугольной таблицы по незамысловатым правилам, что является большим плюсом к удобности использования.

Правила построения полинома Жегалкина методом треугольника:

  1. Построить таблицу истинности
  2. Вектор значений функции выписать в горизонтальной строке, это будет началом дополнительной таблицы
  3. Каждая ячейка следующих строк таблицы получается суммированием по модулю 2 двух вышестоящих ячеек предыдущей строки
  4. Вычисления продолжаются, пока в строке не останется лишь одна цифра
  5. В построенной таблице слева мы получаем искомый набор коэффициентов. Первому левому элементу каждой строки из получившейся треугольной таблицы соответствует значение переменной C в полиноме Жегалкина. Набору (0,0,…,0) соответствует константа 1.

Пример построения полинома Жегалкина для функции приведен в таблице 1. Полином для рассматриваемой функции имеет вид:

Таблица 1. Пример построения полинома Жегалкина

Полином Жегалкина, в котором отсутствуют конъюнкции переменных, называется линейным. Рассмотренный выше полином линейным не является.