22
правки
Изменения
→Преобразование Мёбиуса
Любая булева функция представима в виде полинома Жегалкина, притом единственным образом.
Пусть <tex> i = (i _1i_1, i _2i_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= (i_1, i_2, ..n}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 ... \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>.
