Вес булевой функции

Определение 5.3. Множеством истинности функции / : F? —> F2 называется множество I = 1(f) наборов значений ее аргументов х е Fg, на которых выполнено равенство f(x) — 1.

Весом w(f) функции / называется мощность ее множества истинности. Для обозначения веса функции / мы также будем использовать обозначение ||/||.

Если вес функции удовлетворяет равенству w(f) = 2^n_1, то функция называется сбалансированной, или равновероятной.

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

• 1. 0 < w(f) 2^п.
• 2. Ц/®1) = 2^п - w(f).
• 3. Пусть h — еще одна булева функция, h : F? —> F2. Тогда

4. Для любого натурального т ^ п выполнено равенство

где суммирование проводится по всем возможным наборам

• (он,... ,а_т) € F™.
• 5. Величина w(f) принимает нечетное значение тогда и только тогда, когда deg(/) = п.

Читателю в качестве упражнения предлагается доказать сформулированные свойства.

Разложение в ряд Фурье

Для заданного двоичного вектора а — (ai,...,a_n) € через (о, х) обозначим линейную булеву функцию

Для любой функции справедливо единственное разложение вида:

Множество {C_a(f), a G Fg} называется спектром Фурье для булевой функции f(x).