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

В математике симметричная булева функция — это булева функция , значение которой не зависит от порядка ее входных бит, т. е. оно зависит только от количества единиц (или нулей) во входных данных. ^[1] По этой причине их также называют булевыми счетными функциями . ^[2]

Есть 2 ^{п +1} симметричные n -арные булевы функции. Вместо таблицы истинности , традиционно используемой для представления булевых функций, можно использовать более компактное представление для симметричной булевой функции с n -переменной: ( n + 1)-вектор, i -я запись которого ( i = 0, .. ., n ) — значение функции на входном векторе с i единицами. Математически симметричные булевы функции взаимно однозначно соответствуют функциям, которые отображают n+1 элементов в два элемента: $f:\{0,1,...,n\}\rightarrow \{0,1\}$ .

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

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

Выделяют ряд особых случаев: ^[1]

Функция большинства : их значение равно 1 для входных векторов с числом более n/2.
Пороговые функции : их значение равно 1 на входных векторах с k или более для фиксированного k.
Функция «все равно» и «не все равно» : их значения равны 1, когда входные данные (не) все имеют одинаковое значение.
Функции точного подсчета : их значение равно 1 на входных векторах с k для фиксированного k.
- Функция One-Hot или 1-in-n : их значение равно 1 для входных векторов, содержащих ровно одну единицу.
- Однохолодная функция : их значение равно 1 на входных векторах ровно с одним нулем.
Функции сравнения : их значение равно 1 для входных векторов с числом единиц, совпадающим с k по модулю m для фиксированных k , m.
Функция четности : их значение равно 1, если входной вектор имеет нечетное количество единиц.

n-арные версии AND , OR , XOR , NAND , NOR и XNOR также являются симметричными логическими функциями.

Характеристики

В дальнейшем $f_{k}$ обозначает значение функции $f:\{0,1\}^{n}\rightarrow \{0,1\}$ при применении к входному вектору веса $k$ .

Масса

Вес функции можно рассчитать по ее вектору значений:

$|f|=\sum _{k=0}^{n}{\binom {n}{k}}f_{k}$

Алгебраическая нормальная форма

Алгебраическая нормальная форма либо содержит все мономы определенного порядка $m$ , или ни один из них; т.е. преобразование Мёбиуса ${\hat {f}}$ функции также является симметричной функцией. Таким образом, его также можно описать простым ( n +1) битовым вектором, вектором ANF. ${\hat {f}}_{m}$ . АНФ и векторы значений связаны соотношением Мёбиуса: ${\hat {f}}_{m}=\bigoplus _{k_{2}\subseteq m_{2}}f_{k}$ где $k_{2}\subseteq m_{2}$ обозначает все веса k, чье представление по основанию 2 покрывается представлением по основанию 2 для m (следствие теоремы Лукаса ). ^[3] По сути, симметричная булева функция с n-переменной соответствует обычной логической функции с log(n)-переменной, действующей на представление входного веса по основанию 2.

Например, для функций с тремя переменными:

${\begin{array}{lcl}{\hat {f}}_{0}&=&f_{0}\\{\hat {f}}_{1}&=&f_{0}\oplus f_{1}\\{\hat {f}}_{2}&=&f_{0}\oplus f_{2}\\{\hat {f}}_{3}&=&f_{0}\oplus f_{1}\oplus f_{2}\oplus f_{3}\end{array}}$

трех переменных Таким образом, функция большинства с вектором значений (0, 0, 1, 1) имеет вектор ANF (0, 0, 1, 0), т.е.: ${\text{Maj}}(x,y,z)=xy\oplus xz\oplus yz$

Единичный полином гиперкуба

Коэффициенты действительного многочлена, согласующиеся с функцией от $\{0,1\}^{n}$ даны: $f_{m}^{*}=\sum _{k=0}^{m}(-1)^{|k|+|m|}{\binom {m}{k}}f_{k}$ Например, полином мажоритарной функции с тремя переменными имеет коэффициенты (0, 0, 1, -2): ${\text{Maj}}(x,y,z)=(xy+xz+yz)-2(xyz)$

