Forma normal conjuntiva

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

Les següents fórmules estan en FNC:

$\neg A\wedge (B\vee C)$
$(A\vee B)\wedge (\neg B\vee C\vee \neg D)\wedge (D\vee \neg E)$
$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:

$\neg (B\vee C)$
$(A\wedge B)\vee C$
$A\wedge (B\vee (D\wedge E)).$

Tot i això, són equivalents a les següents, que sí que estan en FNC:

$\neg B\wedge \neg C$
$(A\vee C)\wedge (B\vee C)$
$A\wedge (B\vee D)\wedge (B\vee E).$

Conversió a FNC

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

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

Jackson, Paul; Sheridan, Daniel; editat per H.H. Hoos i D.G. Mitchell «Clause Form Conversions for Boolean Circuits» (pdf) (en anglès). School of Informatics. Springer Verlag Berlin Heidelberg [Edinburgh, Regne Unit], 2005, pàg. 183-198 [Consulta: 5 gener 2014].
Tseitin, G. S. «On the complexity of derivation in propositional calculus» (pdf) (en anglès). Structures in Constructive Mathematics and Mathematical Logic, Part II, Seminars in Mathematics. Institut de Matemàtiques Steklov, 1968, pàg. 115-125.

Vegeu també

Enllaços externs

Aplicació Java per convertir FNC i FND, utilitzant lleis lògiques Arxivat 2012-12-08 at Archive.is (en anglès)
Aplicació 3D que mostra la diferència entre FNC i FND per a diferents Triples De Morgan Arxivat 2010-02-19 a Wayback Machine. (en anglès)