Forma normal conjuntiva

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda

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 formas canónicas usadas en teoría de circuitos.

Todas las conjunciones de literales y todas las disyunciones de literales están en FNC, pues ellas 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 CNF como un conjunto de conjuntos de literales.

Ejemplos y contraejemplos[editar]

Las siguientes fórmulas están en FNC:

  1. \neg A \wedge (B \vee C)
  2. (A \vee B) \wedge (\neg B \vee C \vee \neg D) \wedge (D \vee \neg E)
  3. A \wedge B.

La última forma está en FNC porque puede ser vista como la conjunción de las dos cláusulas de literales A y B. Esta fórmula es también una forma normal disyuntiva. Las siguientes fórmulas no están en FNC:

  1. \neg (B \vee C)
  2. (A \wedge B) \vee C
  3. A \wedge (B \vee (D \wedge E)).

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:

  1. \neg B \wedge \neg C
  2. (A \vee C) \wedge (B \vee C)
  3. A \wedge (B \vee D) \wedge (B \vee E).

Conversión a FNC[editar]

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:

(X_1 \wedge Y_1) \vee (X_2 \wedge Y_2) \vee \dots \vee (X_n \wedge Y_n).

a FNC se obtiene una fórmula con 2^n cláusulas:

(X_1 \vee \cdots \vee X_{n-1} \vee X_n) \wedge 
(X_1 \vee \cdots \vee X_{n-1} \vee Y_n) \wedge
\cdots \wedge
(Y_1 \vee \cdots \vee Y_{n-1} \vee Y_n).

Esta fórmula contiene 2^n cláusulas; cada cláusula contiene o bien X_i o Y_i para cada i.

Existen transformaciones en CNF 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 Z_1,\ldots,Z_n como sigue:

(Z_1 \vee \cdots \vee Z_n) \wedge
(\neg Z_1 \vee X_1) \wedge (\neg Z_1 \vee Y_1) \wedge
\cdots \wedge 
(\neg Z_n \vee X_n) \wedge (\neg Z_n \vee Y_n).

Una traducción alternativa, la transformación Tseitin, incluye también las cláusulas Z_i \vee \neg X_i \vee \neg Y_i. Con estas cláusulas, la fórmula implica Z_i \equiv X_i \wedge Y_i; esta fórmula muchas veces se considera para "definir" Z_i siendo un nombre para X_i \wedge Y_i.

Lógica de primer orden[editar]

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 CNF

( l_{11} \lor \ldots \lor l_{1n_1} ) \land \ldots \land ( l_{m1} \lor \ldots \lor l_{mn_m} ) , con literales l_{ij}, es comúnmente representado como un conjunto de conjuntos
\{ \{ l_{11} , \ldots , l_{1n_1} \} , \ldots , \{ l_{m1} , \ldots , l_{mn_m} \} \} .

Complejidad computacional[editar]

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 CNF, preservando validez, 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 X_1 \vee \cdots \vee X_k \vee \cdots \vee X_n por dos conjunciones X_1 \vee \cdots \vee X_{k-1} \vee Z y \neg Z \vee X_k \cdots \vee X_n con una nueva variable Z, y repitiendo cuantas veces sea necesario.

Conversión desde lógica de primer orden[editar]

Para convertir lógica de primer orden a FNC:[3]

  1. Convertir a forma normal negativa.
    1. Eliminar implicaciones y equivalencias: sustituir reiteradamente P \rightarrow Q con \lnot P \lor Q; sustituir P \leftrightarrow Q con (P \lor \lnot Q) \land (\lnot P \lor Q). Eventualmente, esto eliminará todas las apariciones de \rightarrow y \leftrightarrow.
    2. Desplace NOTs hacia el interior aplicando varias veces la ley de De Morgan. En concreto, sustituya \lnot (P \lor Q) con (\lnot P) \land (\lnot Q); reemplace \lnot (P \land Q) por (\lnot P) \lor (\lnot Q); reemplace \lnot \lnot P por P; reemplace \lnot (\forall x P (x)) por \exists x \lnot P (x); \lnot (\exists x P (x))) por \forall x \lnot P (x). Después de eso, un \lnot puede ocurrir solo inmediatamente antes de un símbolo de predicado.
  2. Estandarizar variables
    1. Para sentencias como (\forall x P(x)) \lor (\exists x Q(x)) que utilice el mismo nombre de variable dos veces, cambiar el nombre de de una de las variables. Esto evita confusiones posteriores al dejar cuantificadores para más tarde. Por ejemplo, \forall x [\exists y Animal(y) \land \lnot Amores(x, y)] \lor [\exists y Amores(y, x)] se renombra a \forall x [\exists y Animal(y) \land \lnot Amores(x, y)] \lor [\exists z Amores(z,x)].
  3. Skolemizar la declaración
    1. Desplace cuantificadores hacia el exterior: sustituir reiteradamente P \land (\forall x Q(x)) con \forall x (P \land Q(x)); reemplace P \lor (\forall x Q(x)) con \forall x (P \lor Q(x)); reemplace P \land (\exists x Q(x)) con \exists x (P \land Q(x)); reemplace P \lor (\exists x Q(x)) con \exists x (P \lor Q(x)). 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 \land, o \lor.
    2. Reemplace repetidamente \forall x_1 \ldots \forall x_n \; \exists y \; P(y) con \forall x_1 \ldots \forall x_n \; P (f (x_1, \ldots, x_n)), 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.
  4. Descartar todos los cuantificadores universales.
  5. Distribuir ORs hacia adentro sobre ANDs: sustituir reiteradamente P \lor (Q \land R) con (P \lor Q) \land (P \lor R).

