Forma normal negativa

En lógica proposicional, una fórmula lógica está en forma normal negativa si, de poseer negaciones, estas únicamente afectan las fórmulas atómicas, y si además los únicos conectivos existentes son {$\lnot ,\lor ,\land$}. En lógica clásica cada fórmula puede ser representada de esta manera reemplazando implicaciones y equivalencias por sus definiciones, utilizando las Leyes de De Morgan para distribuir las negaciones dentro de cada átomo, o bien eliminando las dobles negaciones. Este proceso puede representarse utilizando las siguientes reglas:

$\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 puede ponerse en las formas más fuertes de forma normal conjuntiva o forma normal disyuntiva, aplicando las leyes de distributividad.

Ejemplos y contraejemplos

Las siguientes fórmulas están todas 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 ejemplo está también en forma normal conjuntiva y las dos últimas estántanto en forma normal conjuntiva como forma normal disyuntiva, pero el segundo ejemplo no se encuentra en ninguno de ellos.

Las siguientes fórmulas no están en forma normal negativa:

$A\Rightarrow B$

$\lnot (A\vee B)$

$\lnot (A\wedge B)$

$\lnot (A\vee \lnot C)$

Sin embargo, son respectivamente equivalentes a las siguientes fórmulas en forma normal negativa:

$\lnot A\vee B$

$\lnot A\wedge \lnot B$

$\lnot A\vee \lnot B$

$\lnot A\wedge C$

Referencias

• Alan J.A. Robinson and Andrei Voronkov, Handbook of Automated Reasoning 1:203ff (2001) ISBN 0444829490. (en inglés)

Enlaces externos

• Applet de Java para convertir fórmulas lógicas a forma normal negativa, mostrando las reglas utilizadas.

• Datos: Q1640479