Пример построения, взят с википедии

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

2011-10-20T06:43:07Z

Целиков Александр: Вроде бы наконец доделал

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

<tex>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 </tex>
== Предпосылки ==

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

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

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

#Не сохраняет 0: <tex> 1 </tex>;
#Не сохраняет 1: <tex> \oplus </tex>;
#Нелинейна: <tex> \wedge </tex>;
#Немонотонна: <tex> \oplus </tex>;
#Несамодвойственны: <tex> \wedge, \oplus, 1 </tex>.

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

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

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

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

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

=== По таблице истинности ===
Пусть для функции <tex>f(x_1,x_2,..,x_n)</tex> задана таблица истинности. Запишем сначала данную функцию в виде полинома Жегалкина с неопределёнными коэффициентами. Затем по очереди подставляем всевозможные наборы в порядке увеличения количества единиц и находим коэффициенты с учётом того, что <tex> a \oplus 1 = \bar{a}</tex>, а <tex> a \oplus 0 = a</tex>. Можно показать, что за каждую подстановку находим только один коэффициент.

'''Пример:'''
Дана функция <tex>f(x_1,x_2,x_3,x_4)</tex> и её таблица истинности:

{| border=1
|-
!class="dark" style="font-weight:normal"| <tex>x_1</tex>
!class="dark" style="font-weight:normal"| <tex>x_2</tex>
!class="dark" style="font-weight:normal"| <tex>x_3</tex>
!class="dark" style="font-weight:normal"| <tex>x_4</tex>
!class="dark" style="font-weight:normal"| <tex>f(x_1,x_2,x_3,x_4)</tex>
|- align="center"
||0||0||0||0||0
|- align="center"
||0||0||0||1||0
|- align="center"
||0||0||1||0||0
|- align="center"
||0||0||1||1||0
|- align="center"
||0||1||0||0||0
|- align="center"
||0||1||0||1||0
|- align="center"
||0||1||1||0||1
|- align="center"
||0||1||1||1||0
|- align="center"
||1||0||0||0||1
|- align="center"
||1||0||0||1||0
|- align="center"
||1||0||1||0||0
|- align="center"
||1||0||1||1||1
|- align="center"
||1||1||0||0||1
|- align="center"
||1||1||0||1||0
|- align="center"
||1||1||1||0||1
|- align="center"
||1||1||1||1||0
|}
Построим для неё полином Жегалкина:

<tex>f(x_1,x_2,x_3,x_4) = a_0 \oplus a_1 x_1 \oplus a_2 x_2 \oplus a_3 x_3 \oplus a_4 x_4 \oplus a_5 x_1 x_2 \oplus a_6 x_1 x_3 \oplus a_7 x_1 x_4 \oplus a_8 x_2 x_3 \oplus a_9 x_2 x_4 \oplus a_{10} x_3 x_4 \oplus a_{11} x_1 x_2 x_3 \oplus a_{12} x_1 x_2 x_4 \oplus a_{13} x_1 x_3 x_4 \oplus a_{14} x_2 x_3 x_4 \oplus a_{15} x_1 x_2 x_3 x_4</tex>

Так как <tex>f(0,0,0,0) = 0</tex>, то <tex>a_0 = 0</tex>.
Далее подставляем все остальные наборы в порядке возрастания числа единиц, подставляя вновь полученные значения в следующие формулы:

<tex>f(1,0,0,0) = a_0 \oplus a_1 = 1 \Rightarrow a_1 = 1</tex>

<tex>f(0,1,0,0) = a_0 \oplus a_2 = 0 \Rightarrow a_2 = 0</tex>

<tex>f(0,0,1,0) = a_0 \oplus a_3 = 0 \Rightarrow a_3 = 0</tex>

<tex>f(0,0,0,1) = a_0 \oplus a_4 = 0 \Rightarrow a_4 = 0</tex>

<tex>f(1,1,0,0) = a_0 \oplus a_1 \oplus a_2 \oplus a_5 = 1 \Rightarrow a_5 = 0</tex>

<tex>f(1,0,1,0) = a_0 \oplus a_1 \oplus a_2 \oplus a_6 = 0 \Rightarrow a_6 = 1</tex>

