Полином Жегалкина. Теорема о представлении в виде полинома Жегалкина

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

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

Полином Жегалкина представляет собой сумму по модулю два произведений неинвертированных переменных, а также { если необходимо } константы

Формально полином Жегалкина можно представить в виде

$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\ } .$

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

${\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}.}$

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

• $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$ является полной:

На основе этой системы и строятся полиномы Жегалкина.

Существование и единственность представления { теорема Жегалкина }

**Теорема Жегалкина:**Каждая булева функция единственным образом представляется в виде полинома Жегалкина.

Заметим, что различных булевых функций от $n$ переменных $2^ { 2^n }$ штук. При этом конъюнкций вида $x\_ { i\_1 } \ldots x\_ { i\_k }$ существует ровно $2^n$, так как из $n$ возможных сомножителей каждый или входит в конъюнкцию, или нет. В полиноме у каждой такой конъюнкции стоит $0$ или $1$, то есть существует $2^ { 2^n }$ различных полиномов Жегалкина от $n$ переменных.

Теперь достаточно лишь доказать, что различные полиномы реализуют различные функции. Предположим противное. Тогда приравняв два различных полинома и перенеся один из них в другую часть равенства, получим полином, тождественно равный нулю и имеющий ненулевые коэффициенты. Тогда рассмотрим слагаемое с единичным коэффициентом наименьшей длины, то есть с наименьшим числом переменных, входящих в него { любой один, если таких несколько } . Подставив единицы на места этих переменных, и нули на места остальных, получим, что на этом наборе только одно это слагаемое принимает единичное значение, то есть нулевая функция на одном из наборов принимает значение 1. Противоречие. Значит, каждая булева функция реализуется полиномом Жегалкина единственным образом.

Построение полинома Жегалкина

Существует несколько способов построения полинома Жегалкина.

По таблице истинности

Пусть для функции $f(x\_1,x\_2,\dots,x\_n)$ задана таблица истинности. Запишем сначала данную функцию в виде полинома Жегалкина с неопределёнными коэффициентами. Затем по очереди подставляем всевозможные наборы в порядке увеличения количества единиц и находим коэффициенты с учётом того, что $a \oplus 1 = \bar { a }$, а $a \oplus 0 = a$. За каждую подстановку находим только один коэффициент.

**Пример:**Дана функция $f(x\_1,x\_2,x\_3,x\_4)$ и её таблица истинности:

Построим для неё полином Жегалкина:

$f(x\_1,x\_2,x\_3,x\_4) = a\_ { 0000 } \oplus a\_ { 1000 } x\_1 \oplus a\_ { 0100 } x\_2 \oplus a\_ { 0010 } x\_3 \oplus a\_ { 0001 } x\_4 \oplus a\_ { 1100 } x\_1 x\_2 \oplus a\_ { 1010 } x\_1 x\_3 \oplus a\_ { 1001 } x\_1 x\_4 \oplus \\ \oplus a\_ { 0110 } x\_2 x\_3 \oplus a\_ { 0101 } x\_2 x\_4 \oplus a\_ { 0011 } x\_3 x\_4 \oplus a\_ { 1110 } x\_1 x\_2 x\_3 \oplus a\_ { 1101 } x\_1 x\_2 x\_4 \oplus \\ \oplus a\_ { 1011 } x\_1 x\_3 x\_4 \oplus a\_ { 0111 } x\_2 x\_3 x\_4 \oplus a\_ { 1111 } x\_1 x\_2 x\_3 x\_4$

Так как $f(0,0,0,0) = 0$, то $a\_ { 0000 } = 0$.

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

$f(1,0,0,0) = a\_ { 0000 } \oplus a\_ { 1000 } = 1 \Rightarrow a\_ { 1000 } = 1$

$f(0,1,0,0) = a\_ { 0000 } \oplus a\_ { 0100 } = 0 \Rightarrow a\_ { 0100 } = 0$

$f(0,0,1,0) = a\_ { 0000 } \oplus a\_ { 0010 } = 0 \Rightarrow a\_ { 0010 } = 0$

$f(0,0,0,1) = a\_ { 0000 } \oplus a\_ { 0001 } = 0 \Rightarrow a\_ { 0001 } = 0$

$f(1,1,0,0) = a\_ { 0000 } \oplus a\_ { 1000 } \oplus a\_ { 0100 } \oplus a\_ { 1100 } = 1 \Rightarrow a\_ { 1100 } = 0$

$f(1,0,1,0) = a\_ { 0000 } \oplus a\_ { 1000 } \oplus a\_ { 0100 } \oplus a\_ { 1010 } = 0 \Rightarrow a\_ { 1010 } = 1$

