Викиконспекты:Текущие события — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 4: Строка 4:
 
<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>
 
<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>
  
 +
== Предпосылки ==
 +
 +
По теореме Поста, чтобы система булевых функций была полной, надо, чтобы в ней существовали:
 +
 +
  \li Хотя бы одна функция, не сохраняющая 0.
 +
  \li Хотя бы одна функция, не сохраняющая 1.
 +
  \li Хотя бы одна нелинейная функция.
 +
  \li Хотя бы одна немонотонная функция.
 +
  \li Хотя бы одна несамодвойственная функция.
  
== Предпосылки ==
+
Этому требованию отвечает система функций \bigl\langle \wedge, \oplus, 1 \bigr\rangle. На её основе и строятся полиномы Жегалкина.

Версия 02:00, 11 октября 2010

Полином Жегалкина — полином с коэффициентами вида 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]

Предпосылки

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

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

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