Полином Жегалкина: любая булева функция одной формулой

Калькулятор булевых функций выводит СДНФ и СКНФ — и ставит рядом третью форму: полином Жегалкина. В нём нет ни отрицания, ни дизъюнкции: хватает двух операций, сложения по модулю два и умножения. В 1927 году московский математик Иван Жегалкин доказал, что такая запись существует для любой таблицы истинности и единственна. В западных учебниках форма называется algebraic normal form, ANF, а в криптографии она до сих пор рабочий инструмент.

Как выглядит многочлен над нулями и единицами

Договоримся: сложение — это XOR (⊕, сумма по модулю два), умножение — конъюнкция (∧). Полином от переменных x₁, …, x_n выглядит как сумма произведений:

f = a₀ ⊕ a₁x₁ ⊕ a₂x₂ ⊕ a₁₂x₁x₂ ⊕ … ⊕ a₁…ₙx₁…xₙ

Коэффициенты a равны 0 или 1: слагаемое либо входит в полином, либо нет. Разложим базовые операции:

Последняя строка требует пояснения: когда оба входа равны 1, XOR даёт 0, а дизъюнкция хочет 1 — поэтому к x ⊕ y добавлена поправка x·y. Отрицание есть частный случай той же арифметики: прибавление единицы по модулю два переворачивает бит, ¬x = x ⊕ 1. Из двух правил собирается любое выражение: x → y раскладывается как ¬x ∨ y и после приведения подобных даёт 1 ⊕ x ⊕ x·y (проверим это ниже таблицей, а пока примем на веру).

Полином существует и единственен

Посчитаем. Моном (произведение разных переменных) строится выбором: каждую из n переменных либо брать в произведение, либо нет; пустое произведение — константа. Итого 2ⁿ мономов, у каждого коэффициент 0 или 1 — значит, различных полиномов ровно 2^(2ⁿ). Ровно столько же существуют булевы функции от n переменных. Теорема Жегалкина (1927) говорит: каждая функция представима полиномом. Раз функций и полиномов поровну, а каждый полином задаёт ровно одну функцию, представление единственно: две разные таблицы истинности не могут дать один и тот же многочлен.

Проверка на пальцах для n = 2: 4 монома (1, x, y, x·y), 2⁴ = 16 полиномов — те же 16 функций, что перечисляет таблица из четырёх строк.

Как получить полином из таблицы истинности

Метод неопределённых коэффициентов решает полином по строкам таблицы, от первой к последней. Возьмём импликацию x → y с вектором значений 1, 1, 0, 1 (строки 00, 01, 10, 11) и подставим в общий вид:

f = a ⊕ b·x ⊕ c·y ⊕ d·x·y

00: f = a             = 1 → a = 1
01: f = a ⊕ c         = 1 → c = 0
10: f = a ⊕ b         = 0 → b = 1
11: f = a ⊕ b ⊕ c ⊕ d = 1 → d = 1

Каждая новая строка добавляет ровно одно новое неизвестное и не спорит с прежними: система треугольная и решается за один проход. Ответ: x → y = 1 ⊕ x ⊕ x·y. Для n переменных схема та же, только строк 2ⁿ.

Калькулятор идёт быстрее: применяет преобразование Мёбиуса, прогоняя вектор значений по каждой переменной и заменяя нижнюю половину каждого блока её суммой с верхней. Для вектора 1101 (та же импликация): начальное состояние 1 1 0 1, после хода по y получается 1 0 0 1, после хода по x — 1 0 1 1. Четыре числа на выходе — коэффициенты при 1, y, x и x·y: снова 1 ⊕ x ⊕ x·y. Промежуточные векторы видны в решении, если включить опцию «С решением».

Степень полинома и линейные функции

Степень — наибольшее число переменных в одном произведении. Полином степени не выше первой особенный: это константа, XOR переменных или XOR переменных с инвертированием (x ⊕ 1 = ¬x). Такие функции образуют класс L Поста, и калькулятор проверяет принадлежность к нему ровно по полиному: нашлось произведение двух и более переменных — функция нелинейна.

Самая узнаваемая линейная функция — строгая чётность, XOR всех входов. На ней держатся регистры сдвига с обратной связью: в LFSR новый бит есть линейный полином от нескольких разрядов, например x₁ ⊕ x₅. Компонент LFSR живёт в песочнице: подай такт и следи, как единица бежит по кольцу.

Где полином работает

В схемотехнике форма удобна там, где XOR дешевле дизъюнкции: суммы сумматоров, генераторы чётности и контрольные суммы, CRC — это каскады исключающего ИЛИ, то есть полиномы первой или низкой степени, уложенные в минимальное число вентилей.

В криптографии ANF — язык анализа блочных шифров: степень полиномов S-блока и расстояние до класса линейных функций (нелинейность) определяют, выдержит ли алгоритм линейные и алгебраические атаки. Хороший S-блок строится так, чтобы его полином Жегалкина содержал много слагаемых высокой степени: тогда каждое отдельное уравнение почти ничего не говорит о ключе.

Зачем это в игре

Полный сумматор (уровень 1.7) — учебный пример разницы форм. Сумма трёх битов в СДНФ занимает четыре минтерма, а в полиноме — одна строка A ⊕ B ⊕ P, где P — входной перенос. Перенос в обеих формах пишется одинаково коротко: AB ⊕ AP ⊕ BP. Совпадение с минимальной ДНФ из прошлой статьи не случайно: на каждом наборе с ответом 1 в мажоритарной функции сработана одна пара входов или сразу все три, то есть нечётное число; для нечётного числа единиц дизъюнкция и сложение по модулю два дают одно и то же.

assign sum   = a ^ b ^ c;
assign carry = (a & b) ^ (a & c) ^ (b & c);

Введи в калькулятор вектор голосования 00010111 и включи «С решением»: получишь полином AB ⊕ AP ⊕ BP и все три хода преобразования Мёбиуса отдельной таблицей. Таблица для этой же функции есть и в генераторе таблиц истинности.

Резюме

1. Полином Жегалкина — сумма по модулю два произведений переменных с коэффициентами 0 и 1; достаточно операций ⊕ и ∧.

2. Представление существует и единственно: полиномов ровно столько, сколько функций (2^(2ⁿ)); доказал Жегалкин в 1927 году.

3. Коэффициенты решаются треугольной подстановкой строк таблицы — метод неопределённых коэффициентов; калькулятор применяет преобразование Мёбиуса за n проходов.

4. Степень не выше первой — линейные функции: чётность, XOR-цепочки, обратная связь LFSR; это и есть класс L в проверке Поста.

5. Полином экономит вентили там, где дешёв XOR: сумма полного сумматора — одна строка против четырёх минтермов в СДНФ.

На уровнях 1.6–1.8 посмотри свежим взглядом на сумму полного и 8-битного сумматоров: в полиноме Жегалкина обе линейные, и потому складывающие биты блоки — цепочки XOR, а не четырёхуровневые схемы из СДНФ. Проверить свою функцию можно в калькуляторе, а дальше по курсу идёт арифметика: двоичная математика.