polynom

Ответ от Єарит Аиткулов[гуру]
Полином Жегалкина — многочлен над кольцом, то есть полином с коэффициентами вида 0 и 1, где в качестве произведения берётся конъюнкция, а в качестве сложения — исключающее или. Полином был предложен в 1927 году Иваном Жегалкиным в качестве удобного средства для представления функций булевой логики. В зарубежной литературе представление в виде полинома Жегалкина обычно называется алгебраической нормальной формой (АНФ) .
Теорема Жегалкина — утверждение о существовании и единственности представления всякой булевой функции в виде полинома Жегалкина.
Полином Жегалкина представляет собой сумму по модулю два произведений неинвертированных переменных, а также (если необходимо) константы 1. Формально полином Жегалкина можно представить в виде
или в более формализованном виде как:
Примеры полиномов Жегалкина:
Содержание [убрать]
1 Предпосылки
2 Cуществование и единственность представления
3 Представление функции в виде полинома Жегалкина
3.1 С помощью эквивалентных преобразований ДНФ
3.2 С помощью эквивалентных преобразований СДНФ
3.3 С помощью карты Карно
3.4 Метод треугольника [1]
4 Литература
5 Примечания
[править]
Предпосылки
По теореме Поста, чтобы система булевых функций была полной, надо, чтобы в ней существовали:
Хотя бы одна функция, не сохраняющая 0.
Хотя бы одна функция, не сохраняющая 1.
Хотя бы одна нелинейная функция.
Хотя бы одна немонотонная функция.
Хотя бы одна несамодвойственная функция.
Этому требованию отвечает система функций . На её основе и строятся полиномы Жегалкина.
[править]
Cуществование и единственность представления
По теореме Жегалкина каждая булева функция единственным образом представляется в виде полинома Жегалкина. Теорема доказывается следующим образом. Заметим, что различных булевых функций от n переменных штук. При этом конъюнкций вида существует ровно 2n, так как из n возможных сомножителей каждый или входит в конъюнкцию, или нет. В полиноме у каждой такой конъюнкции стоит 0 или 1, то есть существует различных полиномов Жегалкина от n переменных. Теперь достаточно лишь доказать, что различные полиномы реализуют различные функции. Предположим противное. Тогда приравняв два различных полинома и перенеся один из них в другую часть равенства, получим полином, тождественно равный нулю и имеющий ненулевые коэффициенты. Тогда рассмотрим слагаемое с единичным коэффициентом наименьшей длины, то есть с наименьшим числом переменных, входящих в него (любой один, если таких несколько) . Подставив единицы на места этих переменных, и нули на места остальных, получим, что на этом наборе только одно это слагаемое принимает единичное значение, то есть нулевая функция на одном из наборов принимает значение 1. Противоречие. Значит, каждая булева функция реализуется полиномом Жегалкина единственным образом.