Доказательство. К вопросу о нахождении векторов значений булевой функции

0.

К вопросу о нахождении векторов значений булевой функции , где пробегает по всем векторам из . Можно заметить, что столбец значений получается из столбца значений его переворачиванием. То есть достаточно вычислить только половину векторов значений, а вторая половина получится переворачиванием соответствующих векторов из первой половины.

Доказательство.

Здесь - это вектор из .

Как выглядит вектор ? Нетрудно увидеть, что это вектор, получающийся из вектора заменой всех единиц на нули и всех нулей - на единицы. Теперь надо определить, на каком месте в таблице располагается этот вектор относительно вектора . По индукции можно доказать, что если вектор соответствует положительному целому числу , то вектор соответствует числу . А это значит, что в таблице векторы и будут расположены симметрично относительно ее центра. Для вектора , очевидно, выполнится то же самое, то есть

Итак, (здесь – номер вектора в столбце).

Доказательство закончено.

1.

Утверждение о связи между энергетическим спектром (коэффициентами Уолша) и автокорреляции булевой функции :

Доказательство.

Поменяем порядок суммирования:

Теперь воспользуемся тем, что

Утверждение доказано.

2.

Следствие предыдущего утверждения:

Дата добавления: 2015-07-15