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 aparecen en una fórmula en FNC son la conjunción, disyunción y negación. El operador negación sólo 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)).

Sin embargo, son equivalentes a las siguientes, que sí están en FNC:

  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).

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 a lo más k variables.

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.

Véase también[editar]

Referencias[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]