Изменения

|statement=Пусть задана функция <tex> f </tex>. Тогда отображение функцию <tex>f\rightarrow \alpha _alpha_{ix} </tex> (то есть такое, которое можно найти по заданной функции определяет ее коэффициенты при членах [[Полином_Жегалкина|полинома Жегалкина]]) являетсяформуле: <tex>\alpha _{ix} = \bigoplus \limits_{j\preceq ix} f(j)</tex> &nbsp;&nbsp; <tex> (2)</tex>.||proof=Докажем с помощью при помощи индукции по количеству единичек единиц в векторе <tex> x </tex> ( иначе говоря, по сумме <tex>x_{1}+x_{2}+...+x_{n}</tex> )и для удобства обозначим это количество (сумму) <tex> wt(x) </tex>. <br/>'''1) ''' База: если <tex> x = 0 </tex>, то, очевидно <tex> f(0) = \alpha _{0} </tex><br/>'''2) ''' Пускай теорема справедлива для всех сумм <tex>x_{1}+x_{2}+...+x_{n} wt(x) < k</tex>. Покажем, что в таком случае она верна и для <tex>x_{1}+x_{2}+...+x_{n} wt(x) = k</tex>. По определению <tex> f (1) </tex>, а далее по предположению индукции видим: <tex> f(x) = \bigoplus\limits_{i\preceq x} \alpha _{i} = \left [ \bigoplus \cdot x_limits_{1i \prec x}^\bigoplus \limits_{i_j\preceq i} f(j) \right ] \oplus \alpha_{1x}</tex> Рассмотрим сумму <tex> \left [ \bigoplus \limits_{i \prec x} \cdot x_bigoplus \limits_{j\preceq i} f(j) \right ] </tex>. Каждый элемент <tex> f(j) </tex> содержится в ней, только если <tex> j \preceq x </tex>. И для фиксированных <tex> j, x </tex> элемент <tex> f(j)</tex> встречается ровно столько раз, сколько существует <tex> i </tex> , таких, что <tex> j \prec i \preceq x</tex>. Несложно увидеть, что таких <tex> i </tex> встретится ровно <tex> 2}^{i_wt(x)-wt(j)}-1 </tex>, то есть нечетное количество раз. Тогда <tex> \left [ \bigoplus \limits_{2i \prec x}\bigoplus \limits_{j\preceq i} f(j) \right ] = \bigoplus \cdot ..limits_{j\prec x} f(j) </tex>. Но тогда <tex> f(x) = \left [ \bigoplus \limits_{j\prec x} f(j) \right ] \oplus \cdot x_alpha_{nx}^\Leftrightarrow f(x) \oplus \bigoplus \limits_{i_j\prec x} f(j) = \alpha_{nx}\Leftrightarrow \alpha_{x} = \bigoplus \limits_{j\preceq x} f(j)</tex>. <br/>То есть при <tex>wt(x) = k</tex> формула также выполняется, значит при любых <tex> x </tex> выполняется <tex>\alpha _{x} = \bigoplus \limits_{j\preceq x} f(j)</tex>.

Множество коэффициентов Отображение <tex>\{\alpha _{i}\}</tex> можно рассматривать как функцию <tex>\alpha</tex>, заданной на множестве индексов <tex> i \in \overline{1..n}</tex>, то есть <tex>\alpha: i f \mapsto \alpha_{i}</tex>.  Очевидно, функцию <tex> f </tex> можно записать и следующим образом: <tex> 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}]</tex>отображение также называется '''преобразованием Мёбиуса'''.

Тут запись <tex>[x _{k} , \; \mbox {if} \; i _{k}]</tex> означаетВидно, что элелемент <tex> x_{k} (1) </tex> присутствует в соответствующем члене полинома только если и <tex> i_{k} = 1 (2) </tex>это одно и тоже преобразование. Отсюда ясноЗначит, что если применить '''преобразование Мёбиуса''' к функции, а затем вновь применить то же преобразование к получившейся функции, тогда вновь получим исходную функцию <tex> f(x) = \bigoplus \limits_{i \preceq x} \alpha _{i} </tex>. То есть '''преобразование Мёбиуса''' обратно самому себе.

Таким образом== Литература ==* Логачёв О.А, Сальников А.А., если применить Ященко В.В. '''преобразование МёбиусаБулевы фунции в теории кодирования и криптологии''' к функции— МЦНМО, а затем вновь применить то же преобразование к получившейся функции, тогда вновь получим исходную функцию <tex>f</tex>2004. - 470с. То есть '''преобразование Мёбиуса''' обратно самому себе— ISBN 5-94057-117-4.