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

Полином Жегалкина — полином(многочлен) над $Z_2$, то есть полином с коэффициентами вида 0 и 1, где в качестве произведения берется конъюнкция, а в качестве сложения исключающее или. Полином был предложен в 1927 году И. И. Жегалкиным в качестве удобного средства для представления функций булевой логики.

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

$P(X_1...X_n) = a ~\oplus~ a_1 X_1 ~\oplus~ a_2 X_2 ~\oplus~ ... ~\oplus~ a_n X_n ~\oplus~ a_{12} X_1 X_2 ~\oplus~ a_{13} X_1 X_3 ~\oplus~ ... ~\oplus~ a_{1...n} X_1...X_n,$

$a \ldots a_{1 \ldots n} \in \{0,1\} .$

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

$P = a \oplus \bigoplus_{ \begin{array}{c} 1\leq i_1< \ldots<i_k\leq n \\ k\in\overline{0,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\}.$

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

$P = B \oplus AB;$

$P = X \oplus YZ \oplus ABX \oplus ABDYZ;$

$P = 1 \oplus A \oplus ABD.$

Предпосылки

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

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

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

Cуществование и единственность представления (теорема Жегалкина)

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

Представление функции в виде полинома Жегалкина

С помощью эквивалентных преобразований ДНФ

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

$A \vee B = A \oplus B \oplus AB;$

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

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

$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) =$

$= XY \oplus XY \oplus X \oplus Y \oplus 1 = X \oplus Y \oplus 1.$

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

$A \oplus A = 0;$

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

С помощью эквивалентных преобразований СДНФ

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

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

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

С помощью карты Карно

В качестве примера преобразуем в полином Жегалкина логическую функцию трёх переменных 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 и т.д.
• Если в верхней строке какого-либо столбца стоит единица, то соответствующий член присутствует в полиноме Жегалкина.

Пример преобразования таблицы истинности в полином Жегалкина для функции трёх переменных P(A,B,C) показан на рисунке.

Процедура преобразования

Ниже приведена паскаль-функция (Delphi 6.0), преобразующая таблицу истинности в полином Жегалкина. Входным параметром процедуры является текстовая строка, в которой закодирована таблица истинности функции (перечисляются значения функции по строкам таблицы истинности, например '10101001'). Функция возвращает полином Жегалкина в виде текстовой строки, где переменные обозначены латинскими буквами A, B, C, D... в порядке их следования в таблице истинности, знак операции конъюнкции опущен, операция исключающее ИЛИ обозначена знаком +. Функция использует алгоритм треугольника.

function toZhegalkin(s:string):string;
var i,j,k,L,N,M:integer;
A: array of boolean;
begin
L:=Length(s); if L=0 then exit;
if s[1]='1' then Result:='1';
N:=1;
for i:=1 to 16 do if N>=Length(s) then break else N:=N shl 1;
M:=i-1;
SetLength(A,N);
for i:=0 to N-1 do A[i]:=false;
for i:=1 to Length(s) do if s[i]='1' then A[i-1]:=true;
for i:=1 to N-1 do begin
 for j:=0 to N-2 do A[j]:=A[j] xor A[j+1];
 if A[0] then begin
   Result:=Result+'+'; j:=N; k:=M;
   while j>0 do begin
     if i and j >0 then Result:=Result+char(64-k+M);
     j:=j div 2;dec(k);
   end;
 end;
end;
end;

Тот же алгоритм на C#

static string toZhegalkin(string s)
        {
            if (s.Length == 0)
                return string.Empty;
            int N = 1, M = 0;
            string buffer = "";
            if (s[0] == '1')
                buffer += s[0];
            for (int i = 1; i < 16; i++)
            {
                if (N >= s.Length)
                    break;
                else
                    N = N << 1;
                M++;
            }
            bool[] A = new bool[N];
            for (int i = 0; i < N; i++)
                A[i] = (s[i] == '1') ? true : false;
            for (int i = 1; i <= N - 1; i++)
            {
                for (int j = 0; j < N - 1; j++)
                    A[j] ^= A[j + 1];
                if (A[0])
                {
                    buffer += '+';
                    for (int j = N, k = M; j > 0; j /= 2, k--)
                    {
                        if ((i & j) > 0)
                        {
                            buffer += (char)(64 - k + M);
                        }
                    }
                }
            }
            return buffer.ToString();
        }

Пример вызова функции: Delphi

writeln(toZhegalkin('10101001'));

C#

Console.WriteLine(toZhegalkin("10101001"));

Результат:

1+C+AB

Литература

• Яблонский С. В. Введение в дискретную математику. — М.: Наука. — 1986
• Марченков С. С. Замкнутые классы булевых функций. — М.: Физматлит. — 2000