- Симметричная булева функция
-
В математике, симметричной булевой функцией называется такая булева функция, значение которой не зависит от перестановки её входных бит, а зависит только от количества единиц на входе.[1]
Из определения следует, что вместо таблицы истинности, традиционно используемой для представления булевых функций, можно использовать более компактное представление для симметричных булевых функций от n переменных: в виде (n + 1)-вектора, в i-ой позиции которого (i = 0, ..., n) записано значение функции для всех входных векторов, содержащих i единиц.
Особые случаи
Особыми случаями симметричных булевых функций являются:[1]
- Пороговые функции: принимают значение 1 на всех входных векторах, имеющих k или более единиц для заданного k
- Функции точного значения: принимают значение 1 на всех входных векторах, имеющих ровно k единиц для заданного k
- Функции счетчики : принимают значение 1 на всех входных векторах, количество единиц в которых сравнимо с k по модулю m для заданных k и m
- Функции четности: принимают значение 1 на всех входных векторах с четным числом единиц.
References
Категория:- Булева алгебра
Wikimedia Foundation. 2010.