Función booleana 2-monótona

Función booleana 2-monótona

En matemáticas, una función booleana 2-monótona (más conocida en inglés como 2-monotone boolean function) es una función booleana monótona ƒ : {0,1}n → {0,1}, para la cual existe un ordenamiento lineal de sus variables w1, w2, ..., wn, de modo que se convierte también en una función booleana regular.[1]

Estas funciones han sido estudiadas en muchos contextos, tales como la threshold logic,[2] teoría de juegos,[3] teoría de hipergrafos[4] y teoría del aprendizaje.[5]

Estas funciones fueron definidas por primera vez en 1965,[6] y desarrolladas más extensamente en 1971.[2]

En teoría de juegos cooperativos, una función booleana 2-monótona es equivalente a un juego completo.[7]

Complejidad computacional

Del punto de vista de la complejidad computacional, se sabe que son computables en tiempo polinomial.[1]

Ejemplo

Toda función umbral es una función booleana 2-monótona, mientras que lo contrario no es cierto.[1]

Referencias

  1. ↑ a b c Kazuhisa Makino (2002), A linear time algorithm for recognizing regular Boolean functions, 43, Journal of Algorithms: Academic Press, pp. 155–176 .
  2. ↑ a b S. Muroga (1971), Threshold Logic and Its Applications, Wiley .
  3. ↑ K.G. Ramamurthy (1990), Coherent Structures and Simple Games, Kluwer .
  4. ↑ V. Chvátal; P.L. Hammer (1977), Aggregation of inequalities in integer programming, 1, Ann. Discrete Math., pp. 145-162 .
  5. ↑ E. Boros; P.L. Hammer, T. Ibaraki, K. Kawakami (1997), Polynomial time recognition of 2-monotonic positive Boolean functions given by an oracle, 26, SIAM J. Comput., pp. 93-109 .
  6. ↑ S.T. Hu (1965), Threshold logic, USA: Univ. of California Press .
  7. ↑ J. Freixas; X. Molinero (2008), On the existence of a minimum integer representation for weighted voting systems, Ann. Oper. Res., pp. 243-260 .

Wikimedia foundation. 2010.

Игры ⚽ Поможем сделать НИР

Mira otros diccionarios:

  • Función booleana regular — En matemáticas, una función booleana regular es una clase particular de funciones booleanas que toma en cuenta el ordenamiento de sus distintos parámetros. Estas funciones son útiles en muchas áreas de la matemática aplicada, tales como la… …   Wikipedia Español

  • Función — (Del lat. functio, onis.) ► sustantivo femenino 1 BIOLOGÍA Actividad o capacidad de acción específica de un ser vivo y de sus órganos: ■ la función del riñón; la función clorofílica. 2 Desempeño de un cargo u oficio: ■ el vicepresidente desempeña …   Enciclopedia Universal

  • Función umbral — En matemáticas, una función umbral (más conocida en inglés como threshold function) es una función booleana monótona ƒ : {0,1}n → {0,1}, donde existen n+1 reales no negativos w1, w2, ..., wn, t tales que:[1] Mediante esta función es pos …   Wikipedia Español

  • Conexión de Galois — En matemática, especialmente en la teoría del orden, una conexión de Galois es una correspondencia particular entre dos conjuntos parcialmente ordenados (abreviado poset en inglés). Las conexiones de Galois generalizan la correspondencia entre… …   Wikipedia Español

Compartir el artículo y extractos

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