Примеры

16 симметричных булевых функций трех переменных
Значение функции				Вектор значений	Масса	Имя	Разговорное описание	вектор АНФ
0	1	2	3	Вектор значений	Масса	Имя	Разговорное описание	вектор АНФ
Ф	Ф	Ф	Ф	(0, 0, 0, 0)	0	Постоянное ложь	"никогда"	(0, 0, 0, 0)
Ф	Ф	Ф	Т	(0, 0, 0, 1)	1	Трехстороннее И , Порог(3), Счет(3)	"все трое"	(0, 0, 0, 1)
Ф	Ф	Т	Ф	(0, 0, 1, 0)	3	Граф(2), Один простудный	"ровно два"	(0, 0, 1, 1)
Ф	Ф	Т	Т	(0, 0, 1, 1)	4	Большинство, Порог(2)	«большинство», «минимум два»	(0, 0, 1, 0)
Ф	Т	Ф	Ф	(0, 1, 0, 0)	3	Граф(1), Один-горячий	"ровно один"	(0, 1, 0, 1)
Ф	Т	Ф	Т	(0, 1, 0, 1)	4	Трехстороннее исключающее ИЛИ , (нечетная) четность	«один или три»	(0, 1, 0, 0)
Ф	Т	Т	Ф	(0, 1, 1, 0)	6	Не все равны	"один или два"	(0, 1, 1, 0)
Ф	Т	Т	Т	(0, 1, 1, 1)	7	Трехходовое ИЛИ , Порог(1)	«любой», «хотя бы один»	(0, 1, 1, 1)
Т	Ф	Ф	Ф	(1, 0, 0, 0)	1	Трехстороннее НО , счетчик(0)	"никто"	(1, 1, 1, 1)
Т	Ф	Ф	Т	(1, 0, 0, 1)	2	Все равные	«все или ничего»	(1, 1, 1, 0)
Т	Ф	Т	Ф	(1, 0, 1, 0)	4	Трехстороннее XNOR , четность	«ни один или два»	(1, 1, 0, 0)
Т	Ф	Т	Т	(1, 0, 1, 1)	5		"не совсем один"	(1, 1, 0, 1)
Т	Т	Ф	Ф	(1, 1, 0, 0)	4	( пункт о роге )	"максимум один"	(1, 0, 1, 0)
Т	Т	Ф	Т	(1, 1, 0, 1)	5		"не совсем два"	(1, 0, 1, 1)
Т	Т	Т	Ф	(1, 1, 1, 0)	7	Трехходовой NAND	"максимум два"	(1, 0, 0, 1)
Т	Т	Т	Т	(1, 1, 1, 1)	8	Постоянное истинное значение	"всегда"	(1, 0, 0, 0)

См. также

Симметричная функция

Ссылки

^ Jump up to: Перейти обратно: ^а ^б Инго Вегенер , «Сложность симметричных булевых функций», в: Теория вычислений и логика , Конспекты лекций по информатике , том. 270, 1987, стр. 433–442.
^ «BooleanCountingFunction — Документация по языку Wolfram» . ссылка.wolfram.com . Проверено 25 мая 2021 г.
^ Канто, А.; Видео, М. (2005). «Симметричные булевы функции» . Транзакции IEEE по теории информации . 51 (8): 2791–2811. дои : 10.1109/TIT.2005.851743 . ISSN 1557-9654 .

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

[2] «BooleanCountingFunction — Документация по языку Wolfram» . ссылка.wolfram.com . Проверено 25 мая 2021 г.

[3] Канто, А.; Видео, М. (2005). «Симметричные булевы функции» . Транзакции IEEE по теории информации . 51 (8): 2791–2811. дои : 10.1109/TIT.2005.851743 . ISSN 1557-9654 .

[1]

[2]

[3]