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 clausole, dove le clausole sono una congiunzione di letterali. Una formula in DNF ha quindi la seguente struttura:

$\bigvee_{i=1}^n \left( \bigwedge_{k=1}^{m(i)} L_{i,k} \right)$

$n$ : Numero di clausole.

$m(i)$ : Numero di letterali della clausola i-esima.

$L_{i,k}$ : È il k-esimo letterale della i-esima clausola. Un letterale può essere una variabile o la negazione di una variabile.

Esempi

Le seguenti formule sono in DNF:

$(\neg A \wedge B) \vee (B \wedge C)$

$(A \wedge B) \vee (\neg B \wedge C \wedge \neg D) \vee (D \wedge \neg E)$

$(\neg B \wedge C)$

$(\neg B \wedge C) \vee A$

$A \vee B$

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

Voci correlate

• Forma normale congiuntiva
• Forma canonica (algebra di Boole)

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