Редактирование: Преобразование Мёбиуса для получения коэффициентов полинома Жегалкина
Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.
Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия | Ваш текст | ||
Строка 1: | Строка 1: | ||
− | + | Пусть задана булева функция <tex>f: B^n \rightarrow B, \;\; B=\{ 0; 1 \}</tex>. Любая булева функция представима в виде полинома Жегалкина, притом единственным образом. Пусть <tex> i = (i _{1}, i _{2}, .. i _{n}), \;\; i _{k} = \{0 ; 1\}</tex>, и введем обозначение <tex> x ^{i _{k}} \sim \left\{\begin{matrix} x, \;\; i _{k}=1 | |
+ | \\ 1, \;\; i _{k}=0 | ||
+ | \end{matrix}\right. </tex> Тогда полином Жегалкина можно записать как: | ||
+ | :<math> f(x) = \bigoplus _{i} \alpha _{i} \cdot x_{1}^{i_{1}} \cdot x_{2}^{i_{2}} \cdot ... \cdot x_{n}^{i_{n}}</math>, | ||
+ | :где <tex>\alpha _{i} \in \{ 0; 1 \}</tex> | ||
+ | |||
+ | Тогда отображение <tex>f\rightarrow \alpha _{i} </tex> (то есть такое, которое по заданной функции определяет ее коэффициенты при членах полинома Жегалкина) является: | ||
+ | |||
+ | : <math>\alpha _{i} = \bigoplus _{j\preceq i} f(j)</math> | ||
+ | |||
+ | Такое отображение также называется '''преобразованием Мёбиуса'''. | ||
+ | ---- | ||
+ | <br/> | ||
+ | Очевидно, функцию <tex> f </tex> можно записать и следующим образом: | ||
+ | |||
+ | : <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> | ||
+ | |||
+ | Запись <tex>[x _{k} , \; \text {if} \; i _{k}]</tex> означает, что элелемент <tex> x_{k} </tex> присутствует в соответствующем члене полинома только если <tex> i_{k} = 1 </tex>. | ||
+ | Отсюда ясно, что | ||
+ | |||
+ | : <math> f(x) = \bigoplus _{i \preceq x} \alpha _{i} </math>. | ||
+ | |||
+ | Таким образом, если применить '''преобразование Мёбиуса''' к функции, а затем вновь применить то же преобразование к получившейся функции, тогда вновь получим исходную функцию <tex>f</tex>. То есть '''преобразование Мёбиуса''' обратно самому себе. |