Изменения

<tex>P = a_{0} a_0 \oplus a_{1} x_{1} a_1 x_1 \oplus a_{2} a_2 x_{2} x_2 \oplus ... \oplus a_{n} a_n x_{n} x_n \oplus a_{n+1} x_{1} x_{2} x_1 x_2 \oplus ... \oplus a_{..n + C _C_{n}^2} x_{n-1} x_{n} x_n \oplus ... \oplus a_{2^n-1} x_{1} x_{2} x_1 x_2 ... x_{n} x_n </tex>

Заметим, что различных булевых функций от <tex>n</tex> переменных <tex>2^{2^n}</tex> штук. При этом конъюнкций вида <tex>x_{i_1}\ldots x_{i_k}</tex> существует ровно <tex>2^n</tex>, так как из <tex>n</tex> возможных сомножителей каждый или входит в конъюнкцию, или нет. В полиноме у каждой такой конъюнкции стоит 0 или 1, то есть существует <tex>2^{2^n}</tex> различных полиномов Жегалкина от <tex>n</tex> переменных.

Пусть для функции <tex>f(x_{1}x_1,x_{2}x_2,..,x_{n}x_n)</tex> задана таблица истинности. Запишем сначала данную функцию в виде полинома Жегалкина с неопределёнными коэффициентами. Затем по очереди подставляем всевозможные наборы в порядке увеличения количества единиц и находим коэффициентыс учётом того, что <tex> a \oplus 1 = \bar{a}</tex>, а <tex> a \oplus 0 = a</tex>. Можно показать, что за каждую подстановку находим только один коэффициент. '''Пример:'''Дана функция <tex>f(x_1,x_2,x_3,x_4)</tex> и её таблица истинности: {| border=1 |- !class="dark" style="font-weight:normal"| <tex>x_1</tex> !class="dark" style="font-weight:normal"| <tex>x_2</tex> !class="dark" style="font-weight:normal"| <tex>x_3</tex> !class="dark" style="font-weight:normal"| <tex>x_4</tex> !class="dark" style="font-weight:normal"| <tex>f(x_1,x_2,x_3,x_4)</tex> |- align="center" ||0||0||0||0||0 |- align="center" ||0||0||0||1||0 |- align="center" ||0||0||1||0||0 |- align="center" ||0||0||1||1||0 |- align="center" ||0||1||0||0||0 |- align="center" ||0||1||0||1||0 |- align="center" ||0||1||1||0||1 |- align="center" ||0||1||1||1||0 |- align="center" ||1||0||0||0||1 |- align="center" ||1||0||0||1||0 |- align="center" ||1||0||1||0||0 |- align="center" ||1||0||1||1||1 |- align="center" ||1||1||0||0||1 |- align="center" ||1||1||0||1||0 |- align="center" ||1||1||1||0||1 |- align="center" ||1||1||1||1||0|}Построим для неё полином Жегалкина: <tex>f(x_1,x_2,x_3,x_4) = a_0 \oplus a_1 x_1 \oplus a_2 x_2 \oplus a_3 x_3 \oplus a_4 x_4 \oplus a_5 x_1 x_2 \oplus a_6 x_1 x_3 \oplus a_7 x_1 x_4 \oplus a_8 x_2 x_3 \oplus a_9 x_2 x_4 \oplus a_{10} x_3 x_4 \oplus a_{11} x_1 x_2 x_3 \oplus a_{12} x_1 x_2 x_4 \oplus a_{13} x_1 x_3 x_4 \oplus a_{14} x_2 x_3 x_4 \oplus a_{15} x_1 x_2 x_3 x_4</tex> Так как <tex>f(0,0,0,0) = 0</tex>, то <tex>a_0 = 0</tex>.Далее подставляем все остальные наборы в порядке возрастания числа единиц, подставляя вновь полученные значения в следующие формулы: <tex>f(1,0,0,0) = a_0 \oplus a_1 = 1 \Rightarrow a_1 = 1</tex> <tex>f(0,1,0,0) = a_0 \oplus a_2 = 0 \Rightarrow a_2 = 0</tex> <tex>f(0,0,1,0) = a_0 \oplus a_3 = 0 \Rightarrow a_3 = 0</tex> <tex>f(0,0,0,1) = a_0 \oplus a_4 = 0 \Rightarrow a_4 = 0</tex> <tex>f(1,1,0,0) = a_0 \oplus a_1 \oplus a_2 \oplus a_5 = 1 \Rightarrow a_5 = 0</tex> <tex>f(1,0,1,0) = a_0 \oplus a_1 \oplus a_2 \oplus a_6 = 0 \Rightarrow a_6 = 1</tex> <tex>f(1,0,0,1) = a_0 \oplus a_1 \oplus a_2 \oplus a_7 = 0 \Rightarrow a_7 = 1</tex> <tex>f(0,1,1,0) = a_0 \oplus a_2 \oplus a_3 \oplus a_8 = 1 \Rightarrow a_8 = 1</tex> <tex>f(0,1,0,1) = a_0 \oplus a_2 \oplus a_4 \oplus a_9 = 0 \Rightarrow a_9 = 0</tex> <tex>f(0,0,1,1) = a_0 \oplus a_3 \oplus a_4 \oplus a_{10} = 0 \Rightarrow a_{10} = 0</tex> <tex>f(1,1,1,0) = a_0 \oplus a_1 \oplus a_2 \oplus a_3 \oplus a_5 \oplus a_6 \oplus a_8 \oplus a_{11} = 1 \Rightarrow a_{11} = 0</tex> <tex>f(1,1,0,1) = a_0 \oplus a_1 \oplus a_2 \oplus a_4 \oplus a_5 \oplus a_7 \oplus a_9 \oplus a_{12} = 0 \Rightarrow a_{12} = 0</tex> <tex>f(1,0,1,1) = a_0 \oplus a_1 \oplus a_3 \oplus a_4 \oplus a_6 \oplus a_7 \oplus a_{10} \oplus a_{13} = 1 \Rightarrow a_{13} = 0</tex> <tex>f(0,1,1,1) = a_0 \oplus a_2 \oplus a_3 \oplus a_4 \oplus a_8 \oplus a_9 \oplus a_{10} \oplus a_{14} = 0 \Rightarrow a_{14} = 1</tex> <tex>f(1,1,1,1) = a_0 \oplus a_1 \oplus a_2 \oplus a_3 \oplus a_4 \oplus a_5 \oplus a_6 \oplus a_7 \oplus a_8 \oplus a_9 \oplus a_{10} \oplus a_{11} \oplus a_{12} \oplus a_{13} \oplus a_{14} = 0 \Rightarrow a_{15} = 1</tex> Таким образом, полином Жегалкина выглядит так: <tex>f(x_1,x_2,x_3,x_4) = x_1 \oplus x_1 x_3 \oplus x_1 x_4 \oplus x_2 x_3 \oplus x_2 x_3 x_4 \oplus x_1 x_2 x_3 x_4</tex>

