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 posible definir un grafo umbral.
Historia
editarSi bien estas funciones fueron definidas por primera vez en la década de 1960[2] y desarrolladas más extensamente en 1971,[3] están inspiradas en el modelo matemático de neurona de McCulloch-Pitts, propuesto en 1943.[4]
En el contexto de la teoría de juegos, por su parte, estas funciones son además equivalentes a los juegos de mayoría ponderada, siendo estos mencionados por primera vez en 1944[5] y 1956.[6]
Complejidad computacional
editarDel punto de vista de la complejidad computacional, se sabe que son computables en tiempo polinómico. De hecho corresponden a una subclase (estricta[3]) de las funciones booleanas 2-monótonas, las cuales también se pueden computar eficientemente.[1]
Referencias
editar- ↑ a b Kazuhisa Makino (2002), A linear time algorithm for recognizing regular Boolean functions 43, Journal of Algorithms: Academic Press, pp. 155-176..
- ↑ S.T. Hu (1965), Threshold logic, USA: Univ. of California Press.
- ↑ a b S. Muroga (1971), Threshold Logic and Its Applications, Wiley.
- ↑ McCulloch, W.; Pitts, W. (1943). A logical calculus of the ideas immanent in nervous activity (en inglés) 7. Bulletin of Mathematical Biophysics. pp. 115-133.
- ↑ von Neumann, J.; Morgenstern, O. (1944). Theory of Games and Economic Behavior (en inglés). Princeton University Press, NJ.
- ↑ Isbell, J.R. (1956). A class of majority games (en inglés) 7. Ouart J. Math. Oxford Scr. pp. 183-187.
Datos: Q5871012
