22
правки
Изменения
Нет описания правки
'''Полином Жегалкина''' — полином с коэффициентами вида 0 и 1, где в качестве произведения берётся конъюнкция, а в качестве сложения исключающее или. Полином был предложен в 1927 году И. И. Жегалкиным в качестве удобного средства для представления [[Определение булевой функции|функций булевой логики]]. Полином Жегалкина имеет следующий вид:
<tex>P = a_{000...000} \oplus a_{000100...0010} x_1 \oplus a_{000010...0100} x_2 \oplus ... \oplus a_{10000...00001} x_n \oplus a_{000110...0110} x_1 x_2 \oplus ... \oplus a_{11000...000011} x_{n-1} x_n \oplus ... \oplus a_{11111..1111} x_1 x_2 ... x_n </tex>
== Предпосылки ==
Построим для неё полином Жегалкина:
<tex>f(x_1,x_2,x_3,x_4) = a_0 a_{0000} \oplus a_1 a_{1000} x_1 \oplus a_2 a_{0100} x_2 \oplus a_3 a_{0010} x_3 \oplus a_4 a_{0001} x_4 \oplus a_5 a_{1100} x_1 x_2 \oplus a_6 a_{1010} x_1 x_3 \oplus a_7 a_{1001} x_1 x_4 \oplus a_8 a_{0110} x_2 x_3 \oplus a_9 a_{0101} x_2 x_4 \oplus a_{100011} x_3 x_4 \oplus a_{111110} x_1 x_2 x_3 \oplus a_{121101} x_1 x_2 x_4 \oplus a_{131011} x_1 x_3 x_4 \oplus a_{140111} x_2 x_3 x_4 \oplus a_{151111} x_1 x_2 x_3 x_4</tex>
Так как <tex>f(0,0,0,0) = 0</tex>, то <tex>a_0 a_{0000} = 0</tex>.
Далее подставляем все остальные наборы в порядке возрастания числа единиц, подставляя вновь полученные значения в следующие формулы:
<tex>f(1,0,0,0) = a_0 a_{0000} \oplus a_1 a_{1000} = 1 \Rightarrow a_1 a_{1000} = 1</tex>
<tex>f(0,1,0,0) = a_0 a_{0000} \oplus a_2 a_{0100} = 0 \Rightarrow a_2 a_{0100} = 0</tex>
<tex>f(0,0,1,0) = a_0 a_{0000} \oplus a_3 a_{0010} = 0 \Rightarrow a_3 a_{0010} = 0</tex>
<tex>f(0,0,0,1) = a_0 a_{0000} \oplus a_4 a_{0001} = 0 \Rightarrow a_4 a_{0001} = 0</tex>
<tex>f(1,1,0,0) = a_0 a_{0000} \oplus a_1 a_{1000} \oplus a_2 a_{0100} \oplus a_5 a_{1100} = 1 \Rightarrow a_5 a_{1100} = 0</tex>
<tex>f(1,0,1,0) = a_0 a_{0000} \oplus a_1 a_{1000} \oplus a_2 a_{0100} \oplus a_6 a_{1010} = 0 \Rightarrow a_6 a_{1010} = 1</tex>
<tex>f(1,0,0,1) = a_0 a_{0000} \oplus a_1 a_{1000} \oplus a_2 a_{0100} \oplus a_7 a_{1001} = 0 \Rightarrow a_7 a_{1001} = 1</tex>
<tex>f(0,1,1,0) = a_0 a_{0000} \oplus a_2 a_{0100} \oplus a_3 a_{0010} \oplus a_8 a_{0110} = 1 \Rightarrow a_8 a_{0110} = 1</tex>
<tex>f(0,1,0,1) = a_0 a_{0000} \oplus a_2 a_{0100} \oplus a_4 a_{0001} \oplus a_9 a_{0101} = 0 \Rightarrow a_9 a_{0101} = 0</tex>
<tex>f(0,0,1,1) = a_0 a_{0000} \oplus a_3 a_{0010} \oplus a_4 a_{0001} \oplus a_{100011} = 0 \Rightarrow a_{100011} = 0</tex>
<tex>f(1,1,1,0) = a_0 a_{0000} \oplus a_1 a_{1000} \oplus a_2 a_{0100} \oplus a_3 a_{0010} \oplus a_5 a_{1100} \oplus a_6 a_{1010} \oplus a_8 a_{0110} \oplus a_{111110} = 1 \Rightarrow a_{111110} = 0</tex>
<tex>f(1,1,0,1) = a_0 a_{0000} \oplus a_1 a_{1000} \oplus a_2 a_{0100} \oplus a_4 a_{0001} \oplus a_5 a_{1100} \oplus a_7 a_{1001} \oplus a_9 a_{0101} \oplus a_{121101} = 0 \Rightarrow a_{121101} = 0</tex>
<tex>f(1,0,1,1) = a_0 a_{0000} \oplus a_1 a_{1000} \oplus a_3 a_{0010} \oplus a_4 a_{0001} \oplus a_6 a_{1010} \oplus a_7 a_{1001} \oplus a_{100011} \oplus a_{131011} = 1 \Rightarrow a_{131011} = 0</tex>
<tex>f(0,1,1,1) = a_0 a_{0000} \oplus a_2 a_{0100} \oplus a_3 a_{0010} \oplus a_4 a_{0001} \oplus a_8 a_{0110} \oplus a_9 a_{0101} \oplus a_{100011} \oplus a_{140111} = 0 \Rightarrow a_{140111} = 1</tex>
<tex>f(1,1,1,1) = a_0 a_{0000} \oplus a_1 a_{1000} \oplus a_2 a_{0100} \oplus a_3 a_{0010} \oplus a_4 a_{0001} \oplus a_5 a_{1100} \oplus a_6 a_{1010} \oplus a_7 a_{1001} \oplus a_8 a_{0110} \oplus a_9 a_{0101} \oplus a_{100011} \oplus a_{111110} \oplus a_{121101} \oplus a_{131011} \oplus a_{140111} \oplus a_{151111} = 0 \Rightarrow a_{151111} = 1</tex>
Таким образом, полином Жегалкина выглядит так:
