Forma normal de negación

Fórmula lógica con NO solo en variables

En lógica matemática , una fórmula está en forma normal de negación (NNF) si el operador de negación ( , no ) solo se aplica a variables y los únicos otros operadores booleanos permitidos son la conjunción ( , y ) y la disyunción ( , o ). ${\displaystyle \lnot }$ ${\displaystyle \land }$ ${\displaystyle \lor }$

La forma normal de negación no es una forma canónica : por ejemplo, y son equivalentes, y ambos están en forma normal de negación. ${\displaystyle a\land (b\lor \lnot c)}$ ${\displaystyle (a\land b)\lor (a\land \lnot c)}$

En la lógica clásica y en muchas lógicas modales , cada fórmula puede adoptar esta forma reemplazando las implicaciones y equivalencias por sus definiciones, utilizando las leyes de De Morgan para empujar la negación hacia adentro y eliminando las negaciones dobles. Este proceso puede representarse utilizando las siguientes reglas de reescritura : ^[1]

${\displaystyle {\begin{aligned}A\Rightarrow B&~\to ~\lnot A\lor B\\A\Leftrightarrow B&~\to ~(\lnot A\lor B)\land (A\lor \lnot B)\\\lnot (A\lor B)&~\to ~\lnot A\land \lnot B\\\lnot (A\land B)&~\to ~\lnot A\lor \lnot B\\\lnot \lnot A&~\to ~A\\\lnot \exists xA&~\to ~\forall x\lnot A\\\lnot \forall xA&~\to ~\exists x\lnot A\end{aligned}}}$

(En estas reglas, el símbolo indica implicación lógica en la fórmula que se está reescribiendo, y es la operación de reescritura). ${\displaystyle \Rightarrow }$ ${\displaystyle \to }$

La transformación a la forma normal de negación puede aumentar el tamaño de una fórmula solo de manera lineal: el número de ocurrencias de fórmulas atómicas permanece igual, el número total de ocurrencias de y no cambia, y el número de ocurrencias de en la forma normal está limitado por la longitud de la fórmula original. ${\displaystyle \land }$ ${\displaystyle \lor }$ ${\displaystyle \lnot }$

Una fórmula en forma normal de negación se puede poner en la forma normal conjuntiva más fuerte o en la forma normal disyuntiva aplicando distributividad . La aplicación repetida de la distributividad puede aumentar exponencialmente el tamaño de una fórmula. En la lógica proposicional clásica , la transformación a la forma normal de negación no afecta las propiedades computacionales: el problema de satisfacibilidad continúa siendo NP-completo y el problema de validez continúa siendo co-NP-completo . Para fórmulas en forma normal conjuntiva, el problema de validez es solucionable en tiempo polinomial, y para fórmulas en forma normal disyuntiva, el problema de satisfacibilidad es solucionable en tiempo polinomial.

Ejemplos y contraejemplos

Las siguientes fórmulas están todas en forma normal de negación:

${\displaystyle {\begin{aligned}(A&\vee B)\wedge C\\(A&\wedge (\lnot B\vee C)\wedge \lnot C)\vee D\\A&\vee \lnot B\\A&\wedge \lnot B\end{aligned}}}$

El primer ejemplo también está en forma normal conjuntiva y los dos últimos están tanto en forma normal conjuntiva como en forma normal disyuntiva , pero el segundo ejemplo no está en ninguna de las dos.

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

${\displaystyle {\begin{aligned}A&\Rightarrow B\\\lnot (A&\vee B)\\\lnot (A&\wedge B)\\\lnot (A&\vee \lnot C)\end{aligned}}}$

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

${\displaystyle {\begin{aligned}\lnot A&\vee B\\\lnot A&\wedge \lnot B\\\lnot A&\vee \lnot B\\\lnot A&\wedge C\end{aligned}}}$

Véase también

• Forma normal conjuntiva
• Forma normal disyuntiva

Notas

1. Robinson y Voronkov 2001, pág. 204.

Referencias

• Robinson, John Alan ; Voronkov, Andrei , eds. (2001). Manual de razonamiento automatizado . Vol. 1. MIT Press . Págs. 203 y siguientes. ISBN . 0444829490.

Enlaces externos

• Subprograma Java para convertir fórmulas lógicas a la forma normal de negación, mostrando las leyes utilizadas