Симметричная булева функция (Vnbbymjncugx Qrlyfg srutenx)

Перейти к навигации Перейти к поиску

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

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

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

[править | править код]

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

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

Примечания

[править | править код]
  1. 1 2 Ingo Wegener, «The Complexity of Symmetric Boolean Functions», in: Computation Theory and Logic, Lecture Notes in Computer Science, vol. 270, 1987, pp. 433—442