Изменения

Перейти к: навигация, поиск

Полином Жегалкина

3 байта убрано, 03:13, 11 октября 2010
Нет описания правки
<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>
== Предпосылки ==
По теореме Поста, чтобы система булевых функций была полной, надо, чтобы в ней существовали:
1.Хотя бы одна функция, не сохраняющая 0. \\//2.Хотя бы одна функция, не сохраняющая 1. \\//3.Хотя бы одна нелинейная функция. \\//4.Хотя бы одна немонотонная функция. \\//5.Хотя бы одна несамодвойственная функция. \\//
Этому требованию отвечает система функций <math>\bigl\langle \wedge, \oplus, 1 \bigr\rangle</math>. На её основе и строятся полиномы Жегалкина.
43
правки

Навигация