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

Шаблон:Math-stub Шаблон:Булева функция Функция голосования (мажоритарная функция, медиана) — тернарная булева функция, равная тому из двух булевых значений, которое больше раз встретилось среди аргументов.Шаблон:Sfn То есть функция голосования равна $0$ на наборах, в которых 0 или 1 единица (соответственно 3 или 2 нуля) и равна $1$ на наборах, в которых2 или 3 единицы (соответственно 1 или 0 нулей). Обозначения: $m$Шаблон:Sfn, $h$Шаблон:Sfn, $h_2$.Шаблон:Sfn

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

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

$x$	$y$	$z$	$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

Функция голосования является базисом класса монотонных самодвойственных функций.Шаблон:Sfn

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

$(0011)$

Функция голосования удовлетворяет условиям $⟨0^2⟩$ и $⟨1^2⟩$, но не удовлетворяет условиям $⟨0^3⟩$ и $⟨1^3⟩$.

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

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

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

$x$	$y$	$z$	$\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

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

$(1100)$

Литература

• Шаблон:Книга
• Шаблон:Cite web