$f(1,0,0,1) = a\_ { 0000 } \oplus a\_ { 1000 } \oplus a\_ { 0100 } \oplus a\_ { 1001 } = 0 \Rightarrow a\_ { 1001 } = 1$

$f(0,1,1,0) = a\_ { 0000 } \oplus a\_ { 0100 } \oplus a\_ { 0010 } \oplus a\_ { 0110 } = 1 \Rightarrow a\_ { 0110 } = 1$

$f(0,1,0,1) = a\_ { 0000 } \oplus a\_ { 0100 } \oplus a\_ { 0001 } \oplus a\_ { 0101 } = 0 \Rightarrow a\_ { 0101 } = 0$

$f(0,0,1,1) = a\_ { 0000 } \oplus a\_ { 0010 } \oplus a\_ { 0001 } \oplus a\_ { 0011 } = 0 \Rightarrow a\_ { 0011 } = 0$

$f(1,1,1,0) = a\_ { 0000 } \oplus a\_ { 1000 } \oplus a\_ { 0100 } \oplus a\_ { 0010 } \oplus a\_ { 1100 } \oplus a\_ { 1010 } \oplus a\_ { 0110 } \oplus a\_ { 1110 } = 1 \Rightarrow a\_ { 1110 } = 0$

$f(1,1,0,1) = a\_ { 0000 } \oplus a\_ { 1000 } \oplus a\_ { 0100 } \oplus a\_ { 0001 } \oplus a\_ { 1100 } \oplus a\_ { 1001 } \oplus a\_ { 0101 } \oplus a\_ { 1101 } = 0 \Rightarrow a\_ { 1101 } = 0$

$f(1,0,1,1) = a\_ { 0000 } \oplus a\_ { 1000 } \oplus a\_ { 0010 } \oplus a\_ { 0001 } \oplus a\_ { 1010 } \oplus a\_ { 1001 } \oplus a\_ { 0011 } \oplus a\_ { 1011 } = 1 \Rightarrow a\_ { 1011 } = 0$

$f(0,1,1,1) = a\_ { 0000 } \oplus a\_ { 0100 } \oplus a\_ { 0010 } \oplus a\_ { 0001 } \oplus a\_ { 0110 } \oplus a\_ { 0101 } \oplus a\_ { 0011 } \oplus a\_ { 0111 } = 0 \Rightarrow a\_ { 0111 } = 1$

$f(1,1,1,1) = a\_ { 0000 } \oplus a\_ { 1000 } \oplus a\_ { 0100 } \oplus a\_ { 0010 } \oplus a\_ { 0001 } \oplus a\_ { 1100 } \oplus a\_ { 1010 } \oplus a\_ { 1001 } \oplus a\_ { 0110 } \oplus a\_ { 0101 } \oplus a\_ { 0011 } \oplus \\ \oplus a\_ { 1110 } \oplus a\_ { 1101 } \oplus a\_ { 1011 } \oplus a\_ { 0111 } \oplus a\_ { 1111 } = 0 \Rightarrow a\_ { 1111 } = 1$

Таким образом, полином Жегалкина выглядит так:

$f(x\_1,x\_2,x\_3,x\_4) = x\_1 \oplus x\_1 x\_3 \oplus x\_1 x\_4 \oplus x\_2 x\_3 \oplus x\_2 x\_3 x\_4 \oplus x\_1 x\_2 x\_3 x\_4$

Преобразование дизъюнктивной нормальной формы

Этот способ основан на том, что $X \oplus 1 = \bar { X }$. Если функция задана в виде ДНФ, то можно сначала убрать дизъюнкцию, используя правило Де-Моргана, а все отрицания заменить прибавлением единицы по модулю два, после чего раскрыть скобки по обычным правилам, при этом учитывая, что четное число одинаковых слагаемых равно нулю { так как $X \oplus X = 0$ } , а нечетное число одинаковых слагаемых равно одному такому слагаемому. Либо же можно заменить дизъюнкцию по следующему правилу:

$A \lor B = AB \oplus A \oplus B$   $(1)$.

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

**Пример:**Дана функция в ДНФ $f(x\_1,x\_2,x\_3,x\_4) = (x\_1 \land x\_2 \land \neg x\_3 \land x\_4) \lor (\neg x\_1 \land \neg x\_4) \lor (x\_1 \land x\_2) \lor x\_2$, построим полином Жегалкина.

Запишем функцию так:

$f(x\_1,x\_2,x\_3,x\_4) = x\_1 x\_2 \neg x\_3 x\_4 + \neg x\_1 \neg x\_4 + x\_1 x\_2 + x\_2$;

Сгруппируем слагаемые и воспользуемся преобразованием (1):