A modo de ejemplo, la fórmula que dice "¿Quién 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 {\color{red}{\text{rojo}}}):

\forall x ( \forall y Animal( y ) \color{red}\rightarrow Amores(x, y ) ) \rightarrow ( \exists y Amores( y ,x) )
\forall x ( \forall y \lnot Animal( y ) \lor Amores(x, y ) ) \color{red}\rightarrow ( \exists y Amores( y ,x) ) por 1.1
\forall x \color{red}\lnot ( {\color{red}{\forall y}} \lnot Animal( y ) \lor Amores(x, y ) ) \lor ( \exists y Amores( y ,x) ) por 1.1
\forall x ( \exists y \color{red}\lnot ( \lnot Animal( y ) \color{red}\lor Amores(x, y ) ) ) \lor ( \exists y Amores( y ,x) ) por 1.2
\forall x ( \exists y \color{red}\lnot \color{red}\lnot Animal( y ) \land \lnot Amores(x, y ) ) \lor ( \exists y Amores( y ,x) ) por 1.2
\forall x ( {\color{red}{\exists y}} Animal( y ) \land \lnot Amores(x, y ) ) \lor ( \color{red}\exists \color{red}y Amores( y ,x) ) por 1.2
\forall x ( \exists y Animal( y ) \land \lnot Amores(x, y ) ) \color{red}\lor ( \color{red}\exists \color{red}z Amores( z ,x) ) por 2
\forall x \exists z ( {\color{red}{\exists y}} Animal( y ) \land \lnot Amores(x, y ) ) \color{red}\lor Amores( z ,x) por 3.1
\forall x {\color{red}{\exists z}} \exists y ( Animal( y ) \land \lnot Amores(x, y ) ) \lor Amores( z ,x) por 3.1
\forall x {\color{red}{\exists y}} ( Animal( y ) \land \lnot Amores(x, y ) ) \lor Amores( g(x) ,x) por 3.2
( Animal( f(x) ) \color{red}\land \lnot Amores(x, f(x) ) ) \color{red}\lor Amores( g(x) ,x) por 4
( Animal( f(x) ) \color{red}\lor Amores( g(x) ,x) ) \color{red}\land ( \lnot Amores(x,f(x)) \color{red}\lor Amores(g(x),x) ) por 5
\{ \{ Animal( f(x) ) , Amores( g(x) ,x) \} , \{ \lnot Amores(x,f(x)) , Amores(g(x),x) \} \} (cláusula de representación)

Informalmente, la función skolem g(x) puede ser pensado como dando a la persona por quien es amado x, mientras que f(x) se obtiene el animal (si los hay) que x no ama. La tercera última línea contando desde abajo se lee como "x no ama al animal f(x), o bien x es amado por g(x)".

La segunda última línea de arriba, (Animal(f(x)) \lor Amores(g(x), x)) \land (\lnot Amores(x, f(x)) \lor Amores(g(x), x)), es la FNC.

Véase también[editar]

Nota[editar]

  1. ya que una manera de comprobar una CNF por satisfactibilidad es convertirla en DNF, la satisfactibilidad de la misma se puede comprobar en el tiempo lineal

Referencias[editar]

  1. Tseitin (1968)
  2. Jackson and Sheridan (2004)
  3. Artificial Intelligence: A modern Approach [1995...] Russel and Norvig (en inglés)

Bibliografía[editar]

  • 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[editar]