Что такое полином Жегалкина

В алгебре Жегалкина {x, 1, ^, ⊕} – весь наш набор. Есть только сумма по модулю 2 и единица (и переменные)

$$ x ⊕ 0 = x \newline x ⊕ 1 = \overline{x} \newline x ⊕ x = 0, x ⊕ \overline{x} = 1 \newline \text{⊕ коммутативна, ассоциативна, дистрибутивна} $$

¬x = x ⊕ 1

x ∨ y = xy ⊕ x ⊕ y

Алгоритм построения полинома Жегалкина через СДНФ

1. Построить СДНФ;
2. Воспользоваться формулой x ∨ y = xy ⊕ x ⊕ y. Так как мы имеем СДНФ, то тут просто v заменяем на ⊕
3. Выносим за скобки, некоторое по свойствам ⊕ (см выше) станет константой и уйдёт.
4. Отрицания заменяем на (переменная ⊕ 1)
5. Раскрываем скобки, дубликаты уходят (см 3 строчку, там одинаковые просто пропадают в сумме по модулю 2)

Через вектор значений

Быстрее. Выписываем вектор значений горизонтально и складываем соседние цифры по модулю 2. Так у нас вниз растёт треугольник, левая сторона которого и будет коэффициентами полинома:

$a_0 + a_1x_1 + a_2x_2 + ... + a_nx_n$