Этот способ основан на том, что <tex> X \oplus 1 = \bar{X} </tex>. Если функция задана в виде ДНФ, то можно сначала убираем убрать дизъюнкцию, используя при этом правило Де-Моргана, а все отрицания заменяем заменить прибавлением единицы. После этого раскрываем , после чего раскрыть скобки по обычным правилам, при этом учитываемучитывая, что четное число одинаковых слагаемых равно нулю (так как <tex> X \oplus X = 0 </tex>), а нечетное число одинаковых слагаемых равно одному такому слагаемому.Либо же можно заменить дизъюнкцию по следующему правилу: <tex> A \lor B = AB \oplus A \oplus B </tex> &nbsp; <tex> (1) </tex>.Если функция задана в СДНФ, то так как при любых значениях входных переменных в единицу обращается не более одного члена выражения, то достаточно просто заменить все дизъюнкции исключающим ИЛИ. '''Пример:'''Дана функция в ДНФ <tex> f(x_1,x_2,x_3,x_4) = (x_1 \land x_2 \land \neg x_3 \land x_4) \lor (\neg x_1 \land \neg x_4) \lor (x_1 \land x_2) \lor x_2 </tex>, построим полином Жегалкина. Запишем функцию так: <tex>f(x_1,x_2,x_3,x_4) = x_1 x_2 \neg x_3 x_4 + \neg x_1 \neg x_4 + x_1 x_2 + x_2</tex>; Сгруппируем слагаемые и воспользуемся преобразованием <tex>(1)</tex>: <tex>f(x_1,x_2,x_3,x_4) = (x_1 x_2 \neg x_3 x_4 \oplus \neg x_1 \neg x_4 \oplus x_1 x_2 \neg x_3 x_4 \neg x_1 \neg x_4) + (x_1 x_2 \oplus x_2 \oplus x_1 x_2 x_2)</tex> Воспользуемся свойствами конъюнкции <tex>A \land A = A</tex> и <tex>\neg A \land A = 0</tex>, а также тем, что <tex>A \oplus A = 0</tex>, и упростим выражение: <tex>f(x_1,x_2,x_3,x_4) = (x_1 x_2 \neg x_3 x_4 \oplus \neg x_1 \neg x_4) + x_2 </tex> Ещё раз воспользуемся преобразованием <tex>(1)</tex>: <tex>f(x_1,x_2,x_3,x_4) = x_1 x_2 \neg x_3 x_4 \oplus \neg x_1 \neg x_4 \oplus x_2 \oplus (x_1 x_2 \neg x_3 x_4 \oplus \neg x_1 \neg x_4)x_2</tex> Раскроем скобку по алгебраическим правилам: <tex>f(x_1,x_2,x_3,x_4) = x_1 x_2 \neg x_3 x_4 \oplus \neg x_1 \neg x_4 \oplus x_2 \oplus x_1 x_2 x_2 \neg x_3 x_4 \oplus \neg x_1 x_2 \neg x_4 </tex> Снова воспользуемся свойствами конъюнкции и исключающего ИЛИ: <tex>f(x_1,x_2,x_3,x_4) = x_1 x_2 \neg x_3 x_4 \oplus \neg x_1 \neg x_4 \oplus x_2 \oplus \neg x_1 x_2 \neg x_4 </tex> Заменим отрицание на прибавление <tex>1</tex>: <tex>f(x_1,x_2,x_3,x_4) = x_1 x_2 (x_3 \oplus 1) x_4 \oplus (x_1 \oplus 1) (x_4 \oplus 1) \oplus x_2 \oplus (x_1 \oplus 1) x_2 (x_4 \oplus 1)</tex> Раскроем скобки: <tex>f(x_1,x_2,x_3,x_4) = x_1 x_2 x_3 x_4 \oplus x_1 x_2 x_4 \oplus x_1 x_4 \oplus x_1 \oplus x_4 \oplus 1 \oplus x_2 \oplus x_1 x_2 x_4 \oplus x_1 x_2 \oplus x_2 x_4 \oplus x_2</tex> Выкинем парные слагаемые и получим окончательную формулу: <tex>f(x_1,x_2,x_3,x_4) = x_1 x_2 x_3 x_4 \oplus x_1 x_2 \oplus x_1 x_4 \oplus x_2 x_4 \oplus x_1 \oplus x_4 \oplus 1</tex>

