Сбалансированная булева функция

В булевой алгебре, сбалансированной булевой функцией называется такая булева функция, которая на всей области определения функции принимает значение 0 ровно столько же раз, как и значение 1. Другими словами, в таблице истинности сбалансированной булевой функции количество входных комбинаций, при которых функция принимает значение 0, совпадает с количеством комбинаций, при которых функция принимает значение 1. Сбалансированные функции также называются уравновешенными или равновероятными, поскольку при равновероятных случайных значениях на входе или при переборе всех комбинаций по таблице истинности вероятность получения на выходе значения 1 равна 1/2.

Простейшим примером сбалансированной булевой функции является функция, принимающая значение 1, если на входе четное число, и 0, если на входе нечетное число (или наоборот).

Использование

Сбалансированные булевы функции используются в криптографии.

Вес функции

• Т.к. равновероятная функция на одной половине аргументов принимает значение 1, а на другой - 0, то её вес равен 2^n-1

См. также

• Бент-функция

Ссылки

• Balanced boolean functions that can be evaluated so that every input bit is unlikely to be read, Annual ACM Symposium on Theory of Computing