Forma normal conjuntiva

De Viquipèdia
Dreceres ràpides: navegació, cerca

En lògica booleana, una fórmula està en forma normal conjuntiva (FNC) si correspon a una conjunció de clàusules, on una clàusula és una disjunció de literals, on un literal i el seu complement no poden aparèixer en la mateixa clàusula. Aquesta definició és similar a la de formes canòniques emprades en teoria de circuits.

Totes les conjuncions de literals i totes les disjuncions de literals estan en FNC, car poden ser vistes, respectivament, com a conjuncions de clàusules d'un literal, i com a conjuncions d'una única clàusula. De la mateixa manera que en forma normal disjuntiva (FND), els únics connectors lògics que poden aparèixer en una fórmula en FNC són la conjunció, la disjunció i la negació. L'operador negació només pot aplicar-se a un literal, i no a una clàusula completa, la qual cosa significa que només pot precedir una variable proposicional.

Exemples i contraexemples[modifica | modifica el codi]

Les següents fórmules estan 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.

L'última forma està en FNC perquè pot ser vista com a la conjunció de les dues clàusules de literals A i B. Aquesta fórmula és també una forma normal disjuntiva. Les següents fórmules no estan en FNC:

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

Tot i això, són equivalents a les següents, que sí estan 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ó a FNC[modifica | modifica el codi]

Cada fórmula proposicional es pot convertir en una fórmula equivalent que estigui en FNC. Aquesta transformació es basa en regles sobre equivalències lògiques: la doble negació, les lleis de De Morgan i la distributivitat.

Tot i això, hi ha alguns casos en què aquesta conversió pot produir un creixement exponencial de la grandària de la fórmula. Per exemple, en convertir la següent fórmula:

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

a FNC s'obté una fórmula amb 2^n clàusules:

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

Complexitat computacional[modifica | modifica el codi]

Un important conjunt de problemes en complexitat computacional inclou el trobar assignacions per les variables d'una fórmula expressada en forma normal conjuntiva, de tal manera que la fórmula sigui certa. El problema k-SAT és un problema computacional que consisteix en trobar una assignació satisfactible per a una fórmula expressada en FNC tal que cada disjunció contingui, com a molt, k variables.

El problema 3-SAT és NP-complet (de la mateixa forma que qualsevol altre problema k-SAT amb k > 2), mentre que el problema 2-SAT és resoluble en temps polinòmic.

Bibliografia[modifica | modifica el codi]

Vegeu també[modifica | modifica el codi]

Enllaços externs[modifica | modifica el codi]