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

Полином Жегалкина — многочлен над полем ${\displaystyle \mathbb {Z} _{2}}$, то есть полином с коэффициентами вида 0 и 1, где в качестве произведения берётся конъюнкция, а в качестве сложения — исключающее или. Полином был предложен в 1927 году Иваном Жегалкиным в качестве удобного средства для представления функций булевой логики. В зарубежной литературе представление в виде полинома Жегалкина обычно называется алгебраической нормальной формой (АНФ).

Теорема Жегалкина — утверждение о существовании и единственности представления всякой булевой функции в виде полинома Жегалкина^[1].

Полином Жегалкина представляет собой сумму по модулю два попарно различных произведений неинвертированных переменных, где ни в одном произведении ни одна переменная не встречается больше одного раза, а также (если необходимо) константы 1^[1]. Формально полином Жегалкина можно представить в виде

${\displaystyle P(X_{1},\dots ,X_{n})=a\oplus a_{1}X_{1}\oplus a_{2}X_{2}\oplus \dots \oplus a_{n}X_{n}\oplus a_{12}X_{1}X_{2}\oplus a_{13}X_{1}X_{3}\oplus \ldots \oplus a_{1\dots n}X_{1}\dots X_{n},}$

${\displaystyle a_{1},\ldots ,a_{1\ldots n}\in \{0,1\},}$

или в более формализованном виде как

${\displaystyle P=a\oplus \bigoplus _{\begin{array}{c}1\leqslant i_{1}<\ldots <i_{k}\leqslant n\\k\in {\overline {1,n}}\end{array}}a_{i_{1},\ldots ,i_{k}}\wedge x_{i_{1}}\wedge \ldots \wedge x_{i_{k}},\quad a,a_{i_{1},\ldots ,i_{k}}\in \{0,1\}.}$

Примеры полиномов Жегалкина:

${\displaystyle P=B\oplus AB,}$

${\displaystyle P=X\oplus YZ\oplus ABX\oplus ABDYZ,}$

${\displaystyle P=1\oplus A\oplus ABD.}$

По теореме Поста, чтобы система булевых функций была полной, надо, чтобы в ней существовали:

1. Хотя бы одна функция, не сохраняющая 0.
2. Хотя бы одна функция, не сохраняющая 1.
3. Хотя бы одна нелинейная функция.
4. Хотя бы одна немонотонная функция.
5. Хотя бы одна несамодвойственная функция.

Этому требованию отвечает, в частности, система функций ${\displaystyle {\bigl \langle }\wedge ,\oplus ,1{\bigr \rangle }}$ (конъюнкция, сложение по модулю два, константа 1). На её основе и строятся полиномы Жегалкина.

По теореме Жегалкина каждая булева функция единственным образом представляется в виде полинома Жегалкина. Теорема доказывается следующим образом. Заметим, что различных булевых функций от n переменных ${\displaystyle 2^{2^{n}}}$ штук. При этом конъюнкций от n переменных существует ровно 2ⁿ, так как из n возможных сомножителей каждый или входит в конъюнкцию, или нет. В полиноме у каждой такой конъюнкции стоит 0 или 1, то есть существует ${\displaystyle 2^{2^{n}}}$ различных полиномов Жегалкина от n переменных. Теперь достаточно лишь доказать, что различные полиномы реализуют различные функции. Предположим противное. Тогда приравняв два различных полинома и перенеся один из них в другую часть равенства, получим полином, тождественно равный нулю и имеющий ненулевые коэффициенты. Тогда рассмотрим слагаемое с единичным коэффициентом наименьшей длины, то есть с наименьшим числом переменных, входящих в него (любой один, если таких несколько). Подставив единицы на места этих переменных и нули на места остальных, получим, что на этом наборе только одно это слагаемое принимает единичное значение, то есть нулевая функция на одном из наборов принимает значение 1. Противоречие. Значит, каждая булева функция реализуется полиномом Жегалкина единственным образом.

