Докажите, что полином Жегалкина от n переменных степени k > 0 обращается в 0 не менее, чем на 2^(n−k) наборах (и в 1 не менее, чем на 2^(n−k) наборах).

задан 28 Сен '17 0:14

10|600 символов нужно символов осталось
0

Понятно, что обращение в ноль или в единицу -- вещь не принципиальная, так как к многочлену можно прибавить 1, что не влияет на степень. Будем доказывать утверждение индукцией по $%n$%. При $%n=k=1$% всё очевидно. Пусть $%n > 1$%. Рассмотрим полином степени $%k > 0$%. Выделим в нём одночлен степени $%k$%, и пусть в него входит переменная $%x_n$%. Тогда функция представима в виде $%f=g+x_nh$%, где $%g$% и $%h$% -- полиномы Жегалкина от $%n-1$% переменной, причём $%h$% имеет степень $%k-1$%.

Можно было сразу отметить, что для линейного полинома, то есть при $%k=1$%, утверждение очевидно: там всё регулируется значением одной из переменных, и ровно на половине наборов получается значение 0, а на половине 1. Далее считаем, что $%k > 1$%. Допустим, что степень $%g$% меньше $%k-1$%. Тогда при $%x_n=1$% мы имеем многочлен $%g+h$% от $%n-1$% переменной, степень которого равна $%k-1 > 0$%. Тогда по предположению индукции можно гарантировать $%2^{(n-1)-(k-1)}=2^{n-k}$% наборов с заданным значением.

Пусть теперь степень $%g$% равна $%k-1$%. Тогда можно положить $%x_n=0$%, и применить предыдущее рассуждение к $%g$% вместо $%g+h$%. Осталось рассмотреть случай, когда степень $%g$% равна $%k$%. Тогда оба многочлена $%g$% и $%g+h$% имеют степень $%k$%, и они дают по $%2^{n-1-k}$% значений полинома, равных 1. Один случай относится к $%x_n=0$% (для $%g$%), а второй к $%x_n=1$% (для $%g+h$%). Вместе имеем $%2^{n-k}$% наборов для исходного многочлена, что и требовалось.

ссылка

отвечен 28 Сен '17 2:52

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×143

задан
28 Сен '17 0:14

показан
290 раз

обновлен
28 Сен '17 2:52

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru