Forma normal negativa

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

En lògica matemàtica, una fórmula és en forma normal negativa si l'operador negació (\lnot, not) només està aplicat a variables, i els únics altres operadors booleans permesos són la conjunció (\land, and) i la disjunció (\lor, or).

La forma normal negativa no és una forma canònica: per exemple a \land (b\lor \lnot c) i (a \land b) \lor (a \land \lnot c) són equivalents, i totes dues estan en forma normal negativa.

En lògica clàssica i el moltes lògiques modals, tota fórmula pot transformar-se en aquesta forma, tot substituint implicacions i equivalències per llurs definicions, usant les Lleis de De Morgan per desplaçar les negacions cap a l'interior de la fórmula, i eliminant dobles negacions. Aquest procés es pot representar mitjançant les següents regles de reescriptura:

\lnot (\forall x. G) \to \exists x. \lnot G
\lnot (\exists x. G) \to \forall x. \lnot G
\lnot \lnot G \to G
\lnot (G_1 \land G_2) \to (\lnot G_1) \lor (\lnot G_2)
\lnot (G_1 \lor G_2) \to (\lnot G_1) \land (\lnot G_2)

Una fórmula en forma normal negativa es pot transformar en les formes normal conjuntiva o normal disjuntiva tot aplicant distributivitat.

Exemples i contraexemples[modifica | modifica el codi]

Totes les fórmules següents estan en forma normal negativa:

(A \vee B) \wedge C
(A \wedge (\lnot B \vee C) \wedge \lnot C) \vee D
A \vee \lnot B
A \wedge \lnot B

El primer exemple també està en forma normal conjuntiva, i els dos últims estan alhora en forma normal conjuntiva i en forma normal disjuntiva, però el segon exemple no està en cap d'aquestes dues formes.

Les fórmules següents no estan en forma normal negativa:

A \Rightarrow B
\lnot (A \vee B)
\lnot (A \wedge B)
\lnot (A \vee \lnot C)

Tot i això, són equivalents (respectivament) a les següents fórmules en forma normal negativa:

\lnot A \vee B
\lnot A \wedge \lnot B
\lnot A \vee \lnot B
\lnot A \wedge C

Referències[modifica | modifica el codi]

  • Robinson, Alan J.A.; Voronkov, Andrei. Handbook of automated reasoning. reprinted. Amsterdam: North Holland, 2001, p. 203 i següents. ISBN 0444829490. 

Enllaços externs[modifica | modifica el codi]