Forma normale disgiuntiva

Template:U Template:F Template:S 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:

$\underset{i=1}{\overset{n}{\bigvee }}\left(\underset{k=1}{\overset{m_i}{\bigwedge }}{L}_{i,k}\right),$

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:

$(\mathrm{\neg }A\wedge B)\vee (B\wedge C);$

$(A\wedge B)\vee (\mathrm{\neg }B\wedge C\wedge \mathrm{\neg }D)\vee (D\wedge \mathrm{\neg }E);$

$(\mathrm{\neg }B\wedge C);$

$(\mathrm{\neg }B\wedge C)\vee A;$

$A\vee B.$

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

Da notare che formule come l'ultima, ossia del tipo $A_1\vee A_2\vee \dots \vee A_n$ (o similmente $A_1\wedge A_2\wedge \dots \wedge A_n$) dove $A_i$ sono letterali, sono da considerarsi simultaneamente DNF e CNF.

Voci correlate

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

Collegamenti esterni

• Template:Collegamenti esterni