Función mayorante
![](http://upload.wikimedia.org/wikipedia/commons/thumb/c/cd/Majority_Function_Example_Proof_1_Title.png/220px-Majority_Function_Example_Proof_1_Title.png)
En lógica binaria, la función mayorante u operador mediano es una función matemática que va desde n entradas a una salida. El valor de la operación es falso cuando n/2 o más argumentos son falsos, y verdadera en otro caso. Alternativamente, sean 1 los valores verdaderos, y 0 los falsos, se puede definir mediante la siguiente fórmula:
donde el "−1/2" sirve para romper el empate a favor de los ceros cuando n es par; una fórmula similar puede utilizarse para una función que rompa el empate a favor de los unos.
Fórmulas monótonas para mayoricidad
[editar]Para n = 1 el operador mediano es el operador de identidad unaria x. Para n = 3 el operador mediano ternario puede expresarse usando conjunciones y disyunciones de la forma xy + yz + zx. Esta expresión denota la misma operación independientemente de si el símbolo + es interpretado como un o inclusivo o un o exclusivo.
Para un n arbitrario existe una fórmula monótona para mayoraciones de tamaño O(n5.3) (Valiant, 1984). Esto fue demostrado utilizando métodos probabilísticos. Por lo tanto, esta fórmula es no-constructiva. Sin embargo, puede obtenerse de manera explícita una fórmula mayorante de tamaño polinómico usando la red de ordenación de Ajtai, Komlós y Szemerédi.
Propiedades
[editar]Entre las propiedades del operador mediano ternario < x,y,z > están:
- < 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 el álgebra mediana.
Referencias
[editar]- Valiant, L. (1984), «Short monotone formulae for the majority function», Journal of Algorithms 5: 363-366, doi:10.1016/0196-6774(84)90016-6..
- Knuth, Donald E. (2008). Introduction to combinatorial algorithms and Boolean functions. The Art of Computer Programming. 4.0. Upper Saddle River, NJ: Addison-Wesley. pp. 64-74. ISBN 0-321-53496-4.