Викиконспекты:Текущие события

Полином Жегалкина — полином с коэффициентами вида 0 и 1, где в качестве произведения берется конъюнкция, а в качестве сложения исключающее или. Полином был предложен в 1927 году И. И. Жегалкиным в качестве удобного средства для представляения функций булевой логики. Полином Жегалкина имеет следующий вид:

[math]P = a_{0} \oplus a_{1} x_{1} \oplus a_{2} x_{2} \oplus ... \oplus a_{n} x_{n} \oplus a_{n+1} x_{1} x_{2} \oplus ... \oplus a_{n + C _{n}^2} x_{n-1} x_{n} \oplus ... \oplus a_{2^n-1} x_{1} x_{2} .. x_{n} [/math]

Предпосылки

По теореме Поста, чтобы система булевых функций была полной, надо, чтобы в ней существовали:

/item Хотя бы одна функция, не сохраняющая 0. /item Хотя бы одна функция, не сохраняющая 1. /item Хотя бы одна нелинейная функция. /item Хотя бы одна немонотонная функция. /item Хотя бы одна несамодвойственная функция.

Этому требованию отвечает система функций [math]\bigl\langle \wedge, \oplus, 1 \bigr\rangle[/math]. На её основе и строятся полиномы Жегалкина.