Forma normal conjuntiva
En lógica booleana, una fórmula está en forma normal conjuntiva (FNC) si corresponde a una conjunción de cláusulas, donde una cláusula es una disyunción de literales, donde un literal y su complemento no pueden aparecer en la misma cláusula. Esta definición es similar a la de forma de productos de sumas usadas en teoría de circuitos.
Todas las conjunciones de literales y todas las disyunciones de literales están en FNC, puesto que pueden ser vistas, respectivamente, como conjunciones de cláusulas de un literal, y como conjunciones de una única cláusula. Al igual que en una forma normal disyuntiva (FND), los únicos conectivos lógicos que pueden aparecer en una fórmula en FNC son la conjunción, disyunción y negación. El operador negación solo puede aplicarse a un literal, y no a una cláusula completa, lo que significa que este sólo puede preceder a una variable proposicional o un símbolo de predicado.
En demostración automática de teoremas, la noción de «forma normal clausal» se utiliza frecuentemente en un sentido más estricto, significando una representación particular de una fórmula FNC como un conjunto de conjuntos de literales.
Ejemplos y contraejemplos
Las siguientes fórmulas están en FNC:
La última forma está en FNC porque puede ser vista como la conjunción de las dos cláusulas de literales y . Esta fórmula es también una forma normal disyuntiva. Las siguientes fórmulas no están en FNC:
Cada fórmula puede ser el equivalente escrita como una fórmula en forma normal conjuntiva. En particular, este es el caso para los tres contraejemplos recién mencionados; que son, respectivamente, equivalentes a las siguientes tres fórmulas, que están en forma normal conjuntiva:
Conversión a FNC
Cada fórmula proposicional puede convertirse en una fórmula equivalente que está en FNC. Esta transformación se basa en reglas sobre equivalencias lógicas: la doble negación, las leyes de De Morgan, y la distributividad.
Sin embargo, hay algunos casos en que dicha conversión puede producir un crecimiento exponencial del tamaño de la fórmula.
Por ejemplo, al convertir la siguiente fórmula:
a FNC se obtiene una fórmula con cláusulas:
Esta fórmula contiene cláusulas; cada cláusula contiene o bien o para cada .
Existen transformaciones en FNC que evitan un crecimiento exponencial en el tamaño preservando la satisfacibilidad en lugar de equivalencia.[1][2] Estas transformaciones están garantizadas para aumentar solo linealmente el tamaño de la fórmula, pero introduce nuevas variables. Por ejemplo, la fórmula anterior puede ser transformada en FNC adicionando variables como sigue:
Una traducción alternativa, la transformación Tseitin, incluye también las cláusulas . Con estas cláusulas, la fórmula implica ; esta fórmula muchas veces se considera para "definir" siendo un nombre para .
Lógica de primer orden
En la lógica de primer orden, forma normal conjuntiva puede tomarse más para producir la forma normal clausal de una fórmula lógica, que se puede utilizar luego para realizar la resolución de primer orden. En una resolución basada en la provisión automatizada de teorema, una fórmula FNC
, con literales , es comúnmente representado como un conjunto de conjuntos | |||||||||||||||||||
. |
Complejidad computacional
Un importante conjunto de problemas en complejidad computacional incluye el encontrar asignaciones para las variables de una fórmula expresada como forma normal conjuntiva, de modo que la fórmula sea verdadera. El problema k-SAT es un problema computacional que consiste en encontrar una asignación satisfacible para una fórmula expresada en FNC tal que cada disyunción contenga la mayor cantidad de variables k posibles. El problema 3-SAT es NP-completo (así como cualquier otro problema k-SAT con k>2), mientras que el problema 2-SAT es resoluble en tiempo polinómico. Como consecuencia,[nota 1] la tarea de convertir una fórmula a una FND, preservando la satisfactibilidad, es NP-hard; dualmente, convertido en FNC, preservando satisfactilidad, también es NP-hard; por lo tanto la equivalencia preservando conversión en FND o FNC también es un NP-hard.
Los problemas típicos en este caso involucran fórmulas en "3FNC": La forma normal conjuntiva con no más de tres variables por conjunción. Ejemplos de tales fórmulas encontradas en la práctica pueden ser muy grandes, por ejemplo, con 100.000 variables y 1.000.000 conjunciones.
Una fórmula en FNC se puede convertir en una fórmula equisatisfiable en "kFNC" (para k> = 3) sustituyendo cada uno en conjunción con más de variables k por dos conjunciones y con una nueva variable , y repitiendo cuantas veces sea necesario.
Conversión desde lógica de primer orden
Para convertir lógica de primer orden a FNC:[3]
- Convertir a forma normal negativa.
- Eliminar implicaciones y equivalencias: sustituir reiteradamente con ; sustituir con . Eventualmente, esto eliminará todas las apariciones de y .
- Desplazar NOTs hacia el interior aplicando varias veces la ley de De Morgan. En concreto, sustituya con ; reemplace por ; reemplace por reemplace por ; por . Después de eso, un puede ocurrir solo inmediatamente antes de un símbolo de predicado.
- Estandarizar variables
- Para sentencias como que utilice el mismo nombre de variable dos veces, cambiar el nombre de una de las variables. Esto evita confusiones posteriores al dejar cuantificadores para más tarde. Por ejemplo, se renombra a .
- Skolemizar la declaración
- Desplazar cuantificadores hacia el exterior: sustituir reiteradamente con ; reemplace con ; reemplace con ; reemplace con . Estos reemplazos conservan la equivalencia, ya que el paso de normalización variable anterior se aseguró de que x no ocurre en P. Después de estos reemplazos, un cuantificador puede ocurrir solo en el prefijo inicial de la fórmula, pero nunca dentro de un , o .
- Reemplazar repetidamente con , donde f es un nuevo símbolo de la función n-aria, la denominada "función de Skolem". Este es el único paso que conserva solamente satisfacibilidad en lugar de equivalencia. Se eliminan todos los cuantificadores existenciales.
- Descartar todos los cuantificadores universales.
- Distribuir ORs hacia adentro sobre ANDs: sustituir reiteradamente con .
A modo de ejemplo, la fórmula que dice "Quien ama a todos los animales, es a su vez amado por alguien" se convierte en FNC (y posteriormente en forma de cláusula en la última línea) de la siguiente manera (resaltando regla de sustitución redichas con ):
por 1.1 | ||||||||||||||||||||||||||||||||||||
por 1.1 | ||||||||||||||||||||||||||||||||||||
por 1.2 | ||||||||||||||||||||||||||||||||||||
por 1.2 | ||||||||||||||||||||||||||||||||||||
por 1.2 | ||||||||||||||||||||||||||||||||||||
por 2 | ||||||||||||||||||||||||||||||||||||
por 3.1 | ||||||||||||||||||||||||||||||||||||
por 3.1 | ||||||||||||||||||||||||||||||||||||
por 3.2 | ||||||||||||||||||||||||||||||||||||
por 4 | ||||||||||||||||||||||||||||||||||||
por 5 | ||||||||||||||||||||||||||||||||||||
(cláusula de representación) |
Informalmente, la función skolem puede ser pensado como dando a la persona por quien es amado , mientras que se obtiene el animal (si los hay) que no ama. La tercera última línea contando desde abajo se lee como " no ama al animal , o bien es amado por ".
La segunda última línea de arriba, , es la FNC.
Véase también
Nota
- ↑ ya que una manera de comprobar una FNC por satisfactibilidad es convertirla en DNF, la satisfactibilidad de la misma se puede comprobar en el tiempo lineal
Referencias
Bibliografía
- Paul Jackson, Daniel Sheridan: Clause Form Conversions for Boolean Circuits. In: Holger H. Hoos, David G. Mitchell (Eds.): Theory and Applications of Satisfiability Testing, 7th International Conference, SAT 2004, Vancouver, BC, Canada, May 10–13, 2004, Revised Selected Papers. Lecture Notes in Computer Science 3542, Springer 2005, pp. 183–198
- G.S. Tseitin: On the complexity of derivation in propositional calculus. In: Slisenko, A.O. (ed.) Structures in Constructive Mathematics and Mathematical Logic, Part II, Seminars in Mathematics (translated from Russian), pp. 115–125. Steklov Mathematical Institute (1968)
Enlaces externos
- Hazewinkel, Michiel, ed. (2001), «Forma normal conjuntiva», Encyclopaedia of Mathematics (en inglés), Springer, ISBN 978-1556080104 .
- Conversión de fnc a fnd usando computación grid (en inglés)
- Conversión de fnc a fnd usando computación grid en paralelo (en inglés)
- Esta obra contiene una traducción derivada de «Conjunctive normal form» de Wikipedia en inglés, concretamente de esta versión, publicada por sus editores bajo la Licencia de documentación libre de GNU y la Licencia Creative Commons Atribución-CompartirIgual 4.0 Internacional.
Datos: Q846564