Función mayoritaria

En lógica booleana , la función de mayoría (también llamada operador de mediana ) es la función booleana que se evalúa como falsa cuando la mitad o más de los argumentos son falsos y como verdadera en caso contrario; es decir, el valor de la función es igual al valor de la mayoría de las entradas.

Una puerta lógica de mayoría es una puerta lógica utilizada en la complejidad de circuitos y otras aplicaciones de circuitos booleanos . Una puerta lógica de mayoría devuelve verdadero si y solo si más del 50% de sus entradas son verdaderas.

Por ejemplo, en un sumador completo , la salida de acarreo se obtiene aplicando una función de mayoría a las tres entradas, aunque con frecuencia esta parte del sumador se divide en varias puertas lógicas más simples.

Muchos sistemas tienen redundancia modular triple ; utilizan la función de mayoría para la decodificación lógica de mayoría para implementar la corrección de errores .

Un resultado importante en la complejidad de los circuitos afirma que la función de mayoría no puede ser calculada por circuitos AC0 de tamaño subexponencial.

Para cualesquiera x , y y z , el operador mediano ternario ⟨x , y , z⟩ satisface las siguientes ecuaciones .

• ⟨ x , y , y ⟩ = y
• ⟨ x , y , z ⟩ = ⟨ z , x , y ⟩
• ⟨ x , y , z ⟩ = ⟨ x , z , y ⟩
• ⟨ ⟨ x , w , y ⟩ , w , z ⟩ = ⟨ x , w , ⟨ y , w , z ⟩ ⟩

Un sistema abstracto que satisface estos axiomas es un álgebra mediana .

Otras propiedades útiles de la función operador mediana ternaria incluyen:

• dado ⟨ x , y , z ⟩ = w , ⟨ x , y , w ⟩ = z
• ⟨ ¬x , ¬y , ¬z ⟩ = ¬ ⟨ x , y , z ⟩
• ⟨ x , y , x ⊕ y ⊕ z ⟩ = ⟨ x , y , ¬z ⟩
• ⟨ ¬x , y , x ⊕ y ⊕ z ⟩ = ⟨ ¬x , y , z ⟩

La mayoría de las aplicaciones fuerzan deliberadamente un número impar de entradas para no tener que lidiar con la cuestión de qué sucede cuando exactamente la mitad de las entradas son 0 y exactamente la otra mitad son 1. Los pocos sistemas que calculan la función de mayoría con un número par de entradas suelen estar sesgados hacia "0"; producen "0" cuando exactamente la mitad de las entradas son 0. Por ejemplo, una puerta de mayoría de 4 entradas tiene una salida de 0 solo cuando aparecen dos o más 0 en sus entradas. ^{[ 1 ]} En algunos sistemas, el empate puede resolverse aleatoriamente. ^{[ 2 ]}

Para n = 1, el operador de mediana es simplemente la operación de identidad unaria x . Para n = 3, el operador de mediana ternaria se puede expresar usando conjunción y disyunción como xy + yz + zx .

Para un n arbitrario existe una fórmula monótona para la mayoría de tamaño O( n ^5.3 ). Esto se demuestra utilizando un método probabilístico . Por lo tanto, esta fórmula no es constructiva. ^{[ 3 ]}

Existen métodos para obtener una fórmula explícita para la mayoría de los tamaños polinómicos:

• Toma la mediana de una red de clasificación , donde cada "cable" de comparación e intercambio es simplemente una puerta OR y una puerta AND. La construcción Ajtai – Komlós – Szemerédi (AKS) es un ejemplo.
• Combinar las salidas de los circuitos mayoritarios más pequeños. ^{[ 4 ]}
• Desaleatorizar la demostración de Valiant de una fórmula monótona. ^{[ 5 ]}

• Álgebra booleana (estructura)
• Álgebras booleanas definidas canónicamente
• Algoritmo de votación mayoritaria de Boyer-Moore
• Problema de la mayoría (autómata celular)

• Knuth, Donald E. (2008). Introducción a los algoritmos combinatorios y las funciones booleanas . El arte de la programación informática . Vol.  4a. Upper Saddle River, NJ: Addison-Wesley. pp. 64–74 . ISBN  978-0-321-53496-5.

Contenido multimedia relacionado con las funciones de la mayoría en Wikimedia Commons