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

По сравнению с ДНФ в полиноме Жегалкина отсутствуют операции ИЛИ и НЕ. Таким образом, полином Жегалкина можно получить из ДНФ, выразив операции ИЛИ и НЕ через операции сложение по модулю два, и константу 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, причём правый верхний блок матрицы очищается.