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

Инженер собирает схему из элементов «И-НЕ»: два вида работы — отрицание и конъюнкция — покрывают всё. Возникает неудобный вопрос: а из чего собирает математик? Если разрешить только сложение по модулю 2 и умножение, выйдет ли полноценная арифметика логики? Ответ: да, выйдет, и даже лучше, чем в ДНФ — каждая функция получит единственную запись. Эту запись называют полиномом Жегалкина, и она сидит внутри самых разных вещей: от контрольных сумм из урока об основах кодирования до криптографии, где линейность полинома меряется буквально, потому что линейная функция вскрывается проще нелинейной.

Сколько вообще булевых функций#

Булева функция принимает аргументы из $\{0,1\}$ и возвращает 0 или 1. Таблица истинности из $n$ столбцов переменных имеет $2^n$ строк — по строке на каждый входной набор, и в каждой строке значение выбирается из двух вариантов. Отсюда арифметика: функций от $n$ переменных ровно $2^{2^n}$. При $n=2$ их шестнадцать — все были разложены по полочкам ещё в уроке о булевой алгебре; при $n=3$ — уже 256, а при $n=10$ — более триллиона. Писать для каждой свою формулу бессмысленно, нужны стандартные формы.

Одна из них вам уже знакома — дизъюнктивная нормальная форма: дизъюнкция конъюнкций, по одному слагаемому на каждую строку таблицы с единицей. СДНФ честно воспроизводит функцию, но у неё есть дефект: она не единственная. Функцию XOR можно записать как $\bar{x}y\vee x\bar{y}$, а можно упростить до $x\oplus y$ — и обе записи «правильные». Для сравнения схем, для автоматических доказательств и для криптографии нужна форма, которая у каждой функции одна. Такой формой и оказывается многочлен.

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

Это обычный многочлен, но арифметика — модульная. Сложение — XOR: $1\oplus 1=0$. Умножение — обычное И: $1\cdot 1=1$. Отрицаний нет, степеней выше первой нет — и быть не может, ведь $x\cdot x=x$: квадрат переменной в мире нулей и единиц равен самой переменной. Именно это правило убивает все высшие степени и делает число возможных многочленов конечным: для каждой из $2^n$ комбинаций переменных одночлен либо есть, либо нет. Многочленов ровно $2^{2^n}$ — столько же, сколько функций. Гадать не приходится: если различных объектов поровну и каждый многочлен задаёт какую-то функцию, то соответствие взаимно однозначно. Единственность полинома доказывается без единой строки вычислений.

Мостом между привычными операциями и полиномиальным миром служат три тождества — их достаточно, чтобы перевести любую формулу:

• $x\vee y=x\oplus y\oplus xy$ — дизъюнкция равна сумме минус произведение (проверьте на четырёх наборах: совпадение на трёх, а на $x=y=1$ двойная единица схлопывается в ноль, и остаётся $1\oplus 1\oplus 1=1$)
• $\bar{x}=x\oplus 1$ — отрицание это прибавление единицы; в мире по модулю 2 знак минус неотличим от плюса
• $x\to y=1\oplus x\oplus xy$ — импликация тоже раскладывается, хотя на вид кажется далёкой от многочленов

Дальше механика: заменить в ДНФ каждую связку по этим правилам, раскрыть скобки (дистрибутивность И над XOR работает, как в школьной алгебре), собрать повторяющиеся одночлены парами и вычеркнуть — $a\oplus a=0$.

Способ первый: алгебра, раскрытие скобок#

Возьмём функцию мажоритарного голосования — она равна 1, когда хотя бы два из трёх аргументов равны 1. Такое устройство стоит в тройных системах дублирования: два канала против одного. В ДНФ она записывается как $xy\vee xz\vee yz$ — три слагаемых, каждый голос в паре. Переводим: дизъюнкция трёх слагаемых раскладывается итеративно, каждое $\vee$ заменяется по правилу выше. Раскрытие скобок даёт шесть одночленов-произведений (все пары $xy,xz,yz$ возникают дважды), пары гасятся по чётности, и остаётся элегантный итог:

Способ быстрый, но требует алгебраической аккуратности: на четырёх-пяти переменных скобки распухают, и потерять слагаемое проще, чем его найти. Для контрольных работ и самопроверки существует второй путь — систематический.

Способ второй: метод неопределённых коэффициентов#

Выпишем полином с восемью неизвестными коэффициентами — по одному на каждую возможную комбинацию переменных $x,y,z$:

