Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

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

Читайте также:
  1. Доказательство.
  2. Доказательство.
  3. Доказательство.
  4. Доказательство.
  5. Доказательство.
  6. Занятия 3-4. Тема: Теорема Чевы и ее следствия. Применение теоремы Чевы и теоремы Менелая к задачам на доказательство.

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

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








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

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

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

 

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

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

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

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


Дата добавления: 2015-07-15; просмотров: 65 | Нарушение авторских прав


<== предыдущая страница | следующая страница ==>
Доказательство.| Доказательство.

mybiblioteka.su - 2015-2024 год. (0.007 сек.)