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

Пусть задана булева функция [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 _{j\preceq i} f(j)[/math]

Такое отображение также называется преобразованием Мёбиуса.

---

Очевидно, функцию [math] f [/math] можно записать и следующим образом:

[math] f(x) = \bigoplus _{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} , \; \text {if} \; i _{k}][/math] означает, что элелемент [math] x_{k} [/math] присутствует в соответствующем члене полинома только если [math] i_{k} = 1 [/math]. Отсюда ясно, что

[math] f(x) = \bigoplus _{i \preceq x} \alpha _{i} [/math].

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