Función booleana regular

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 con pesos, respectivamente.

Contenido

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 ƒ : BnB, 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 xBn se cumple la siguiente condición:

ƒ(x) ≤ ƒ(x + uiuj)

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]

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(m2n). 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 polinomial.[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

Referencias

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

Wikimedia foundation. 2010.

Игры ⚽ Нужно решить контрольную?

Mira otros diccionarios:

  • Función booleana 2-monótona — 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… …   Wikipedia Español

  • Función umbral — 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 pos …   Wikipedia Español

  • Operador ternario — En informática un operador ternario (a veces incorrectamente llamado operador terciario) es un operador que toma tres argumentos. Los argumentos y el resultado puede ser de diferentes tipos. Originalmente proviene de BCPL, cuyo sintaxis… …   Wikipedia Español

  • Algoritmo de Floyd-Warshall — En informática, el algoritmo de Floyd Warshall, descrito en 1959 por Bernard Roy, es un algoritmo de análisis sobre grafos para encontrar el camino mínimo en grafos dirigidos ponderados. El algoritmo encuentra el camino entre todos los pares de… …   Wikipedia Español

  • Historia del hardware — La máquina analítica de Charles Babbage, en el Science Museum de Londres. El hardware ha sido un componente importante del proceso de cálculo y almacenamiento de datos desde que se volvió útil para que los valores numéricos fueran procesados y… …   Wikipedia Español

  • Número difuso — Un número difuso es una extensión de un número regular en el sentido que no se refiere a un único valor sino a un conjunto de posibles valores, que varían con un peso entre 0 y 1, llamado función miembro. Un número difuso es así un caso especial… …   Wikipedia Español

Compartir el artículo y extractos

Link directo
Do a right-click on the link above
and select “Copy Link”