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

Пусть f (x ₁,..., x _n) L.

Возьмем полином Жегалкина 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 ₂.