Всего в полиноме Жегалкина от переменных будет слагаемых - столько, сколько существует различных конюънкций вида при .

Каждая конъюнкция может либо входить в полином Жегалкина функции (коэф. перед ней 1), либо не входить (коэф. перед ней 0).

То есть всего получается различных полиномов Жегалкина от переменных.

Но булевых функций от переменных тоже .

Поэтому, если бы какой-то функции соответствовало бы 2 различных полинома Жегалкина, то какой-то функции не соответсововало бы вообще ни одного.

А этого быть не может, поскольку мы раньше уже научились строить полином Жегалкина для абсолютно любой булевой функции.

Следовательно, у каждой булевой функции полином Жегалкина единственный.