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:

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

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 FNC que evitan un crecimiento exponencial en el tamaño preservando la satisfacibilidad en lugar de equivalencia.​​ 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

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

$($

$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

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,​ 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 $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

Para convertir lógica de primer orden a FNC:​

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. Desplazar 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 xP(x))$ por $\exists x\lnot P(x)$; $\lnot (\exists xP(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 xP(x))\lor (\exists xQ(x))$ 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, $\forall x[\exists yAnimal(y)\land \lnot Amores(x,y)]\lor [\exists yAmores(y,x)]$ se renombra a $\forall x[\exists yAnimal(y)\land \lnot Amores(x,y)]\lor [\exists zAmores(z,x)]$.
3. Skolemizar la declaración
   1. Desplazar cuantificadores hacia el exterior: sustituir reiteradamente $P\land (\forall xQ(x))$ con $\forall x(P\land Q(x))$; reemplace $P\lor (\forall xQ(x))$ con $\forall x(P\lor Q(x))$; reemplace $P\land (\exists xQ(x))$ con $\exists x(P\land Q(x))$; reemplace $P\lor (\exists xQ(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. Reemplazar 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 "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 ${\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

• Forma normal algebraica
• Forma normal disyuntiva
• Cláusula de Horn
• Algoritmo Quine–McCluskey

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)

• Datos: Q846564