Эта статья находится в разработке!
Пусть задана булева функция [math]f: B^n \rightarrow B, \;\; B=\{ 0; 1 \}[/math]. Любая булева функция представима в виде полинома Жегалкина, притом единственным образом. Пусть [math] i = (i _{1}, i _{2}, .. i _{n}), \;\; i _{k} = \{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]f\rightarrow \alpha _{i} [/math] (то есть такое, которое по заданной функции определяет ее коэффициенты при членах полинома Жегалкина) является: [math]\alpha _{i} = \bigoplus \limits_{j\preceq i} f(j)[/math]. |
| Доказательство: |
| [math]\triangleright[/math] |
|
Докажем с помощью индукции по количеству единичек в векторе [math] x [/math] ( иначе говоря, по сумме [math]x_{1}+x_{2}+...+x_{n}[/math] ).
1) База: если [math] x = 0 [/math], то, очевидно [math] f(0) = \alpha _{0} [/math]
2) Пускай теорема справедлива для всех сумм [math]x_{1}+x_{2}+...+x_{n} \lt k[/math]. Покажем, что в таком случае она верна и для [math]x_{1}+x_{2}+...+x_{n} = k[/math]. По определению [math] f [/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]\triangleleft[/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} , \; \text {if} \;\; i _{1}] \cdot [x _{2} , \; \text {if} \;\; i _{2}] \cdot ... \cdot [x _{n} , \; \text {if} \;\; i_{n}][/math].
Тут запись [math][x _{k} , \; \mbox {if} \; i _{k}][/math] означает, что элелемент [math] x_{k} [/math] присутствует в соответствующем члене полинома только если [math] i_{k} = 1 [/math].
Отсюда ясно, что [math] f(x) = \bigoplus \limits_{i \preceq x} \alpha _{i} [/math].
Таким образом, если применить преобразование Мёбиуса к функции, а затем вновь применить то же преобразование к получившейся функции, тогда вновь получим исходную функцию [math]f[/math]. То есть преобразование Мёбиуса обратно самому себе.
