Как найти полином Жегалкина: решение по шагам

Дано: булева функция $f(x, y, z)$ задана вектором значений 10011110, наборы идут в порядке 000, 001, 010, ..., 111. Найти: полином Жегалкина функции и ответ на вопрос, линейна ли она.

Полином Жегалкина - это запись функции через сложение по модулю два и конъюнкцию, без отрицаний и дизъюнкций. Считать его удобнее всего треугольником Паскаля: под вектором значений выстраиваются строки поразрядных сумм по модулю два, а коэффициенты снимаются с левого края готового треугольника. Ответ: $f = 1 \oplus y \oplus z \oplus xy \oplus xz \oplus xyz$, степень полинома равна 3, функция нелинейна. Калькулятор сверху строит тот же треугольник для любого вектора, а ниже каждый шаг разобран руками.

Решение по шагам

Шаг 1. Раскладываем вектор по наборам. Переменных три, поэтому наборов $2^3 = 8$, и разряды вектора читаются сверху вниз в порядке двоичных чисел: нулевой разряд отвечает набору 000, последний - набору 111. Старший бит номера набора - это переменная $x$, младший - $z$.

Если функция дана не вектором, а таблицей или формулой, сначала получают именно этот столбец значений: порядок заполнения наборов подробно разобран в задаче как построить таблицу истинности.

Шаг 2. Строим треугольник Паскаля. Верхняя строка треугольника - сам вектор значений. Каждая следующая строка получается из предыдущей поразрядным сложением соседей по модулю два: берём первый и второй элементы, складываем, потом второй и третий, и так до конца. Строка при этом становится короче на один элемент, поэтому через восемь шагов от вектора остаётся одно число.

Проверять себя тут легко: сложение по модулю два - это «равно нулю, если цифры одинаковые, и единице, если разные». Первая строка треугольника, например, начинается с $1 \oplus 0 = 1$, потом идёт $0 \oplus 0 = 0$, затем $0 \oplus 1 = 1$.

Шаг 3. Сопоставляем коэффициентам мономы. Коэффициенты стоят в левом столбце, их читают сверху вниз. Номер строки, записанный в двоичном виде, прямо указывает состав монома: единичные разряды номера - это переменные, которые входят в слагаемое. Строка 5 в двоичной записи даёт 101, то есть единицы стоят на местах $x$ и $z$, и коэффициент этой строки относится к моному $xz$. Нулевая строка не содержит ни одной единицы, значит её коэффициент - свободный член.

Шаг 4. Собираем полином. В левом столбце единицы оказались в строках 0, 1, 2, 5, 6 и 7, а нули - в строках 3 и 4. Значит, мономы $yz$ и $x$ в ответ не входят, а остальные шесть складываются по модулю два:

$$f(x, y, z) = 1 \oplus y \oplus z \oplus xy \oplus xz \oplus xyz.$$

Порядок слагаемых произволен: сложение по модулю два коммутативно, поэтому запись обычно упорядочивают по возрастанию степени монома, как здесь.

Шаг 5. Проверяем подстановкой. Полином обязан давать исходный вектор, и проверка занимает минуту, если подставлять «крайние» наборы. На наборе 000 все мономы с переменными обнуляются и остаётся свободный член: $f = 1$, что совпадает с первым разрядом вектора. На наборе 111 работают все шесть слагаемых: $1 \oplus 1 \oplus 1 \oplus 1 \oplus 1 \oplus 1 = 0$, и последний разряд вектора тоже нулевой. Для надёжности берут ещё один набор со смешанными значениями, скажем 101: остаются слагаемые $1$, $z$ и $xz$, их сумма $1 \oplus 1 \oplus 1 = 1$, а в векторе на пятой позиции стоит единица.

Шаг 6. Отвечаем про линейность. Функция линейна тогда и только тогда, когда в её полиноме Жегалкина нет мономов длиннее одной переменной. Здесь есть $xy$, $xz$ и $xyz$, поэтому условие нарушено. Степень полинома - это длина самого длинного монома, у нас это $xyz$, то есть степень 3.

