Forma normale disgiuntiva (DNF)
La forma normale disgiuntiva o DNF (Disjunctive Normal Form) rappresenta una funzione booleana tramite una somma logica (OR) di più congiunzioni logiche (AND) di variabili, che possono apparire in forma diretta $ x_i $ o negata $ \overline{x_i} $. Ogni congiunzione logica rende vera (1) la funzione booleana.
Questa struttura rende la DNF particolarmente adatta a descrivere relazioni complesse in modo conciso.
Esempio
Consideriamo una funzione booleana $ f(x_1,x_2,x_3) $ definita da tre variabili: $ x_1 $, $ x_2 $, e $ x_3 $.
Una possibile DNF per una funzione che diviene vera in specifiche condizioni potrebbe essere:
$$ f(x_1,x_2,x_3) = ( x_1 ∧ x_2 ∧ \overline{x_3})∨( \overline{x_1}∧x_2∧ x_3) $$
La funzione è la somma (OR) di tutti questi termini. Ogni termine è un prodotto (AND) di variabili o delle loro negazioni.
In questo caso la DNF è composta due termini che rendono vera la funzione booleana $ f(x_1,x_2, x_3) $ detti mintermini.
- $ ( x_1 ∧ x_2 ∧ \overline{x_3}) $
- $ ( \overline{x_1}∧x_2∧ x_3) $
La funzione risulta vera in due casi specifici: quando $ x_1 $ è vera, $ x_2 $ è vera e $ x_3 $ è falsa, oppure quando $ x_1 $ è falsa, $ x_2 $ è vera e $ x_3 $ è vera.
Dove in algebra booleana una variabile è vera se è 1, mentre è falsa se è 0.
Pertanto, se almeno uno dei termini $ ( x_1 ∧ x_2 ∧ \overline{x_3}) $ oppure $ ( \overline{x_1}∧x_2∧ x_3) $ risulta vero, allora l'intera funzione \( f \) sarà vera.
Come si costruisce una DNF?
La costruzione di una DNF può essere derivata direttamente dalla tabella di verità della funzione booleana.
- Seleziona le righe vere. Identifica tutte le righe nella tabella di verità dove l'output della funzione è vero (y=1).
- Formula i termini. Per ogni riga selezionata, crea un termine di congiunzione (AND) che corrisponda a quella combinazione specifica di valori. Usa le variabili in modo diretto $ x_i $ se il loro valore è vero (1) nella combinazione, o la loro negazione $ \overline{x_i} $ se il loro valore è falso (0).
- Unisci i termini con OR. Combina tutti i termini di congiunzione usando l'operatore OR. Questo unisce tutte le condizioni sotto cui la funzione è vera.
Ad esempio, supponiamo di avere una funzione booleana $ f(x_1, x_2, x_3) $ e la seguente tabella di verità:
\begin{array}{|c|c|c|c|}
\hline
x_1 & x_2 & x_3 & f(x_1, x_2, x_3) \\
\hline
0 & 0 & 0 & 0 \\
0 & 0 & 1 & 1 \\
0 & 1 & 0 & 0 \\
0 & 1 & 1 & 1 \\
1 & 0 & 0 & 0 \\
1 & 0 & 1 & 1 \\
1 & 1 & 0 & 0 \\
1 & 1 & 1 & 0 \\
\hline
\end{array}
Per costruire la DNF, si considerano solo le righe dove \( f \) è 1:
- Per la riga 2: \( \overline{x_1} \land \overline{x_2} \land x_3 \)
- Per la riga 4: \( \overline{x_1} \land x_2 \land x_3 \)
- Per la riga 6: \( x_1 \land \overline{x_2} \land x_3 \)
La DNF sarà quindi:
$$ f(x_1, x_2, x_3) = ( \overline{x_1} \land \overline{x_2} \land x_3 ) \lor ( \overline{x_1} \land x_2 \land x_3 \ ) \lor ( x_1 \land \overline{x_2} \land x_3 ) $$
Questo processo dimostra come la DNF si concentri esclusivamente sulle condizioni che rendono la funzione booleana vera.
Non si considerano le configurazioni che producono un output falso, poiché la DNF mira a esprimere esplicitamente quando la funzione è vera, fornendo una rappresentazione chiara e diretta delle condizioni di verità.
Questi termini sono poi uniti insieme tramite l'operatore OR.
La forma DNF è utilizzata nella progettazione dei circuiti logici, perché permette una rappresentazione chiara e diretta delle condizioni che rendono vera una funzione booleana. E' utilizzata anche in informatica per ottimizzare le condizioni logiche che attivano o meno l'esecuzione di un algoritmo.
