Función mayorante
# 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:

    $\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:

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

