Булева-алгебра

Понятно, что обращение в ноль или в единицу -- вещь не принципиальная, так как к многочлену можно прибавить 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}$% наборов для исходного многочлена, что и требовалось.