Función mayorante

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda

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[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:

  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[editar]

Véase también[editar]