$f(x\_1,x\_2,x\_3,x\_4) = (x\_1 x\_2 \neg x\_3 x\_4 \oplus \neg x\_1 \neg x\_4 \oplus x\_1 x\_2 \neg x\_3 x\_4 \neg x\_1 \neg x\_4) + (x\_1 x\_2 \oplus x\_2 \oplus \oplus x\_1 x\_2 x\_2)$

Воспользуемся свойствами конъюнкции $A \land A = A$ и $\neg A \land A = 0$, а также тем, что $A \oplus A = 0$, и упростим выражение:

$f(x\_1,x\_2,x\_3,x\_4) = (x\_1 x\_2 \neg x\_3 x\_4 \oplus \neg x\_1 \neg x\_4) + x\_2$

Ещё раз воспользуемся преобразованием (1):

$f(x\_1,x\_2,x\_3,x\_4) = x\_1 x\_2 \neg x\_3 x\_4 \oplus \neg x\_1 \neg x\_4 \oplus x\_2 \oplus (x\_1 x\_2 \neg x\_3 x\_4 \oplus \neg x\_1 \neg x\_4) x\_2$

Раскроем скобку по алгебраическим правилам:

$f(x\_1,x\_2,x\_3,x\_4) = x\_1 x\_2 \neg x\_3 x\_4 \oplus \neg x\_1 \neg x\_4 \oplus x\_2 \oplus x\_1 x\_2 x\_2 \neg x\_3 x\_4 \oplus \neg x\_1 x\_2 \neg x\_4$

Снова воспользуемся свойствами конъюнкции и исключающего ИЛИ:

$f(x\_1,x\_2,x\_3,x\_4) = \neg x\_1 \neg x\_4 \oplus x\_2 \oplus \neg x\_1 x\_2 \neg x\_4$

Заменим отрицание на прибавление $1$:

$f(x\_1,x\_2,x\_3,x\_4) = (x\_1 \oplus 1) (x\_4 \oplus 1) \oplus x\_2 \oplus (x\_1 \oplus 1) x\_2 (x\_4 \oplus 1)$

Раскроем скобки:

$f(x\_1,x\_2,x\_3,x\_4) = x\_1 x\_4 \oplus x\_1 \oplus x\_4 \oplus 1 \oplus x\_2 \oplus x\_1 x\_2 x\_4 \oplus x\_1 x\_2 \oplus x\_2 x\_4 \oplus x\_2$

Выкинем парные слагаемые и получим окончательную формулу:

$f(x\_1,x\_2,x\_3,x\_4) = x\_1 x\_2 x\_4 \oplus x\_1 x\_2 \oplus x\_1 x\_4 \oplus x\_2 x\_4 \oplus x\_1 \oplus x\_4 \oplus 1$

Метод треугольника

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

1. Строится полная таблица истинности, в которой строки идут в порядке возрастания двоичных кодов от $000\dots00$ до $111\dots11$.

2. Строится вспомогательная треугольная таблица, в которой первый столбец совпадает со столбцом значений функции в таблице истинности.

3. Ячейка в каждом последующем столбце получается путём сложения по модулю 2 двух ячеек предыдущего столбца — стоящей в той же строке и строкой ниже.

4. Столбцы вспомогательной таблицы нумеруются двоичными кодами в том же порядке, что и строки таблицы истинности.

5. Каждому двоичному коду ставится в соответствие один из членов полинома Жегалкина в зависимости от позиций кода, в которых стоят единицы. Например, ячейке $111$ соответствует член $ABC$, ячейке $101$ — член $AC$, ячейке $010$ — член $B$, ячейке $000$ — член $1$ и т.д.

6. Если в верхней строке какого-либо столбца стоит единица, то соответствующий член присутствует в полиноме Жегалкина.

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

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

Чтобы получить формулу, по которой рассчитывается какой-либо коэффициент, нужно из клетки, в которой он записан, пройтись всеми возможными путями влево, до столбца $''P''$ таблицы истинности, делая ходы влево и влево-вниз, записать значения в конечных ячейках и сложить их все между собой по модулю 2.

Таким образом, в первом столбце сверху записан коэффициент $a\_0 = P(0,0,0)$,

во втором — $a\_1 = P(0,0,0) \oplus P(0,0,1)$,

в третьем — $a\_2 = P(0,0,0) \oplus P(0,0,1) \oplus P(0,0,1) \oplus P(0,1,0) = P(0,0,0) \oplus P(0,1,0)$,

в четвёртом —

$a\_3 = P(0,0,0) \oplus P(0,0,1) \oplus P(0,0,1) \oplus P(0,0,1) \oplus P(0,1,0) \oplus P(0,1,0) \oplus P(0,1,0) \oplus P(0,1,1) = \\ = P(0,0,0) \oplus P(0,1,0) \oplus P(0,1,0) \oplus P(0,1,1),$

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

Преобразование Мёбиуса

