В математике, симметричной булевой функцией называется такая булева функция, значение которой не зависит от перестановки её входных битов, а зависит только от количества единиц на входеIngo Wegener, «The Complexity of Symmetric Boolean Functions», in: Computation Theory and Logic, Lecture Notes in Computer Science, vol. 270, 1987, pp. 433—442.
Из определения следует, что вместо таблицы истинности, традиционно используемой для представления булевых функций, можно использовать более компактное представление для симметричных булевых функций от n переменных: в виде (n + 1)-мерного вектора, в i-ой позиции которого (i = 0, …, n) записано значение функции для всех входных векторов, содержащих i единиц.
Особые случаи
Особыми случаями симметричных булевых функций являются:
Пороговые функции: принимают значение 1 на всех входных векторах, имеющих k или более единиц для заданного k; Функции точного значения: принимают значение 1 на всех входных векторах, имеющих ровно k единиц для заданного k; Функции-счётчики: принимают значение 1 на всех входных векторах, количество единиц в которых сравнимо с k по модулю m для заданных k и m; Функции чётности: принимают значение 1 на всех входных векторах с чётным числом единиц.
Примечания
Категория:Булева алгебра