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 polinómico.[1]

Ejemplo

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

Referencias
  1. Kazuhisa Makino (2002), A linear time algorithm for recognizing regular Boolean functions 43, Journal of Algorithms: Academic Press, pp. 155-176..
  2. 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 166, Ann. Oper. Res., pp. 243-260 ..
Este artículo ha sido escrito por Wikipedia. El texto está disponible bajo la licencia Creative Commons - Atribución - CompartirIgual. Pueden aplicarse cláusulas adicionales a los archivos multimedia.