Función mayorante

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:

Ejemplo de función mayorante.

$\operatorname {Majority} \left(p_{1},\dots ,p_{n}\right)=\left\lfloor {\frac {1}{2}}+{\frac {\sum _{i=1}^{n}p_{i}-1/2}{n}}\right\rfloor .$

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

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(n^5.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

Entre las propiedades del operador mediano ternario < x,y,z > están:

1. < x,y,y > = y
2. < x,y,z > = < z,x,y >
3. < x,y,z > = < x,z,y >
4. < < x,w,y > ,w,z > = < x,w, < y,w,z > >

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

Referencias

• 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. 

Véase también

• Álgebra de Boole

• Datos: Q1053304
• Multimedia: Majority functions / Q1053304