Función booleana regular

En matemáticas, una función booleana regular es una clase particular de funciones booleanas que toma en cuenta el ordenamiento de sus distintos parámetros.

Estas funciones son útiles en muchas áreas de la matemática aplicada, tales como la programación lógica, teoría de hipergrafos, teoría de juegos, entre otros, donde son equivalentes a clases particulares de formas normales disyuntivas, hipergrafos minimales y juegos de mayoría ponderada, respectivamente.

Historia

La noción de regularidad fue introducida por primera vez en 1962,^[1] por el matemático R.O. Winder, en su tesis de doctorado.^[2]

Definición formal

Formalmente, dado un conjunto finito N = {1, ..., n}, cuyos elementos están linealmente ordenados, una función booleana regular es una función ƒ : Bⁿ → B, donde:

B = {0,1}, con 0 y 1 los valores booleanos falso y verdadero, respectivamente,
n correspondiente al número de parámetros de la función,

y tal que para todo x ∈ Bⁿ se cumple la siguiente condición:

ƒ(x) ≤ ƒ(x + u_i — u_j)

donde u_k es el k-ésimo vector unidad (0,...,0,1,0,...,0) y para todo par (i, j) ∈ N × N, con x_i=0 y x_j=1, y además i "mayor o igual que" j según el orden lineal de N.^[1]

Ejemplos

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.^[1]

Complejidad computacional

En complejidad computacional, estas funciones son muy estudiadas en la actualidad. 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). Actualmente existen algoritmos que pueden decidir esto en tiempo lineal.^[3]

En 1979 se demostró por primera vez que también es posible dualizar una función booleana regular en tiempo polinómico.^[4] Actualmente, esto también puede hacerse en tiempo lineal, y de hecho además se sabe que la función dual de una función regular tiene como máximo (n—2)m+1 términos (donde m es el número de cláusulas de la función representada como FND).^[1]

Véase también

Función booleana 2-monótona

Referencias

↑ ^a ^b ^c ^d Peled, U.N.; Simeone, B. (1994), An O(nm)-time algorithm for computing the dual of a regular Boolean function (en inglés) 49, Discrete applied mathematics: Elsevier, pp. 309-323 .
↑ ^a ^b Winder, R.O. (1962), Threshold logic (en inglés), Ph.D. Dissertation: Department of Mathematics, Princeton University, Princeton, NJ .
↑ Makino, K. (2002), A linear time algorithm for recognizing regular Boolean functions (en inglés) 43, Journal of Algorithms, pp. 155-176 .
↑ Hammer, P.L.; Peled, U.N.; Pollatschek, M.A. (1979), An algorithm to dualize a regular switching function (en inglés) 28, IEEE Trans. Comput., pp. 238-243 .

Datos: Q5870960

[PS94-1] Peled, U.N.; Simeone, B. (1994), An O(nm)-time algorithm for computing the dual of a regular Boolean function (en inglés) 49, Discrete applied mathematics: Elsevier, pp. 309-323 .

[Win62-2] Winder, R.O. (1962), Threshold logic (en inglés), Ph.D. Dissertation: Department of Mathematics, Princeton University, Princeton, NJ .

[3] Makino, K. (2002), A linear time algorithm for recognizing regular Boolean functions (en inglés) 43, Journal of Algorithms, pp. 155-176 .

[4] Hammer, P.L.; Peled, U.N.; Pollatschek, M.A. (1979), An algorithm to dualize a regular switching function (en inglés) 28, IEEE Trans. Comput., pp. 238-243 .

[1]

[2]

[3]

[4]