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

editar

Si 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

editar

Del 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
  1. a b Kazuhisa Makino (2002), A linear time algorithm for recognizing regular Boolean functions 43, Journal of Algorithms: Academic Press, pp. 155-176 ..
  2. S.T. Hu (1965), Threshold logic, USA: Univ. of California Press .
  3. a b S. Muroga (1971), Threshold Logic and Its Applications, Wiley .
  4. 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. 
  5. von Neumann, J.; Morgenstern, O. (1944). Theory of Games and Economic Behavior (en inglés). Princeton University Press, NJ. 
  6. Isbell, J.R. (1956). A class of majority games (en inglés) 7. Ouart J. Math. Oxford Scr. pp. 183-187.