Пусть <tex> i = (i _{1}_1, i _{2}_2, .. i _{n}i_n), \;\; i _{k} i_k \in \{0 ; 1\}</tex>, и введем обозначение <tex> x ^{i _{k}i_k} \sim \left\{\begin{matrix} x, \;\; i _{k}i_k=1\\ 1, \;\; i _{k}i_k=0

<tex> f(x) = \bigoplus\limits_{i} limits_i \alpha _{i} alpha_i \cdot x_{1}x_1^{i_{1}i_1} \cdot x_{2}x_2^{i_{2}i_2} \cdot ... \cdot x_{n}x_n^{i_{n}i_n}</tex>, где <tex>\alpha _{i} alpha_i \in \{ 0; 1 \}</tex>.

Множество коэффициентов <tex>\{\alpha _{i}_i\}</tex> можно рассматривать как функцию <tex>\alpha</tex>, заданной на множестве индексов <tex> i \in \overline{1..n}</tex>, то есть <tex>\alpha: i \mapsto \alpha_{i}alpha_i</tex>.

Очевидно, функцию <tex> f </tex> можно записать и следующим образом: <tex> f(x) = \bigoplus \limits_{i} limits_i \alpha _{i} alpha_i \cdot [x _{1} x_1 , \; </tex> если <tex> \;\; i _{1}i_1] \cdot [x _{2} x_2 , \; </tex> если <tex> \;\; i _{2}i_2] \cdot ... \cdot [x _{n} x_n , \; </tex> если <tex> \;\; i_{n}i_n]</tex>.

Тут запись <tex>[x _{k} x_k , \; </tex> если <tex> \; i _{k}i_k]</tex> означает, что элелемент <tex> x_{k} x_k </tex> присутствует в соответствующем члене полинома только если <tex> i_{k} i_k = 1 </tex>.

Отсюда ясно, что <tex> f(x) = \bigoplus \limits_{i \preceq x} \alpha _{i} alpha_i </tex>. &nbsp; <tex> (12) </tex>

|statement=Пусть задана функция <tex> f </tex>. Тогда функцию <tex> \alpha_{x} alpha_x </tex> можно найти по формуле: <tex>\alpha _{x} alpha_x = \bigoplus \limits_{j\preceq x} f(j)</tex> &nbsp;&nbsp; <tex> (23) </tex>.||proof=Докажем при помощи индукции по количеству единиц в векторе <tex> x </tex> ( иначе говоря, по сумме <tex>x_{1}x_1+x_{2}x_2+...+x_{n}x_n</tex> ) и для удобства обозначим это количество единиц(сумму) <tex> wt(x) </tex>. '''1)''' База: если <tex> x = 0 </tex>, то, очевидно <tex> f(0) = \alpha _{0} alpha_0 </tex> '''2)''' Пускай теорема справедлива для всех сумм <tex>wt(x) < k</tex>. Покажем, что в таком случае она верна и для <tex>wt(x) = k</tex>. По <tex> (12) </tex>, а далее по предположению индукции видим: <tex> f(x) = \bigoplus \limits_{i \preceq x} \alpha _{i} alpha_i = \left [ \bigoplus \limits_{i \prec x} \bigoplus \limits_{j\preceq i} f(j) \right ] \oplus \alpha_{x}alpha_x</tex> .

Но тогда <tex> f(x) = \left [ \bigoplus \limits_{j\prec x} f(j) \right ] \oplus \alpha_{x} alpha_x \Leftrightarrow f(x) \oplus \bigoplus \limits_{j\prec x} f(j) = \alpha_{x} alpha_x \Leftrightarrow \alpha_{x} alpha_x = \bigoplus \limits_{j\preceq x} f(j)</tex>.То есть при <tex>wt(x) = k</tex> формула также выполняется, значит при любых <tex> x </tex> выполняется <tex>\alpha _{x} alpha_x = \bigoplus \limits_{j\preceq x} f(j)</tex>.

Видно, что <tex> (12) </tex> и <tex> (23) </tex> — это одно и тоже преобразование. Значит, если применить преобразование Мёбиуса к функции, а затем вновь применить то же преобразование к получившейся функции, тогда вновь получим исходную функцию <tex>f</tex>. То есть преобразование Мёбиуса обратно самому себе, иными словами, является инволюцией.