И подставим строки таблицы истинности одну за другой. Каждая строка даёт линейное уравнение над $\{0,1\}$, а хитрость в порядке чтения: если идти от набора $000$ вверх, каждый новый коэффициент входит в уравнение один — он умножен на произведение, которое на строках с большим числом единиц ещё не встречалось. Решение выпадает последовательно, без систем уравнений.

Метод выигрывает в надёжности: он не требует ни формулы-исходника, ни знания ДНФ — только таблицу. Именно таблица и есть полный паспорт функции, а полином — её сжатая портретная карточка. Для функций с большим числом переменных оба пути механизируются: коэффициенты метода — это в точности биты преобразования Уолша—Адамара, и вся процедура сводится к быстрому преобразованию, которое работает за $O(n{2}^n)$ операций.

Линейные функции: полином без произведений#

Если все коэффициенты при произведениях нулевые, полином вырождается в сумму переменных и константы: $f=a_0\oplus a_1{x}_1\oplus \cdots \oplus a_n{x}_n$. Такие функции называют линейными. Их немного: коэффициентов $n+1$, каждый выбирается из двух значений, итого $2^{n+1}$ линейных функций на $2^{2^n}$ всех — при $n=3$ шестнадцать из 256. Из уже знакомых линейны: отрицание ($x\oplus 1$), эквивалентность ($x\oplus y\oplus 1$), само сложение по модулю 2, тождественный ноль и единица.

Практический тест на линейность без построения полного полинома: производная по паре переменных. В обычном анализе смешанная вторая производная нелинейного члена не нулевая; здесь то же самое на пальцах — возьмите функцию на двух наборах, различающихся ровно в $x$ и $y$ одновременно. У линейной функции эффекты двух переменных складываются независимо, и разность значений на «диагональной» паре определяется линейными членами. Быстрее всего нелинейность ловится прямым сравнением: посчитайте $f$ на четырёх наборах из квадрата $x,y$ при фиксированных остальных и проверьте, раскладывается ли этот фрагмент в $\alpha \oplus \beta x\oplus \gamma y$. Если нет — где-то спрятано произведение.

Почему за линейностью следят? Во-первых, по теореме Поста из булевой алгебры класс линейных функций не полон: из одних XOR-сумм не собрать ни конъюнкцию, ни запертую систему — значит, не собрать и вычислитель. Во-вторых, в криптографии шифры стараются строить так, чтобы выход не был линейной функцией входа: линейность для криптоаналитика — открытая дверь, взлом сводится к решению системы уравнений. Существуют даже специально «предельно нелинейные» функции — бент-функции, у которых полином содержит произведения максимальной плотности.

Полином Жегалкина полезен и как инструмент сравнения схем: две формулы задают одну функцию тогда и только тогда, когда их полиномы совпали. Пришла пара кандидаток из оптимизатора схем? Приведите обе к Жегалкину — разошлись, значит, функции разные. Тот же критерий работает для проверки эквивалентности логических формул в логике высказываний, только там удобнее сравнивать таблицы; полином экономнее — он короче таблицы.

Отдельная приятность для алгоритмистов: функция, заданная полиномом, вычисляется за один проход по одночленам — нет ни каскада отрицаний, ни длинных дизъюнкций. Комбинационные схемы из XOR-деревьев и умножителей — это в точности железная реализация полинома Жегалкина, а конечные автоматы из соответствующего урока умеют пересчитывать его по мере поступления битов: вспомните сдвиговые регистры с обратной связью — там линейный полином определяет, какие разряды складывать на каждом такте.

Частые промахи при построении полинома: первый — забыть правило $x^2=x$ и оставить «квадраты»; второй — при замене дизъюнкции потерять произведение $xy$, записав $x\vee y=x\oplus y$ (это XOR, а не ИЛИ — на наборе $11$ они расходятся); третий — в методе коэффициентов решать строки в случайном порядке и упираться в систему из нескольких уравнений. Итоговую шпаргалку темы удобно держать в голове списком:

• Полином Жегалкина — сумма по модулю 2 одночленов без отрицаний и степеней выше первой; у каждой функции он ровно один
• Три тождества-переводчика: $\bar{x}=x\oplus 1$, $x\vee y=x\oplus y\oplus xy$, $x\to y=1\oplus x\oplus xy$
• Метод коэффициентов: строки таблицы от нулевого набора вверх, каждый коэффициент выписывается независимо
• Линейные функции — $2^{n+1}$ штук; их класс не полон, а в шифрах линейность — уязвимость