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:

${\displaystyle \bigvee _{i=1}^{n}\left(\bigwedge _{k=1}^{m_{i}}L_{i,k}\right),}$

dove:

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

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

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

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

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

${\displaystyle A\vee B.}$

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

Da notare che formule come l'ultima, ossia del tipo ${\displaystyle A_{1}\vee A_{2}\vee \ldots \vee A_{n}}$ (o similmente ${\displaystyle A_{1}\wedge A_{2}\wedge \ldots \wedge A_{n}}$) dove ${\displaystyle 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

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

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