В математике , симметричной булевой функцией называется такая булева функция , значение которой не зависит от перестановки её входных бит, а зависит только от количества единиц на входе .

Из определения следует, что вместо таблицы истинности , традиционно используемой для представления булевых функций, можно использовать более компактное представление для симметричных булевых функций от n переменных: в виде ( n + 1)-мерного вектора, в i -ой позиции которого ( i = 0, …, n ) записано значение функции для всех входных векторов, содержащих i единиц.

Особые случаи

Особыми случаями симметричных булевых функций являются :

• Пороговые функции : принимают значение 1 на всех входных векторах, имеющих k или более единиц для заданного k ;
• Функции точного значения : принимают значение 1 на всех входных векторах, имеющих ровно k единиц для заданного k ;
• Функции-счётчики : принимают значение 1 на всех входных векторах, количество единиц в которых сравнимо с k по модулю m для заданных k и m ;
• Функции чётности : принимают значение 1 на всех входных векторах с чётным числом единиц.

Примечания