По сравнению с ДНФ в полиноме Жегалкина отсутствуют операции ИЛИ и НЕ. Таким образом, полином Жегалкина можно получить из ДНФ, выразив операции ИЛИ и НЕ через операции сложение по модулю два, и константу 1. Для этого применяются следующие соотношения:

${\displaystyle A\vee B=A\oplus B\oplus AB,}$

${\displaystyle {\overline {A}}=A\oplus 1.}$

Ниже приведён пример преобразования ДНФ в полином Жегалкина:

${\displaystyle XY\vee {\overline {X}}\,{\overline {Y}}=XY\oplus {\overline {X}}\,{\overline {Y}}\oplus XY{\overline {X}}\,{\overline {Y}}=XY\oplus {\overline {X}}\,{\overline {Y}}=XY\oplus (X\oplus 1)(Y\oplus 1)=}$

${\displaystyle \quad =XY\oplus XY\oplus X\oplus Y\oplus 1=X\oplus Y\oplus 1.}$

При преобразованиях использованы соотношения

${\displaystyle A\oplus A=0,}$

${\displaystyle (A\oplus B)C=AC\oplus BC.}$

СДНФ обладает тем свойством, что при любых значениях входных переменных в единицу обращается не более одного члена выражения. Для таких выражений операция дизъюнкции эквивалентна операции сложение по модулю два.

При преобразовании СДНФ в полином Жегалкина достаточно заменить все дизъюнкции на операции сложение по модулю два и избавиться от инверсий при помощи эквивалентного преобразования

${\displaystyle {\overline {A}}=A\oplus 1.}$

Логическая функция трёх переменных ${\displaystyle P(A,B,C)}$, представленная в виде карты Карно, преобразуется в полином Жегалкина следующими шагами:

• Рассматриваем все ячейки карты Карно в порядке возрастания количества единиц в их кодах. Для функции трёх переменных последовательность ячеек будет 000—100 — 010—001 — 110—101 — 011—111. Каждой ячейке карты Карно сопоставляем член полинома Жегалкина в зависимости от позиций кода, в которых стоят единицы. Например, ячейке 111 соответствует член ABC, ячейке 101 — член AC, ячейке 010 — член B, ячейке 000 — член 1.
• Если в рассматриваемой ячейке находится 0, переходим к следующей ячейке.
• Если в рассматриваемой ячейке находится 1, добавляем в полином Жегалкина соответствующий член, инвертируем в карте Карно все ячейки, где этот член равен 1, и переходим к следующей ячейке. Например, если при рассмотрении ячейки 110 в ней оказывается единица, то в полином Жегалкина добавляется член AB и инвертируются все ячейки карты Карно, где A = 1 и B = 1. Если единице равна ячейка 000, то в полином Жегалкина добавляется член 1 и инвертируется вся карта Карно.
• Процесс преобразования можно считать законченным, когда после очередной инверсии все ячейки карты Карно становятся нулевыми.

Метод треугольника (часто называемый методом треугольника Паскаля) позволяет преобразовать таблицу истинности в полином Жегалкина путём построения вспомогательной треугольной таблицы в соответствии со следующими правилами:

• Строится полная таблица истинности, в которой строки идут в порядке возрастания двоичных кодов от 000…00 до 111…11.
• Строится вспомогательная треугольная таблица, в которой первый столбец совпадает со столбцом значений функции в таблице истинности.
• Ячейка в каждом последующем столбце получается путём суммирования по модулю 2 двух ячеек предыдущего столбца — стоящей в той же строке и строкой ниже.
• Столбцы вспомогательной таблицы нумеруются двоичными кодами в том же порядке, что и строки таблицы истинности.
• Каждому двоичному коду ставится в соответствие один из членов полинома Жегалкина в зависимости от позиций кода, в которых стоят единицы. Например, ячейке 111 соответствует член ABC, ячейке 101 — член AC, ячейке 010 — член B, ячейке 000 — член 1 и т. д.
• Если в верхней строке какого-либо столбца стоит единица, то соответствующий член присутствует в полиноме Жегалкина.

