Доказательство. Возьмем полином Жегалкина R для f

Возьмем полином Жегалкина R для f. Так как f - это нелинейная функция, то в полиноме R содержится слагаемое, включающее произведение некоторых двух переменных. Без ограничения общности можно считать, что такое произведение содержит вхождения переменных x₁и x₂.

(Если все произведения двух и большего числа переменных не содержат одновременно эти переменные, то необходимо произвести соответствующее переименование переменных в f, используя подстановки переменных вместо переменных функции.)

Сгруппируем слагаемые в R и, вынося переменные x₁ и x₂ за скобки, представим его в виде

(1).

Здесь полином R₁ содержит хотя бы одно ненулевое слагаемое и поэтому представляет булевскую функцию, отличную от тождественного нуля.

Пусть . Подставим вместо переменных x₃, . . . , x_n конкретные значения . Тогда имеет место равенство:

= (2)

Здесь и .

Заменим x₁ на x₁ + b и х₂ на x₂ +a. При этом, если a или b, равно нулю, то соответствующая переменная не заменяется. В противном случае соответствующая переменная заменяется на отрицание этой переменной.

В результате такой замены выражение (2) преобразуется к виду

. (3)

Если , то функция x₁&x₂уже получена.

В противном случае применим отрицание к функции вида (3) и также получим x₁&x₂.