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

Эта статья находится в разработке!

Пусть задана булева функция [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]. То есть преобразование Мёбиуса обратно самому себе.