<tex>f(1,0,0,1) = a_0 \oplus a_1 \oplus a_2 \oplus a_7 = 0 \Rightarrow a_7 = 1</tex>

<tex>f(0,1,1,0) = a_0 \oplus a_2 \oplus a_3 \oplus a_8 = 1 \Rightarrow a_8 = 1</tex>

<tex>f(0,1,0,1) = a_0 \oplus a_2 \oplus a_4 \oplus a_9 = 0 \Rightarrow a_9 = 0</tex>

<tex>f(0,0,1,1) = a_0 \oplus a_3 \oplus a_4 \oplus a_{10} = 0 \Rightarrow a_{10} = 0</tex>

<tex>f(1,1,1,0) = a_0 \oplus a_1 \oplus a_2 \oplus a_3 \oplus a_5 \oplus a_6 \oplus a_8 \oplus a_{11} = 1 \Rightarrow a_{11} = 0</tex>

<tex>f(1,1,0,1) = a_0 \oplus a_1 \oplus a_2 \oplus a_4 \oplus a_5 \oplus a_7 \oplus a_9 \oplus a_{12} = 0 \Rightarrow a_{12} = 0</tex>

<tex>f(1,0,1,1) = a_0 \oplus a_1 \oplus a_3 \oplus a_4 \oplus a_6 \oplus a_7 \oplus a_{10} \oplus a_{13} = 1 \Rightarrow a_{13} = 0</tex>

<tex>f(0,1,1,1) = a_0 \oplus a_2 \oplus a_3 \oplus a_4 \oplus a_8 \oplus a_9 \oplus a_{10} \oplus a_{14} = 0 \Rightarrow a_{14} = 1</tex>

<tex>f(1,1,1,1) = a_0 \oplus a_1 \oplus a_2 \oplus a_3 \oplus a_4 \oplus a_5 \oplus a_6 \oplus a_7 \oplus a_8 \oplus a_9 \oplus a_{10} \oplus a_{11} \oplus a_{12} \oplus a_{13} \oplus a_{14} = 0 \Rightarrow a_{15} = 1</tex>

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

<tex>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</tex>

=== Преобразование [[Определение_булевой_функции#Дизъюнктивная нормальная форма (ДНФ)|дизъюнктивной нормальной формы]] ===
Этот способ основан на том, что <tex> X \oplus 1 = \bar{X} </tex>. Если функция задана в виде ДНФ, то можно сначала убрать дизъюнкцию, используя правило Де-Моргана, а все отрицания заменить прибавлением единицы, после чего раскрыть скобки по обычным правилам, при этом учитывая, что четное число одинаковых слагаемых равно нулю (так как <tex> X \oplus X = 0 </tex>), а нечетное число одинаковых слагаемых равно одному такому слагаемому. Либо же можно заменить дизъюнкцию по следующему правилу: <tex> A \lor B = AB \oplus A \oplus B </tex>   <tex> (1) </tex>.
Если функция задана в СДНФ, то так как при любых значениях входных переменных в единицу обращается не более одного члена выражения, то достаточно просто заменить все дизъюнкции исключающим ИЛИ.

'''Пример:'''
Дана функция в ДНФ <tex> 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 </tex>, построим полином Жегалкина.

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

<tex>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</tex>;

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

<tex>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 x_1 x_2 x_2)</tex>

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

<tex>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 </tex>

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

<tex>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</tex>

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

<tex>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 </tex>

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

<tex>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 \neg x_1 x_2 \neg x_4 </tex>

Заменим отрицание на прибавление <tex>1</tex>:

<tex>f(x_1,x_2,x_3,x_4) = x_1 x_2 (x_3 \oplus 1) x_4 \oplus (x_1 \oplus 1) (x_4 \oplus 1) \oplus x_2 \oplus (x_1 \oplus 1) x_2 (x_4 \oplus 1)</tex>

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

<tex>f(x_1,x_2,x_3,x_4) = x_1 x_2 x_3 x_4 \oplus x_1 x_2 x_4 \oplus 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</tex>

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

<tex>f(x_1,x_2,x_3,x_4) = x_1 x_2 x_3 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</tex>

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

Пусть <tex> i = (i _1, i _2, .. i_n), \;\; i_k \in \{0 ; 1\}</tex>, и введем обозначение <tex> x ^{i_k} \sim \left\{\begin{matrix} x, \;\; i_k=1
\\ 1, \;\; i_k=0
\end{matrix}\right. </tex>  . 

Тогда полином Жегалкина можно записать как:
<tex> f(x) = \bigoplus\limits_i \alpha_i \cdot x_1^{i_1} \cdot x_2^{i_2} \cdot ... \cdot x_n^{i_n}</tex>, где <tex>\alpha_i \in \{ 0; 1 \}</tex>.

Множество коэффициентов <tex>\{\alpha _i\}</tex> можно рассматривать как функцию <tex>\alpha</tex>, заданной на множестве индексов <tex> i \in \overline{1..n}</tex>, то есть <tex>\alpha: i \mapsto \alpha_i</tex>.

Очевидно, функцию <tex> f </tex> можно записать и следующим образом: <tex> f(x) = \bigoplus \limits_i \alpha_i \cdot [x_1 , \; </tex> если <tex> \;\; i_1] \cdot [x_2 , \; </tex> если <tex> \;\; i_2] \cdot ... \cdot [x_n , \; </tex> если <tex> \;\; i_n]</tex>.

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

{{Теорема
|statement=Пусть задана функция <tex> f </tex>. Тогда функцию <tex> \alpha_x </tex> можно найти по формуле: <tex>\alpha_x = \bigoplus \limits_{j\preceq x} f(j)</tex>  <tex> (3) </tex>.
||proof=Докажем при помощи индукции по количеству единиц в векторе <tex> x </tex> ( иначе говоря, по сумме <tex>x_1+x_2+...+x_n</tex> ) и для удобства обозначим это количество единиц(сумму) <tex> wt(x) </tex>.

'''1)''' База: если <tex> x = 0 </tex>, то, очевидно <tex> f(0) = \alpha_0 </tex>

'''2)''' Пускай теорема справедлива для всех сумм <tex>wt(x) < k</tex>. Покажем, что в таком случае она верна и для <tex>wt(x) = k</tex>. По <tex> (2) </tex>, а далее по предположению индукции видим: <tex> 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</tex> .

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

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

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

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

* [http://www.stat-mat.com/?p=330 Cтатистика | Математика НГУ]
* [http://ru.wikipedia.org/wiki/Полином_Жегалкина Википедия]
* [http://dvo.sut.ru/libr/himath/w163rabk/index.htm Е.Л Рабкин, Ю.Б. Фарфоровская, дискретная математика]
* Логачёв О.А, Сальников А.А., Ященко В.В. Булевы фунции в теории кодирования и криптологии — МЦНМО, 2004. - 470с. — ISBN 5-94057-117-4.

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Булевы функции]]

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

2011-10-15T02:22:40Z

Целиков Александр:

Участник:Целиков Александр

2011-10-15T01:43:55Z

Целиков Александр:

Студент ИТМО, группа 1537.
Контакты:
*e-mail: [mailto:tselikov.alexander@gmail.com tselikov.alexander@gmail.com]
*jabber: sansany4@jaber.ru
*skype: rumbleblowingaggregate

Участник:Целиков Александр

2011-10-15T01:42:24Z

Целиков Александр: коротко о себе

Студент ИТМО, гр. 1537.
Контакты:
*[mailto:tselikov.alexander@gmail.com]
*jabber: sansany4@jaber.ru
*skype: rumbleblowingaggregate

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

2011-10-15T01:37:54Z

Целиков Александр: Перенёс статью «Преобразование Мёбиуса»

Преобразование Мёбиуса для получения коэффициентов полинома Жегалкина

2011-10-15T01:36:39Z

Целиков Александр: Перенёс в статью «Полином Жегалкина»

#перенаправление [[Полином Жегалкина#Преобразование Мёбиуса]]

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

2011-10-08T00:46:24Z

Целиков Александр: