Forma normal negativa

En lògica matemàtica, una fórmula és en forma normal negativa si l'operador negació ($\mathrm{\neg }$, Plantilla:Smallcaps) només està aplicat a variables, i els únics altres operadors booleans permesos són la conjunció ($\wedge$, Plantilla:Smallcaps) i la disjunció ($\vee$, Plantilla:Smallcaps).

La forma normal negativa no és una forma canònica: per exemple $a\wedge (b\vee \mathrm{\neg }c)$ i $(a\wedge b)\vee (a\wedge \mathrm{\neg }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:

$\mathrm{\neg }(\mathrm{\forall }x.G)\to \mathrm{\exists }x.\mathrm{\neg }G$

$\mathrm{\neg }(\mathrm{\exists }x.G)\to \mathrm{\forall }x.\mathrm{\neg }G$

$\mathrm{\neg }\mathrm{\neg }G\to G$

$\mathrm{\neg }(G_1\wedge G_2)\to (\mathrm{\neg }{G}_1)\vee (\mathrm{\neg }{G}_2)$

$\mathrm{\neg }(G_1\vee G_2)\to (\mathrm{\neg }{G}_1)\wedge (\mathrm{\neg }{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

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

$(A\vee B)\wedge C$

$(A\wedge (\mathrm{\neg }B\vee C)\wedge \mathrm{\neg }C)\vee D$

$A\vee \mathrm{\neg }B$

$A\wedge \mathrm{\neg }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$

$\mathrm{\neg }(A\vee B)$

$\mathrm{\neg }(A\wedge B)$

$\mathrm{\neg }(A\vee \mathrm{\neg }C)$

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

$\mathrm{\neg }A\vee B$

$\mathrm{\neg }A\wedge \mathrm{\neg }B$

$\mathrm{\neg }A\vee \mathrm{\neg }B$

$\mathrm{\neg }A\wedge C$

Referències

• Plantilla:Ref-llibre

Enllaços externs

• Cálculo de la forma normal negativa a Lógica informática (2011–12) Plantilla:Es