Ответ: $f(x, y, z) = 1 \oplus y \oplus z \oplus xy \oplus xz \oplus xyz$; степень полинома 3, функция нелинейна и классу $L$ не принадлежит.

Формула и откуда она берётся

Полином Жегалкина от $n$ переменных - это сумма по модулю два произведений переменных без повторений, взятых с коэффициентами 0 или 1:

$$f(x_1, \dots, x_n) = a_0 \oplus \bigoplus_{i} a_i x_i \oplus \bigoplus_{i < j} a_{ij} x_i x_j \oplus \dots \oplus a_{12\ldots n} x_1 x_2 \ldots x_n.$$

Существование такой записи доказывается конструктивно. Любую функцию можно записать формулой через отрицание, конъюнкцию и дизъюнкцию, а эти операции выражаются через $\oplus$ и $\wedge$: $\neg x = x \oplus 1$ и $x \vee y = x \oplus y \oplus xy$. Подставляем замены, раскрываем скобки и сокращаем одинаковые слагаемые по правилам $x \oplus x = 0$ и $x \cdot x = x$ - остаётся полином нужного вида.

Единственность следует из подсчёта. Мономов ровно $2^n$ (каждое подмножество переменных даёт свой), коэффициенты независимы, значит различных полиномов $2^{2^n}$ - ровно столько же, сколько булевых функций от $n$ переменных. Отображение «полином - функция» сюръективно, а множества равномощны, поэтому оно взаимно однозначно: у каждой функции полином Жегалкина ровно один.

Коэффициент при мономе выражается напрямую через значения функции. Обозначим набор индексов монома через маску $\alpha$; тогда

$$a_{\alpha} = \bigoplus_{\beta \subseteq \alpha} f(\beta),$$

то есть складываются значения функции на всех наборах, которые «вкладываются» в $\alpha$ по единицам. Это преобразование Мёбиуса, и треугольник Паскаля вычисляет именно его. Элемент строки $k$ на нулевой позиции равен сумме $f(j)$, взятых с биномиальными коэффициентами $\binom{k}{j} \bmod 2$, а по теореме Люка $\binom{k}{j}$ нечётен ровно тогда, когда $j$ - подмаска $k$. Отсюда и совпадение: левый край строки $k$ есть коэффициент при мономе с номером $k$.

Метод неопределённых коэффициентов

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

$$f(x, y, z) = a_0 \oplus a_1 x \oplus a_2 y \oplus a_3 z \oplus a_4 xy \oplus a_5 xz \oplus a_6 yz \oplus a_7 xyz.$$

Набор 000 обнуляет всё, кроме свободного члена, поэтому $a_0 = f(0,0,0) = 1$ сразу. На наборах с одной единицей выживают свободный член и один линейный моном: из $f(1,0,0) = 1$ получаем $1 \oplus a_1 = 1$, то есть $a_1 = 0$; аналогично $f(0,1,0) = 0$ даёт $a_2 = 1$, а $f(0,0,1) = 0$ даёт $a_3 = 1$.

Наборы с двумя единицами добавляют по одному парному моному к уже известным величинам. Из $f(1,1,0) = 1$ следует $a_0 \oplus a_1 \oplus a_2 \oplus a_4 = 1$, подставляем найденное и получаем $a_4 = 1$. Точно так же $f(1,0,1) = 1$ приводит к $a_5 = 1$, а $f(0,1,1) = 1$ - к $a_6 = 0$. Последний набор 111 включает все слагаемые: сумма известных семи коэффициентов равна 1, а значение функции равно 0, поэтому $a_7 = 1$.

Итог совпадает с треугольником: $f = 1 \oplus y \oplus z \oplus xy \oplus xz \oplus xyz$. Метод медленнее, но нагляднее и полезен, когда нужно найти всего один-два коэффициента, а не весь полином. Порядок подстановки менять нельзя: каждый следующий набор обязан добавлять ровно одно новое неизвестное, иначе уравнение не решится в одно действие.

Если функция задана формулой, а не вектором

