Forma normale negativa

Nella logica booleana, una formula è in forma normale negativa (FNN), indicata anche come NNF (acronimo di Negation Normal Form) se l'operatore di negazione ($\lnot$) è applicato solo ai suoi atomi. Inoltre, gli unici operatori consentiti sono congiunzione ($\land$) e disgiunzione ($\lor$).

La forma normale negativa non è una forma canonica: ad esempio, $a\land (b\lor \lnot c)$ e $(a\land b)\lor (a\land \lnot c)$ sono equivalenti, pur essendo entrambe in forma normale negativa.

Nella logica classica e in molte logiche modali, ogni formula può essere espressa in questa forma, applicando ad implicazioni ed equivalenze le rispettive definizioni, usando le leggi di De Morgan ed eliminando le negazioni doppie. Questo processo può essere definito tramite le seguenti formule di riscrittura:

$A\Rightarrow B\to \lnot A\lor 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$

Nelle formule di cui sopra, il simbolo $\Rightarrow$ indica l'implicazione logica nella formula da riscrivere, mentre $\to$ è l'operatore di riscrittura.

Una formula in FNN può essere trasposta nelle forme normali—queste canoniche—congiuntiva o disgiuntiva grazie alla proprietà distributiva degli operatori $\land$ e $\lor$.

Esempi

Le seguenti formule sono tutte in forma normale 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$

Le seguenti formule non sono in forma normale negativa:

$A\Rightarrow B$

$\lnot (A\vee B)$

$\lnot (A\wedge B)$

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

Seguono i rispettivi delle formule di cui sopra in forma normale negativa:

$\lnot A\vee B$

$\lnot A\wedge \lnot B$

$\lnot A\vee \lnot B$

$\lnot A\wedge C$

Voci correlate

• Forma normale disgiuntiva
• Forma normale congiuntiva