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

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

[math]P = a_{0} \oplus a_{1} x_{1} \oplus a_{2} x_{2} \oplus ... \oplus a_{n} x_{n} \oplus a_{n+1} x_{1} x_{2} \oplus ... \oplus a_{..n + C _{n}^2} x_{n-1} x_{n} \oplus ... \oplus a_{2^n-1} x_{1} x_{2} .. x_{n} [/math]

Предпосылки

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

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

Исходя из этого, система функций [math]\bigl\langle \wedge, \oplus, 1 \bigr\rangle[/math] является полной, так как в ней:

1. Не сохраняет 0: [math] 1 [/math];
2. Не сохраняет 1: [math] \oplus [/math];
3. Нелинейна: [math] \wedge [/math];
4. Немонотонна: [math] \oplus [/math];
5. Несамодвойственны: [math] \wedge, \oplus, 1 [/math].

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

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

Теорема (Жегалкина):

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

Доказательство:

[math]\triangleright[/math]

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

[math]\triangleleft[/math]

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

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

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

Пусть для функции [math]f(x_{1},x_{2},..,x_{n})[/math] задана таблица истинности. Запишем сначала данную функцию в виде полинома Жегалкина с неопределёнными коэффициентами. Затем по очереди подставляем всевозможные наборы в порядке увеличения количества единиц и находим коэффициенты. Можно показать, что за каждую подстановку находим только один коэффициент.

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

Этот способ основан на том, что [math] X \oplus 1 = \bar{X} [/math]. Если функция задана в виде ДНФ, то сначала убираем дизъюнкцию, используя при этом правило Де-Моргана, а все отрицания заменяем прибавлением единицы. После этого раскрываем скобки по обычным правилам, при этом учитываем, что четное число одинаковых слагаемых равно нулю (так как [math] X \oplus X = 0 [/math]), а нечетное число одинаковых слагаемых равно одному такому слагаемому.

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

Пусть задана булева функция [math]f: B^n \rightarrow B, \;\; B=\{ 0; 1 \}[/math]. Любая булева функция представима в виде полинома Жегалкина, притом единственным образом.

Пусть [math] i = (i _{1}, i _{2}, .. i _{n}), \;\; i _{k} \in \{0 ; 1\}[/math], и введем обозначение [math] x ^{i _{k}} \sim \left\{\begin{matrix} x, \;\; i _{k}=1 \\ 1, \;\; i _{k}=0 \end{matrix}\right. [/math]  . 

Тогда полином Жегалкина можно записать как: [math] f(x) = \bigoplus\limits_{i} \alpha _{i} \cdot x_{1}^{i_{1}} \cdot x_{2}^{i_{2}} \cdot ... \cdot x_{n}^{i_{n}}[/math], где [math]\alpha _{i} \in \{ 0; 1 \}[/math].

Множество коэффициентов [math]\{\alpha _{i}\}[/math] можно рассматривать как функцию [math]\alpha[/math], заданной на множестве индексов [math] i \in \overline{1..n}[/math], то есть [math]\alpha: i \mapsto \alpha_{i}[/math].

Очевидно, функцию [math] f [/math] можно записать и следующим образом: [math] f(x) = \bigoplus \limits_{i} \alpha _{i} \cdot [x _{1} , \; [/math] если [math] \;\; i _{1}] \cdot [x _{2} , \; [/math] если [math] \;\; i _{2}] \cdot ... \cdot [x _{n} , \; [/math] если [math] \;\; i_{n}][/math].

Тут запись [math][x _{k} , \; [/math] если [math] \; i _{k}][/math] означает, что элелемент [math] x_{k} [/math] присутствует в соответствующем члене полинома только если [math] i_{k} = 1 [/math]. Тогда если для какого-то [math]x[/math], [math]i \succ x[/math] ,то в слагаемом будет существовать хотя бы один множитель, равный нулю, и такое слагаемое на сумму не повлияет. Отсюда ясно, что [math] f(x) = \bigoplus \limits_{i \preceq x} \alpha _{i} [/math].   [math] (1) [/math] Найдем отображение [math] f \mapsto \alpha[/math] (То есть такое, которое по заданной функции вычисляет значения всех коэффициентов).

Теорема:

Пусть задана функция [math] f [/math]. Тогда функцию [math] \alpha_{x} [/math] можно найти по формуле: [math]\alpha _{x} = \bigoplus \limits_{j\preceq x} f(j)[/math]    [math] (2) [/math].

Доказательство:

[math]\triangleright[/math]

Докажем при помощи индукции по количеству единиц в векторе [math] x [/math] ( иначе говоря, по сумме [math]x_{1}+x_{2}+...+x_{n}[/math] ) и для удобства обозначим это количество единиц(сумму) [math] wt(x) [/math]. 1) База: если [math] x = 0 [/math], то, очевидно [math] f(0) = \alpha _{0} [/math] 2) Пускай теорема справедлива для всех сумм [math]wt(x) \lt k[/math]. Покажем, что в таком случае она верна и для [math]wt(x) = k[/math]. По [math] (1) [/math], а далее по предположению индукции видим: [math] 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}[/math] . Рассмотрим сумму [math] \left [ \bigoplus \limits_{i \prec x} \bigoplus \limits_{j\preceq i} f(j) \right ] [/math]. Каждый элемент [math] f(j) [/math] содержится в ней, только если [math] j \preceq x [/math], и для фиксированных [math] j, x [/math] элемент [math] f(j)[/math] встречается ровно столько раз, сколько существует [math] i [/math] , таких, что [math] j \prec i \preceq x[/math]. Несложно увидеть, что таких [math] i [/math] существует ровно [math] 2^{wt(x)-wt(j)}-1 [/math], то есть нечетное количество раз. Тогда [math] \left [ \bigoplus \limits_{i \prec x} \bigoplus \limits_{j\preceq i} f(j) \right ] = \bigoplus \limits_{j\prec x} f(j) [/math]. Но тогда [math] 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)[/math]. То есть при [math]wt(x) = k[/math] формула также выполняется, значит при любых [math] x [/math] выполняется [math]\alpha _{x} = \bigoplus \limits_{j\preceq x} f(j)[/math].

[math]\triangleleft[/math]

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

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

Литература и источники информации

• Cтатистика | Математика НГУ
• Википедия
• Е.Л Рабкин, Ю.Б. Фарфоровская, дискретная математика
• Логачёв О.А, Сальников А.А., Ященко В.В. Булевы фунции в теории кодирования и криптологии — МЦНМО, 2004. - 470с. — ISBN 5-94057-117-4.