|
|
| (не показано 14 промежуточных версий 3 участников) |
| Строка 1: |
Строка 1: |
| − | Пусть задана булева функция <tex>f: B^n \rightarrow B, \;\; B=\{ 0; 1 \}</tex>. Любая булева функция представима в виде полинома Жегалкина, притом единственным образом.
| + | #перенаправление [[Полином Жегалкина#Преобразование Мёбиуса]] |
| − | То есть
| |
| − | <br/><br/>
| |
| − | : <math>f(x_{1},x_{2},...x_{n}) = \bigoplus _{1\leq k \leq n} \left [\bigoplus _{1\leq i_{1}<i_{2}<..<i_{k} \leq n} \alpha _{i_{1}i_{2},..i_{k}}x_{i_{1}}x_{i_{2}}...x_{i_{k}} \right ],</math>
| |
| − | | |
| − | :где <tex>\alpha _{i} \in \{ 0; 1 \}</tex> (<tex>i</tex> - вектор из <tex>i_{1}, i_{2},.. i_{k}</tex>).
| |
| − | <br/>
| |
| − | Пусть <tex> m(i) = (m _{1}, m _{2}, .. m _{n}), \;\;</tex> где для всех индексов <tex>t=i _{k}, \;\; m _{t} = 1</tex>, а для остальных индексов <tex>t \neq i _{k}, \; m _{t} = 0</tex>. Тогда отображение <tex>f\rightarrow \alpha _{i} </tex> (то есть такое, которое по заданной функции определяет ее коэффициенты при членах полинома Жегалкина) является:
| |
| − | | |
| − | : <math>\alpha _{i} = \bigoplus _{j\preceq m(i)} f(j)</math>
| |
| − | | |
| − | Такое отображение также называется '''преобразованием Мёбиуса'''.
| |
| − | ----
| |
| − | <br/>
| |
| − | Очевидно, функцию <tex> f </tex> можно записать и следующим образом:
| |
| − | | |
| − | : <math> f(x) = \bigoplus _{i} \alpha _{i} \cdot [x _{1} , \; \text {if} \; m _{1}] \cdot [x _{2} , \; \text {if} \; m _{2}] \cdot ... </math>
| |
| − | | |
| − | Запись <tex>[x _{k} , \; \text {if} \; m _{k}]</tex> означает, что элелемент <tex> x_{k} </tex> присутствует в соответствующем члене полинома только если <tex> m_{k} = 1 </tex>.
| |
| − | Отсюда ясно, что
| |
| − |
| |
| − | : <math> f(x) = \bigoplus _{m(i) \leq x} \alpha _{i} </math>.
| |
| − | | |
| − | Таким образом, если применить '''преобразование Мёбиуса''' к функции, а затем вновь применить то же преобразование к получившейся функции, тогда вновь получим исходную функцию <tex>f</tex>. То есть '''преобразование Мёбиуса''' обратно самому себе.
| |
