Forma normale disgiuntiva

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 FND ha quindi la seguente struttura:

⋁_{i = 1}^{n} (⋀_{k = 1}^{m_{i}} L_{i, k}),

dove:

$n$ è il numero di congiunzioni;
$m_{i}$ è il numero di letterali della congiunzione $i$ -esima;
$L_{i, k}$ è il $k$ -esimo letterale della $i$ -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

Le seguenti formule sono in FND:

(\neg A \land B) \lor (B \land C);

(A \land B) \lor (\neg B \land C \land \neg D) \lor (D \land \neg E);

(\neg B \land C);

(\neg B \land C) \lor A;

A \lor B .

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

Da notare che formule come l'ultima, ossia del tipo $A_{1} \lor A_{2} \lor \dots \lor A_{n}$ (o similmente $A_{1} \land A_{2} \land \dots \land A_{n}$ ) dove $A_{i}$ sono letterali, sono da considerarsi simultaneamente DNF e CNF.

Voci correlate

Collegamenti esterni

forma normale disgiuntiva, in Enciclopedia della Matematica, Istituto dell'Enciclopedia Italiana, 2013.

(EN) Eric W. Weisstein, Forma normale disgiuntiva, su MathWorld, Wolfram Research.

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