Одним из способов представления булевых функций является полином Жегалкина.
Полином был предложен в 1927 году И. И. Жегалкиным (1869-1947 гг.) в качестве удобного средства для представления функций булевой логики.
В зарубежной литературе представление в виде полинома Жегалкина обычно называется алгебраической нормальной формой (АНФ).
Определение
Полиномом Жегалкина от n переменных U1,U2,…Un называется сумма по модулю 2 этих переменных, каждое слагаемое которой является либо константой 0 или 1, либо переменной, либо конъюнкцией нескольких переменных.
Общий вид полинома Жегалкина для двух переменных x1 и x2 можно записать как
, где C0, C1, C2, C12 - константы 0 или 1.
Теорема
Каждая булева функция от n переменных представима полиномом Жегалкина от этих же переменных.
По теореме Жегалкина, полином Жегалкина от n переменных x1,x2,…xn содержит не более 2n слагаемых и однозначно определяется набором своих коэффициентов.
Методы построения полинома Жегалкина
Существует несколько методов построения полинома Жегалкина.
Обычно, рассматриваются два таких метода: метод неопределенных коэффициентов и метод эквивалентных преобразований.
Но зачастую, расчеты с использованием этих методов оказываются громоздкими.
Существуют многообразные способы, упрощающие построение полинома.
Одним из этих методов является метод треугольника (метод «треугольника Паскаля»).
Он позволяет преобразовать таблицу истинности в полином Жегалкина с помощью построения дополнительной треугольной таблицы по незамысловатым правилам, что является большим плюсом к удобности использования.
Правила построения полинома Жегалкина методом треугольника:
- Построить таблицу истинности
- Вектор значений функции выписать в горизонтальной строке, это будет началом дополнительной таблицы
- Каждая ячейка следующих строк таблицы получается суммированием по модулю 2 двух вышестоящих ячеек предыдущей строки
- Вычисления продолжаются, пока в строке не останется лишь одна цифра
- В построенной таблице слева мы получаем искомый набор коэффициентов. Первому левому элементу каждой строки из получившейся треугольной таблицы соответствует значение переменной C в полиноме Жегалкина. Набору (0,0,…,0) соответствует константа 1.
Пример построения полинома Жегалкина для функции
приведен в таблице 1.
Полином для рассматриваемой функции имеет вид: 
Таблица 1. Пример построения полинома Жегалкина
Полином Жегалкина, в котором отсутствуют конъюнкции переменных, называется линейным. Рассмотренный выше полином линейным не является.