Forma normale disgiuntiva

Da Wikipedia, l'enciclopedia libera.
Vai alla navigazione Vai alla ricerca

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 congiunzioni di letterali. Una formula in DNF ha quindi la seguente struttura:

dove:

  • è il numero di congiunzioni;
  • è il numero di letterali della congiunzione -esima;
  • è il -esimo letterale della -esima congiunzione. Un letterale può essere una variabile booleana (cioè che può valere solo 0 o 1, vero o falso) o la negazione di una variabile.

Esempi[modifica | modifica wikitesto]

Le seguenti formule sono in DNF:

L'ultima formula ha due congiunzioni, 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 correlate[modifica | modifica wikitesto]

Collegamenti esterni[modifica | modifica wikitesto]

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