Когда дана готовая формула, таблицу можно не строить: достаточно подставить тождества $\neg x = x \oplus 1$, $x \vee y = x \oplus y \oplus xy$ и $x \rightarrow y = 1 \oplus x \oplus xy$, после чего раскрыть скобки. Работать при этом нужно по обычным правилам алгебры, но с двумя поправками: одинаковые слагаемые уничтожаются парами, а степень переменной всегда падает до первой.

Возьмём импликацию как пример. Замена даёт $x \rightarrow y = \neg x \vee y = (1 \oplus x) \vee y$, а дизъюнкция раскрывается в $(1 \oplus x) \oplus y \oplus (1 \oplus x)y = 1 \oplus x \oplus y \oplus y \oplus xy$. Слагаемые $y$ и $y$ сокращаются, остаётся $1 \oplus x \oplus xy$ - этот вариант есть среди чипов калькулятора сверху, и треугольник даёт для него тот же ответ. Путь через формулу короче, если исходная запись компактна, и заметно длиннее, если в ней много вложенных дизъюнкций: тогда проще выписать вектор значений и вернуться к треугольнику.

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

Частые ошибки

• Путают порядок переменных в наборе. Если вектор выписан для порядка $z, y, x$, треугольник даст верные коэффициенты, но отнесёт их к другим мономам. Порядок фиксируют один раз и держат до конца задачи.
• Складывают соседей обычным сложением. В строке треугольника допустимы только 0 и 1: результат $1 + 1$ равен нулю, а не двойке.
• Снимают коэффициенты с правого края или с последней строки. Ответ даёт только левый столбец, прочитанный сверху вниз.
• Теряют степень при раскрытии скобок. Произведение $x \cdot x$ равно $x$, а не $x^2$: в булевой алгебре квадратов не бывает.
• Забывают сократить повторяющиеся слагаемые. Пара одинаковых мономов даёт ноль, и если её не убрать, полином перестанет быть единственным представлением функции.
• Считают линейной функцию с большим числом слагаемых. Линейность определяется длиной мономов, а не их количеством: $x \oplus y \oplus z \oplus 1$ линейна, а короткое $xy$ уже нет.

FAQ

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

Можно ли получить полином Жегалкина после упрощения формулы? Да, и это часто быстрее: чем короче исходная запись, тем меньше скобок придётся раскрывать. Сначала сводят формулу к компактному виду, как в разборе про упрощение логических выражений, и только потом подставляют тождества для отрицания и дизъюнкции.

Зачем вообще проверять линейность? Линейные функции образуют замкнутый класс $L$ - один из пяти предполных классов в критерии Поста. Система функций полна тогда и только тогда, когда она не вкладывается целиком ни в один из этих классов, и полином Жегалкина отвечает на вопрос про $L$ мгновенно. Подробный разбор самих классов есть в материале про классы Поста.

Что делать с функцией от четырёх и более переменных? Схема не меняется, растёт только размер: вектор длины 16 даёт треугольник из шестнадцати строк, а мономов становится 16. Руками это ещё считается, а начиная с пяти переменных удобнее быстрое преобразование Мёбиуса, которое делает то же самое за $n \cdot 2^{n-1}$ операций вместо квадратичного перебора.

Коротко

1. Выписать вектор значений функции в порядке наборов 000, 001, ..., 111; для трёх переменных это восемь разрядов.
2. Построить треугольник Паскаля: каждая следующая строка - поразрядные суммы соседей по модулю два, длина строки уменьшается на единицу.
3. Снять коэффициенты с левого столбца сверху вниз; номер строки в двоичной записи указывает, какие переменные входят в моном.
4. Для вектора 10011110 получается $f = 1 \oplus y \oplus z \oplus xy \oplus xz \oplus xyz$; проверка подстановкой наборов 000, 101 и 111 даёт 1, 1 и 0, как в исходном векторе.
5. Степень полинома равна 3, мономы $xy$, $xz$ и $xyz$ длиннее одной переменной, поэтому функция нелинейна и в класс $L$ не входит.