Если

, то

- формула для преобразования Жегалкина (можно рассматривать

как цифры индекса

в двоичной системе счисления). То есть можно рассматривать

как функцию формулы от

переменных, а можно как функцию

булевых констант.
Доказать можно по индукции по

(только обозначения немного кривые, если кто знает лучше - напишите):
Для

проверяем, что

:
Пусть для любой

от

переменных

.

. Слева - преобразование Жегалкина от функции

nеременных, в которую потом подставили

, а справа - преобразование Жегалкина функции

переменных

. Причем, если рассматривать преобразования Жегалкина как функции от энки булевых констант, то у функции справа размерность

, а у функции слева -

, поэтому они разные и для различия пишется индекс.
Это соотношение доказывается через формулу для преобразования Жегалкина. Обе части при определенном выборе порядка аргументов равны

.
Представим

как

.
При

, и тогда

по предположению индукции.
Если

, то

, а функция

- аддитивна, поэтому опять по предположению индукции

.
Таким образом, формула

верна при

, и верна при

. Значит, она верна и в общем случае для

переменных, значит по индукции верна для всех

.
З.Ы. А можно ли найти число

.