Apri il menu principale

Nella logica booleana, una formula è in forma normale disgiuntiva o disgiunta (FND), indicata anche come DNF (acronimo di Disjunctive Normal Form) se è una disgiunzione di clausole, dove le clausole sono una congiunzione di letterali. Una formula in DNF ha quindi la seguente struttura:

 : Numero di clausole.

 : Numero di letterali della clausola i-esima.

 : È il k-esimo letterale della i-esima clausola. Un letterale può essere una variabile booleana (cioè che può valere solo 0 o 1, vero o falso) o la negazione di una variabile.

EsempiModifica

Le seguenti formule sono in DNF:

 
 
 
 
 

L'ultima formula ha due clausole, entrambe con un solo letterale.

Da notare che formule come l'ultima, ossia del tipo   (o similmente  ) dove   sono letterali, sono da considerarsi simultaneamente DNF e CNF.

Voci correlateModifica