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 quebrar los lazos en favor de ceros cuando n es par; una fórmula similar puede utilizarse para una función que quiebra lazos en favor de los unos.

Contenido

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(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 polinomial 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

Véase también


Wikimedia foundation. 2010.

Игры ⚽ Поможем решить контрольную работу

Mira otros diccionarios:

  • Álgebra mediana — En matemática, un álgebra mediana es un conjunto con un operador ternario < x,y,z > que satisface los siguientes axiomas, los cuales generalizan la noción de mediana o función mayorante, como una función booleana: Absorción por la derecha:… …   Wikipedia Español

  • Teorema del sándwich — Saltar a navegación, búsqueda En cálculo, el teorema del sándwich (llamado también teorema de encaje, teorema de intercalación, teorema del enclaustramiento, teorema de compresión,teorema de las funciones mayorante y minorante, criterio del… …   Wikipedia Español

  • Teorema del emparedado — En cálculo, el teorema del emparedado (llamado también teorema de encaje, teorema de intercalación, teorema de estricción, teorema del enclaustramiento, teorema de compresión,teorema de las funciones mayorante y minorante, criterio del sándwich,… …   Wikipedia Español

  • Acotado — El concepto de acotado aparece en matemáticas para referirse a una situación en la que para cierto objeto matemático o un objeto construido a partir del mismo puede establecerse una relación de orden con otro tipo de entidad llamada cota superior …   Wikipedia Español

  • Serie convergente — En matemáticas, una serie se llama serie convergente si la sucesión de sumas parciales tiene un límite en el espacio considerado. De otro modo se llama serie divergente. Contenido 1 Definición formal 2 Ejemplos 3 Convergencia absoluta …   Wikipedia Español

  • Meandro (matemática) — Para otros usos de este término, véase meandro. En matemáticas, un meandro o meandro cerrado es una curva cerrada que no se interseca a sí misma e interseca una línea un cierto número de veces. Puede verse intuitivamente como un camino que cruza… …   Wikipedia Español

Compartir el artículo y extractos

Link directo
… Do a right-click on the link above
and select “Copy Link”