Пусть задана булева функция $f: B^n \rightarrow B, ;; B=\ { 0; 1 \ }$.

Любая булева функция представима в виде полинома Жегалкина, притом единственным образом.

Пусть $i = (i\_1, i\_2, .. i\_n), ;; i\_k \in \ { 0 ; 1\ }$, и введем обозначение $x^{i_k} \sim \begin{cases} x, & \text{if } i_k = 1 \\ 1, & \text{if } i_k = 0 \end{cases}$

Тогда полином Жегалкина можно записать как:

$f(x) = \bigoplus\limits\_i \alpha\_i \cdot x\_1^ { i\_1 } \cdot x\_2^ { i\_2 } \cdot$$\dots$$\cdot x\_n^ { i\_n }$, где $\alpha\_i \in \ { 0; 1 \ }$.

Множество коэффициентов $\ { \alpha \_i\ }$ можно рассматривать как функцию $\alpha$, заданной на множестве индексов $i = (i\_1, i\_2, \dots i\_n)$, то есть $\alpha: i \mapsto \alpha\_i$.

Очевидно, функцию $f$ можно записать и следующим образом: $f(x) = \bigoplus \limits\_i \alpha\_i \cdot [x\_1 , ;$ если $;; i\_1] \cdot [x\_2 , ;$ если $;; i\_2] \cdot$$\dots$$\cdot [x\_n , ;$ если $;; i\_n]$.

Тут запись $[x\_k , ;$ если $; i\_k]$ означает, что элелемент $x\_k$ присутствует в соответствующем члене полинома только если $i\_k = 1$.

Тогда если для какого-то $x$, $i \succ x$* ,то в слагаемом будет существовать хотя бы один множитель, равный нулю, и такое слагаемое на сумму не повлияет.

Отсюда ясно, что $f(x) = \bigoplus \limits\_ { i \preceq x } \alpha\_i$  $(2)$

Найдем отображение $f \mapsto \alpha$ { То есть такое, которое по заданной функции вычисляет значения всех коэффициентов } .

$*$ $i \succ x$ обозначает, что $x$ "меньше" $i$ как последовательность бит

**Теорема:**Пусть задана функция $f$. Тогда функцию $\alpha\_x$ можно найти по формуле: $\alpha\_x = \bigoplus \limits\_ { j\preceq x } f(j)$ (3)

Докажем при помощи индукции по количеству единиц в векторе $x$ { иначе говоря, по сумме $x\_1+x\_2+\dots +x\_n$ } и для удобства обозначим это количество единиц { сумму } $wt(x)$.

1) База: если $x = 0$, то, очевидно $f(0) = \alpha\_0$

2) Пускай теорема справедлива для всех сумм $wt(x) < k$. Покажем, что в таком случае она верна и для $wt(x) = k$. По $(2)$, а далее по предположению индукции видим: $f(x) = \bigoplus \limits\_ { i \preceq x } \alpha\_i = \left[ \bigoplus \limits\_ { i \prec x } \bigoplus \limits\_ { j\preceq i } f(j) \right] \oplus \alpha\_x$ .

Рассмотрим сумму $\left[ \bigoplus \limits\_ { i \prec x } \bigoplus \limits\_ { j\preceq i } f(j) \right]$. Каждый элемент $f(j)$ содержится в ней, только если $j \prec x$, и для фиксированных $j, x$ элемент $f(j)$ встречается ровно столько раз, сколько существует $i$ , таких, что $j \prec i \prec x$. Несложно увидеть, что таких $i$ существует ровно $2^ { wt(x)-wt(j) } -1$, то есть нечетное количество раз. Тогда $\left[ \bigoplus \limits\_ { i \prec x } \bigoplus \limits\_ { j\preceq i } f(j) \right] = \bigoplus \limits\_ { j\prec x } f(j)$.

Но тогда $f(x) = \left[ \bigoplus \limits\_ { j\prec x } f(j) \right] \oplus \alpha\_x \Leftrightarrow f(x) \oplus \bigoplus \limits\_ { j\prec x } f(j) = \alpha\_x \Leftrightarrow \alpha\_x = \bigoplus \limits\_ { j\preceq x } f(j)$.

То есть при $wt(x) = k$ формула также выполняется, значит при любых $x$ выполняется $\alpha\_x = \bigoplus \limits\_ { j\preceq x } f(j)$.

Отображение $f \rightarrow \alpha$ также называется преобразованием Мёбиуса.

Видно, что $(2)$ и $(3)$ — это одно и тоже преобразование. Значит, если применить преобразование Мёбиуса к функции, а затем вновь применить то же преобразование к получившейся функции, тогда вновь получим исходную функцию $f$. То есть преобразование Мёбиуса обратно самому себе, иными словами, является инволюцией.