Функция голосования

Функция голосования (мажоритарная функция, медиана) — тернарная булева функция, равная тому из двух булевых значений, которое больше раз встретилось среди аргументов.^[1][2] То есть функция голосования равна ${\displaystyle 0}$ на наборах, в которых 0 или 1 единица (соответственно 3 или 2 нуля) и равна ${\displaystyle 1}$ на наборах, в которых2 или 3 единицы (соответственно 1 или 0 нулей). Обозначения: ${\displaystyle m}$^[2], ${\displaystyle h}$^[3], ${\displaystyle h_{2}}$.^[4]

Функция голосования
Диаграмма Венна
Определение	${\displaystyle xy\lor xz\lor yz}$
Таблица истинности	${\displaystyle (00010111)}$
Нормальные формы
Дизъюнктивная	${\displaystyle xy+xz+yz}$
Конъюнктивная	${\displaystyle (x+y)(x+z)(y+z)}$
Полином Жегалкина	${\displaystyle xy\oplus xz\oplus yz}$
Принадлежность предполным классам
Сохраняет 0	Да
Сохраняет 1	Да
Монотонна	Да
Линейна	Нет
Самодвойственна	Да

Таблица истинности:

Функция голосования

${\displaystyle x}$	${\displaystyle y}$	${\displaystyle z}$	${\displaystyle h_{2}(x,y,z)}$
0	0	0	0
0	0	1	0
0	1	0	0
0	1	1	1
1	0	0	0
1	0	1	1
1	1	0	1
1	1	1	1

Функция голосования является базисом класса монотонных самодвойственных функций.^[3]

Функция голосования является симметричной функцией. Вектор значений симметричной булевой функции:

${\displaystyle (0011)}$

Функция голосования удовлетворяет условиям ${\displaystyle \langle 0^{2}\rangle }$ и ${\displaystyle \langle 1^{2}\rangle }$, но не удовлетворяет условиям ${\displaystyle \langle 0^{3}\rangle }$ и ${\displaystyle \langle 1^{3}\rangle }$.

Отрицание функции голосования

Не менее важной функцией является отрицание функции голосования ${\displaystyle {\overline {h_{2}}}}$. Оно равно тому булеву значению, которое встречалось среди аргументов меньшее число раз. Таблица истинности:

Отрицание функции голосования

${\displaystyle x}$	${\displaystyle y}$	${\displaystyle z}$	${\displaystyle {\overline {h_{2}}}(x,y,z)}$
0	0	0	1
0	0	1	1
0	1	0	1
0	1	1	0
1	0	0	1
1	0	1	0
1	1	0	0
1	1	1	0

Отрицание функции голосования является базисом класса самодвойственных функций. Она также является симметричной, её вектор значений симметричной функции:

${\displaystyle (1100)}$