En lógica booleana , la función mayoritaria (también llamada operador mediano ) es una función de n entradas a una salida. El valor de la operación es falso cuando n / 2 o más argumentos son falsos y verdadero en caso contrario. Alternativamente, representando los valores verdaderos como 1 y los valores falsos como 0, podemos usar la fórmula
El "-1/2" en la fórmula sirve para romper empates a favor de ceros cuando n es par. Si se omite el término "-1/2", la fórmula se puede usar para una función que rompe los lazos a favor de unos.
La mayoría de las aplicaciones fuerzan deliberadamente un número impar de entradas para no tener que lidiar con la pregunta de qué sucede cuando exactamente la mitad de las entradas son 0 y exactamente la mitad de las entradas son 1. Los pocos sistemas que calculan la función mayoritaria en un número par de las entradas a menudo están sesgadas hacia "0"; producen "0" cuando exactamente la mitad de las entradas son 0; por ejemplo, una puerta mayoritaria de 4 entradas tiene una salida 0 solo cuando aparecen dos o más ceros en sus entradas. [1] En algunos sistemas, el empate se puede romper al azar. [2]
Circuitos booleanos
Una puerta mayoritaria es una puerta lógica que se utiliza en la complejidad de circuitos y otras aplicaciones de los circuitos booleanos . Una puerta 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 encuentra aplicando una función mayoritaria a las tres entradas, aunque con frecuencia esta parte del sumador se divide en varias puertas lógicas más simples.
Muchos sistemas tienen triple redundancia modular ; utilizan la función de mayoría para la decodificación lógica mayoritaria para implementar la corrección de errores .
Un resultado importante en la complejidad del circuito afirma que la función mayoritaria no puede ser calculada por circuitos AC0 de tamaño subexponencial.
Propiedades
Para cualquier x , y , y z , el operador mediana 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 los satisfaga como axiomas es un álgebra mediana .
Fórmulas monótonas para la mayoría
Para n = 1, el operador mediano es solo la operación de identidad unaria x . Para n = 3, el operador mediano ternario se puede expresar usando conjunción y disyunción como xy + yz + zx . Sorprendentemente, esta expresión denota la misma operación independientemente de si el símbolo + se interpreta como inclusivo o exclusivo o .
Para una n arbitraria existe una fórmula monótona para la mayoría de tamaño O ( n 5.3 ). Esto se demuestra mediante el método probabilístico . Por tanto, esta fórmula no es constructiva. [3]
Existen enfoques para una fórmula explícita para la mayoría del tamaño de polinomio:
- Tome 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.
- Combine las salidas de circuitos mayoritarios más pequeños. [4]
- Desaleatorizar la prueba Valiant de una fórmula monótona. [5]
Notas
- ^ Peterson, William Wesley; Weldon, EJ (1972). Códigos de corrección de errores . MIT Press. ISBN 9780262160391.
- ^ Chaouiya, Claudine; Ourrad, Ouerdia; Lima, Ricardo (julio de 2013). "Reglas de la mayoría con ruptura de empates aleatoria en redes reguladoras de genes booleanos". PLoS ONE . 8 (7). Biblioteca Pública de Ciencias. doi : 10.1371 / journal.pone.0069626 .
- ^ Valiente, Leslie (1984). "Fórmulas breves y monótonas para la función mayoritaria". Revista de algoritmos . 5 (3): 363–366. doi : 10.1016 / 0196-6774 (84) 90016-6 .
- ^ Amano, Kazuyuki (2018). "Profundidad de dos circuitos mayoritarios para la mayoría y expansores de lista". 43 ° Simposio Internacional sobre Fundamentos Matemáticos de la Informática (MFCS 2018) . Schloss Dagstuhl – Leibniz-Zentrum fuer Informatik. 117 (81): 1–13. doi : 10.4230 / LIPIcs.MFCS.2018.81 .
- ^ Hoory, Shlomo; Magen, Avner; Pitassi, Toniann (2006). "Circuitos monótonos para la función mayoritaria" . Aproximación, Aleatorización y Optimización Combinatoria. Algoritmos y técnicas . Springer: 410–425. doi : 10.1007 / 11830924_38 .
Referencias
- Knuth, Donald E. (2008). Introducción a los algoritmos combinatorios y funciones booleanas . El arte de la programación informática . 4a . Upper Saddle River, Nueva Jersey: Addison-Wesley. págs. 64–74. ISBN 0-321-53496-4.
Ver también
Medios relacionados con las funciones de la mayoría en Wikimedia Commons