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]
YouTube Encyclopedic
-
1/1Views:2 064
-
0626 Desigualdad de Boole
Transcription
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
- ↑ a b c Kazuhisa Makino (2002), A linear time algorithm for recognizing regular Boolean functions 43, Journal of Algorithms: Academic Press, pp. 155-176..
- ↑ a b S. Muroga (1971), Threshold Logic and Its Applications, Wiley..
- ↑ K.G. Ramamurthy (1990), Coherent Structures and Simple Games, Kluwer..
- ↑ V. Chvátal; P.L. Hammer (1977), Aggregation of inequalities in integer programming 1, Ann. Discrete Math., pp. 145-162 ..
- ↑ 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..
- ↑ S.T. Hu (1965), Threshold logic, USA: Univ. of California Press..
- ↑ J. Freixas; X. Molinero (2008), On the existence of a minimum integer representation for weighted voting systems 166, Ann. Oper. Res., pp. 243-260 ..
| Control de autoridades |
|
|---|
Datos: Q5870956
Esta página se editó por última vez el 12 oct 2019 a las 07:46.