Forma normale negativa

termine

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 () è applicato solo agli atomi. Inoltre, gli unici operatori consentiti sono congiunzione () e disgiunzione ().

La forma normale negativa non è una forma canonica: ad esempio, e 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:

Nelle formule di cui sopra, il simbolo indica l'implicazione logica nella formula da riscrivere, mentre è 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 e .

EsempiModifica

Le seguenti formule sono tutte in forma normale negativa:

 
 
 
 

Le seguenti formule non sono in forma normale negativa:

 
 
 
 

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

 
 
 
 

NoteModifica

  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.

Voci correlateModifica

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