La noción de regularidad fue introducida por primera vez en 1962,[1] por el matemático R.O.
[2] Formalmente, dado un conjunto finito N = {1, ..., n}, cuyos elementos están linealmente ordenados, una función booleana regular es una función ƒ : Bn → B, donde: y tal que para todo x ∈ Bn se cumple la siguiente condición: donde uk es el k-ésimo vector unidad (0,...,0,1,0,...,0) y para todo par (i, j) ∈ N × N, con xi=0 y xj=1, y además i "mayor o igual que" j según el orden lineal de N.[1] Dada una función umbral (correspondientes a las funciones características de las soluciones de una inecuación lineal con coeficientes no negativos en variables booleanas) siempre es posible permutar sus variables por medio de un ordenamiento lineal, de modo que la función queda regular.
Como consecuencia de este hecho, las funciones umbrales además son 2-monótonas.
El método descrito inicialmente por Winder en su tesis doctoral,[2] ya da cuenta de un algoritmo que puede decidir si una función dada es o no regular en tiempo O(m²n).
[3] En 1979 se demostró por primera vez que también es posible dualizar una función booleana regular en tiempo polinómico.