Изменения
Нет описания правки
'''Полином Жегалкина''' (англ. ''Zhegalkin polynomial'') — полином с коэффициентами вида <tex>0</tex> и <tex>1</tex>, где в качестве произведения берётся конъюнкция, а в качестве сложения исключающее или. Полином был предложен в 1927 году И. И. Жегалкиным в качестве средства для представления [[Определение булевой функции|функций булевой логики]]. Полином Жегалкина имеет следующий вид:
<tex>P = a_{000...000\ldots000} \oplus a_{100...0\ldots0} x_1 \oplus a_{010...0\ldots0} x_2 \oplus ... \ldots \oplus a_{00...01\ldots01} x_n \oplus a_{110...0\ldots0} x_1 x_2 \oplus ... \ldots \oplus a_{00...011\ldots011} x_{n-1} x_n \oplus ... \ldots \oplus a_{11..1} x_1 x_2 ... \ldots x_n </tex>
== Полнота ==
|<tex>1</tex>||<tex>1</tex>||<tex>0</tex>
|-align="center"
!colspan="4"|[[Полные_системы_функций._Теорема_Поста_о_полной_системе_функций#.D0.97.D0.B0.D0.BC.D0.BA.D0.BD.D1.83.D1.82.D1.8B.D0.B5_.D0.BA.D0.BB.D0.B0.D1.81.D1.81.D1.8B_.D0.B1.D1.83.D0.BB.D0.B5.D0.B2.D1.8B.D1.85_.D1.84.D1.83.D0.BD.D0.BA.D1.86.D0.B8.D0.B9|Сохраняет 0]]
|<tex>0</tex>||<tex>1</tex>||<tex>1</tex>
|-align="center"
!colspan="4"|[[Полные_системы_функций._Теорема_Поста_о_полной_системе_функций#.D0.97.D0.B0.D0.BC.D0.BA.D0.BD.D1.83.D1.82.D1.8B.D0.B5_.D0.BA.D0.BB.D0.B0.D1.81.D1.81.D1.8B_.D0.B1.D1.83.D0.BB.D0.B5.D0.B2.D1.8B.D1.85_.D1.84.D1.83.D0.BD.D0.BA.D1.86.D0.B8.D0.B9|Сохраняет 1]]
|<tex>1</tex>||<tex>1</tex>||<tex>0</tex>
|-align="center"
!colspan="4"|[[Полные_системы_функций._Теорема_Поста_о_полной_системе_функций#.D0.97.D0.B0.D0.BC.D0.BA.D0.BD.D1.83.D1.82.D1.8B.D0.B5_.D0.BA.D0.BB.D0.B0.D1.81.D1.81.D1.8B_.D0.B1.D1.83.D0.BB.D0.B5.D0.B2.D1.8B.D1.85_.D1.84.D1.83.D0.BD.D0.BA.D1.86.D0.B8.D0.B9|Самодвойственная]]
|<tex>0</tex>||<tex>0</tex>||<tex>0</tex>
|-align="center"
!colspan="4"|[[Полные_системы_функций._Теорема_Поста_о_полной_системе_функций#.D0.97.D0.B0.D0.BC.D0.BA.D0.BD.D1.83.D1.82.D1.8B.D0.B5_.D0.BA.D0.BB.D0.B0.D1.81.D1.81.D1.8B_.D0.B1.D1.83.D0.BB.D0.B5.D0.B2.D1.8B.D1.85_.D1.84.D1.83.D0.BD.D0.BA.D1.86.D0.B8.D0.B9|Монотонная]]
|<tex>1</tex>||<tex>1</tex>||<tex>0</tex>
|-align="center"
!colspan="4"|[[Полные_системы_функций._Теорема_Поста_о_полной_системе_функций#.D0.97.D0.B0.D0.BC.D0.BA.D0.BD.D1.83.D1.82.D1.8B.D0.B5_.D0.BA.D0.BB.D0.B0.D1.81.D1.81.D1.8B_.D0.B1.D1.83.D0.BB.D0.B5.D0.B2.D1.8B.D1.85_.D1.84.D1.83.D0.BD.D0.BA.D1.86.D0.B8.D0.B9|Линейная]]
|<tex>1</tex>||<tex>0</tex>||<tex>1</tex>
|}
Видно, что <tex> (2) </tex> и <tex> (3) </tex> — это одно и тоже преобразование. Значит, если применить преобразование Мёбиуса к функции, а затем вновь применить то же преобразование к получившейся функции, тогда вновь получим исходную функцию <tex>f</tex>. То есть преобразование Мёбиуса обратно самому себе, иными словами, является инволюцией.
== См. также ==
* [[Определение_булевой_функции|Булевы функции]]
* [[Полные_системы_функций._Теорема_Поста_о_полной_системе_функций|Полные системы функций, теорема Поста]]
* [[СДНФ|ДНФ]]
* [[СКНФ|КНФ]]
== Источники информации ==
