Изменения
Нет описания правки
'''Полином Жегалкина''' (англ. ''Zhegalkin polynomial'') — полином с коэффициентами вида <tex>0</tex> и <tex>1</tex>, где в качестве произведения берётся конъюнкция, а в качестве сложения исключающее или. Полином был предложен в 1927 году И. И. Жегалкиным в качестве средства для представления [[Определение булевой функции|функций булевой логики]]. Полином Жегалкина имеет следующий вид:
<tex>P = a_{000\ldots000} \oplus a_{100\ldots0} x_1 \oplus a_{010\ldots0} x_2 \oplus \ldots \oplus a_{00\ldots01} x_n \oplus a_{110\ldots0} x_1 x_2 \oplus \ldots \oplus a_{00\ldots011} x_{n-1} x_n \oplus \ldots \oplus a_{11..1\ldots1} x_1 x_2 \ldots x_n </tex>
== Полнота ==
{| class="wikitable" style="width:8cm" border="1"
|-align="center" bgcolor=#EEEEFF
!<tex>x_0</tex>||<tex>x_1</tex>||<tex>\dotsldots</tex>||<tex>x_n</tex>
|<tex>1</tex>||<tex>\land</tex>||<tex>\oplus</tex>
|-align="center"
!<tex>0</tex>||<tex>0</tex>||<tex>\dotsldots</tex>||<tex>0</tex>
|<tex>1</tex>||<tex>0</tex>||<tex>0</tex>
|-align="center"
!<tex>1</tex>||<tex>0</tex>||<tex>\dotsldots</tex>||<tex>0</tex>
|<tex>1</tex>||<tex>0</tex>||<tex>1</tex>
|-align="center"
|<tex>\vdots</tex>||<tex>\vdots</tex>||<tex>\vdots</tex>
|-align="center"
!<tex>1</tex>||<tex>1</tex>||<tex>\dotsldots</tex>||<tex>1</tex>
|<tex>1</tex>||<tex>1</tex>||<tex>0</tex>
|-align="center"
=== По таблице истинности ===
Пусть для функции <tex>f(x_1,x_2,\dotsldots,x_n)</tex> задана таблица истинности. Запишем сначала данную функцию в виде полинома Жегалкина с неопределёнными коэффициентами. Затем по очереди подставляем всевозможные наборы в порядке увеличения количества единиц и находим коэффициенты с учётом того, что <tex> a \oplus 1 = \bar{a}</tex>, а <tex> a \oplus 0 = a</tex>. За каждую подстановку находим только один коэффициент.
'''Пример:'''
=== Метод треугольника === <!-- Да, копипаста с википедии, и что? Метод же прост и удобен -->
Метод треугольника позволяет преобразовать таблицу истинности в полином Жегалкина путём построения вспомогательной треугольной таблицы в соответствии со следующими правилами:
# Строится полная таблица истинности, в которой строки идут в порядке возрастания двоичных кодов от <tex>000\dots00ldots00</tex> до <tex>111\dots11ldots11</tex>.
# Строится вспомогательная треугольная таблица, в которой первый столбец совпадает со столбцом значений функции в таблице истинности.
# Ячейка в каждом последующем столбце получается путём сложения по модулю 2 двух ячеек предыдущего столбца — стоящей в той же строке и строкой ниже.
Любая булева функция представима в виде полинома Жегалкина, притом единственным образом.
Пусть <tex> i = (i_1, i_2, .. \ldots 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</tex><tex>\dotsldots</tex><tex>\cdot x_n^{i_n}</tex>, где <tex>\alpha_i \in \{ 0; 1 \}</tex>.
Множество коэффициентов <tex>\{\alpha _i\}</tex> можно рассматривать как функцию <tex>\alpha</tex>, заданной на множестве индексов <tex> i = (i_1, i_2, \dots ldots i_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</tex><tex>\dotsldots</tex><tex>\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+</tex><tex>\dotsldots</tex><tex>+x_n</tex> ) и для удобства обозначим это количество единиц(сумму) <tex> wt(x) </tex>.
'''1)''' База: если <tex> x = 0 </tex>, то, очевидно <tex> f(0) = \alpha_0 </tex>
