Доказательство. Пусть функция , удовлетворяет

Пусть функция , удовлетворяет . Тогда является сбалансированной функцией при , то есть выполняется:

Возьмем . Тогда, пока бегает от нуля до , будет выполняться
Для понимания этого равенства можно, например, рассмотреть следующий столбец:

Пусть = 2, тогда , .

Идем дальше. Когда бегает от до , очевидно, будет выполняться

Таким образом, мы можем разбить сумму значений на следующие две суммы:

Так как каждое слагаемое суммы №1 равно соответствующему слагаемому суммы №2, то выходит, что

В таком случае, если , то число единиц в обеих суммах четное. Ясно, что если мы будем суммировать не с помощью операции сложения, а с помощью операции исключающего ИЛИ (то есть по модулю 2), то обе суммы будут равны нулю, т. е.

С другой стороны, эта сумма есть не что иное, как сумма по модулю 2 всех значений функции . Так как данная сумма равна нулю, то число единиц в ней четное. Соответственно, число истинных значений функции – четное. Лемма доказана.

Утверждение о степени функции, удовлетворяющей : если удовлетворяет , то

Дата добавления: 2015-07-15