Forma normale negativa

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

La forma normale negativa non è una forma canonica: ad esempio, ${\displaystyle a\land (b\lor \lnot c)}$ e ${\displaystyle (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:

${\displaystyle A\Rightarrow B\to \lnot A\lor B}$

${\displaystyle \lnot (A\lor B)\to \lnot A\land \lnot B}$

${\displaystyle \lnot (A\land B)\to \lnot A\lor \lnot B}$

${\displaystyle \lnot \lnot A\to A}$

${\displaystyle \lnot \exists xA\to \forall x\lnot A}$

${\displaystyle \lnot \forall xA\to \exists x\lnot A}$

Nelle formule di cui sopra, il simbolo ${\displaystyle \Rightarrow }$ indica l'implicazione logica nella formula da riscrivere, mentre ${\displaystyle \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 ${\displaystyle \land }$ e ${\displaystyle \lor }$.

Esempi

Le seguenti formule sono tutte in forma normale negativa:

${\displaystyle (A\vee B)\wedge C}$

${\displaystyle (A\wedge (\lnot B\vee C)\wedge \lnot C)\vee D}$

${\displaystyle A\vee \lnot B}$

${\displaystyle A\wedge \lnot B}$

Le seguenti formule non sono in forma normale negativa:

${\displaystyle A\Rightarrow B}$

${\displaystyle \lnot (A\vee B)}$

${\displaystyle \lnot (A\wedge B)}$

${\displaystyle \lnot (A\vee \lnot C)}$

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

${\displaystyle \lnot A\vee B}$

${\displaystyle \lnot A\wedge \lnot B}$

${\displaystyle \lnot A\vee \lnot B}$

${\displaystyle \lnot A\wedge C}$

Note

1. Luigia Carlucci Aiello, Fiora Pirri, Strutture, logica, linguaggi, 1ª ed., Milano, Pearson Education - Addison Wesley, settembre 2005, p. 152, ISBN 88-7192-269-7.
2. Silvio Ghilardi, Silvio Ranise, Il problema della soddisfacibilità booleana (PDF), su homes.dsi.unimi.it, 28 gennaio 2009, p. 6. URL consultato il 10 luglio 2017 (archiviato dall'url originale il 3 febbraio 2010).

Voci correlate

• Forma normale disgiuntiva
• Forma normale congiuntiva

Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica