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

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

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

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

Вес функции

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

См. также

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

Примечания

Ссылки

• , Annual ACM Symposium on Theory of Computing