Метод треугольника основан на теореме, предложенной В. П. Супруном, не связанной напрямую с треугольником Паскаля. В 1985 году метод двоичного треугольника было предложено использовать для преобразования вектора значений совершенной дизъюнктивной нормальной формы в вектор коэффициентов полинома Жегалкина для произвольной симметрической булевой функции. В 1987 году метод был расширен для произвольной булевой функции. Отметим, что метод треугольника позволяет строить полином Рида — Маллера^[англ.] с отрицательной поляризацией как для симметрических функций, так и для произвольных^[].

Наиболее экономным с точки зрения объёма вычислений и целесообразным для построения полинома Жегалкина вручную является метод быстрого преобразования Фурье (БПФ).

Строим таблицу, состоящую из 2^N столбцов и N + 1 строк, где N — количество переменных в функции. В верхней строке таблицы размещаем вектор значений функции, то есть последний столбец таблицы истинности.

Каждую строку полученной таблицы разбиваем на блоки (чёрные линии на рисунке). В первой строке блок занимает одну клетку, во второй строке — две, в третьей — четыре, в четвёртой — восемь и т. д. Каждому блоку в некоторой строке, который мы будем называть «нижний блок», всегда соответствует ровно два блока в предыдущей строке. Будем называть их «левый верхний блок» и «правый верхний блок».

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

По таблице истинности легко вычислить отдельные коэффициенты полинома Жегалкина. Для этого нужно просуммировать по модулю 2 значения функции в тех строках таблицы, где переменные, отсутствующие в конъюнкции, принимают нулевые значения.

Предположим для примера, что нужно найти коэффициент при конъюнкции xz для функции трёх переменных f(x, y, z). В этой конъюнкции отсутствует переменная y. Найдём входные наборы, в которых переменная y принимает нулевое значение. Это наборы 0, 1, 4, 5 (000, 001, 100, 101). Тогда коэффициент при конъюнкции xz равен

${\displaystyle a_{5}=f_{0}\oplus f_{1}\oplus f_{4}\oplus f_{5}=f(0,0,0)\oplus f(0,0,1)\oplus f(1,0,0)\oplus f(1,0,1).}$

Поскольку в свободном члене отсутствуют все переменные, то

${\displaystyle a_{0}=f_{0}.}$

Для члена, куда входят все переменные, в сумму входят все значения функции:

${\displaystyle a_{N-1}=f_{0}+f_{1}+f_{2}+\ldots +f_{N-2}+f_{N-1}.}$

Представим графически коэффициенты полинома Жегалкина как суммы по модулю 2 значений функций в некоторых точках. Для этого построим квадратную таблицу, где каждый столбец представляет собой значение функции в одной из точек, а строка — коэффициент полинома Жегалкина. Точка на пересечении некоторого столбца и строки означает, что значение функции в данной точке входит в сумму для данного коэффициента полинома (см. рисунок). Назовём эту таблицу T_N, где N — число переменных функции.

Существует закономерность, которая позволяет получить таблицу для функции N переменных, имея таблицу для функции N − 1 переменных. Новая таблица T_N+1 компонуется как матрица 2 × 2 таблиц T_N, причём правый верхний блок матрицы очищается.

Кополиномом Жегалкина называется формула вида

${\displaystyle P(X_{1},\dots ,X_{n})=a\leftrightarrow a_{1}\lor X_{1}\leftrightarrow a_{2}\lor X_{2}\leftrightarrow \dots \leftrightarrow a_{n}\lor X_{n}\leftrightarrow a_{12}\lor X_{1}\lor X_{2}\leftrightarrow a_{13}\lor X_{1}\lor X_{3}\leftrightarrow \ldots \leftrightarrow a_{1\dots n}\lor X_{1}\lor \dots \lor X_{n},}$

