Forma normale disgiuntiva

Da Wikipedia, l'enciclopedia libera.

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[modifica | modifica sorgente]

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.

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

Voci correlate[modifica | modifica sorgente]

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