Симметричная булева функция - Symmetric Boolean function

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

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

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

Признан ряд особых случаев.[1]

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

использованная литература

  1. ^ а б Инго Вегенер, «Сложность симметричных булевых функций», в: Теория вычислений и логика, Конспект лекций по информатике, т. 270, 1987, с. 433–442.

Смотрите также