${\displaystyle a_{1},\ldots ,a_{1\ldots n}\in \{0,1\},}$

понимаемая с точностью до перестановки операндов у эквиваленции и дизъюнкции. Кополином Жегалкина по сути есть обычный полином над ${\displaystyle \{0,1\}}$, роль умножения в котором играет дизъюнкция, а роль сложения — эквиваленция. Более формально, зададим на множестве ${\displaystyle \{0,1\}}$ структуру поля следующим образом: за умножение поля возьмём дизъюнкцию, за сложение — эквиваленцию. Тогда кополином Жегалкина будет обычным многочленом над таким полем. При этом, единицей в этом поле будет ${\displaystyle 0}$, а нулём — ${\displaystyle 1}$.

Несмотря на то, что с точки зрения теории булевых функций эти две нормальные формы равнозначны, кополином Жегалкина используется значительно реже, чем полином. Связано это с тем, что в стандартных обозначениях элементов булева множества и поля из двух элементов через ${\displaystyle 0}$ и ${\displaystyle 1}$ полиному Жегалкина соответствует обычный многочлен над полем, тогда как для кополинома Жегалкина требуется переобозначение элементов (${\displaystyle 0}$ становится единицей поля, а ${\displaystyle 1}$ — нулём).

Кополином Жегалкина — двойственная нормальная форма к полиному Жегалкина. Поэтому для его построения могут применяться все те же методы, что и для построения обычного полинома Жегалкина, видоизменённые в соответствии с двойственностью. Также, по принципу двойственности, задача построения кополинома Жегалкина может быть сведена к задаче построения полинома Жегалкина. Делается это следующим образом. Пусть нужно построить кополином Жегалкина для функции ${\displaystyle f}$. Делаем следующее:

1. Строим полином Жегалкина для двойственной функции ${\displaystyle f^{*}}$;
2. Заменяем все конъюнции на дизъюнкции, а сложения по модулю 2 — на эквиваленции. Получили кополином Жегалкина для ${\displaystyle f}$.

Аналогичным алгоритмом можно получить обычный полином Жегалкина из кополинома для двойственной функции, поменяв операции на двойственные. Ещё один способ перехода между полиномами и кополиномами Жегалкина — использование свойств булевых функций.

Для перехода от полинома к кополиному:

• ${\displaystyle x\oplus y=0\leftrightarrow x\leftrightarrow y}$
• ${\displaystyle x\land y=x\leftrightarrow y\leftrightarrow (x\lor y)}$
• ${\displaystyle x\leftrightarrow x=1}$
• ${\displaystyle x\leftrightarrow 1=x}$
• эквиваленция чётного числа ${\displaystyle 0}$ равна ${\displaystyle 1}$
• эквиваленция нечётного числа ${\displaystyle 0}$ равна ${\displaystyle 0}$

Для перехода от кополинома к полиному:

• ${\displaystyle x\leftrightarrow y=1\oplus x\oplus y}$
• ${\displaystyle x\lor y=x\oplus y\oplus (x\land y)}$
• ${\displaystyle x\oplus x=0}$
• ${\displaystyle x\oplus 0=x}$
• сумма по модулю 2 чётного числа ${\displaystyle 1}$ равна ${\displaystyle 0}$
• сумма по модулю 2 нечётного числа ${\displaystyle 1}$ равна ${\displaystyle 1}$^[4]

• Алгебра Жегалкина

• Яблонский С. В. Введение в дискретную математику. — М.: Наука. — 1986
• Марченков С. С. Замкнутые классы булевых функций. — М.: Физматлит. — 2000
• Супрун В. П. Основы теории булевых функций. — М.: Ленанд / URSS. — 2017.
• Рагимханов В. Р. Дискретная математика. Часть IV. Булевы функции.. — Махачкала: ДГУ, 2019. — 102 с.