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

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

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

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

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

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

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

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

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

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

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

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

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

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

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >