Лемма о несамодвойственной функции

 

Подстановкой функций и в несамодвойственную функцию можно получить одну из констант.

Доказательство.Пусть – несамодвойственная функция. Тогда существует набор , для которого . Построим функцию , заменив единицы в на , а нули – на. Так как , то . Заметим, что .

Тогда , т.е. . Следовательно, функция есть одна из констант.