L'espressione booleana in forma minimale
Un'espressione booleana in forma normale disgiuntiva può essere semplificata in forma minimale. Per farlo basta applicare le leggi dell'algebra booleana.
Ogni funzione booleana ha sempre un'espressione in forma normale disgiuntiva (DNF). Tuttavia, non esiste soltanto questa. Posso rappresentare la stessa tavola di verità anche con altre espressioni booleane. Tra queste c'è anche l'espressione in forma minimale.
Cos'è un'espressione in forma minimale?
Un'espressione in forma minimale esprime la stessa funzione booleana, ha la stessa tavola di verità, ma è composta da un minor numero di clausole e letterali.
Un esempio pratico
Queste due espressioni rappresentano la stessa funzione booleana f.
$$ xyz+xy $$
$$ xy $$
In entrambi i casi la tavola di verità della funzione è
$$ \begin{array}{cr|c} x & y & f \\ \hline 0 & 0 & 0 \\ 0 & 1 & 0 \\ 1 & 0 & 0 \\ 1 & 1 & 1 \end{array} $$
Nota. La prima espressione ha un letterale in più (z) ma è ininfluente. Se x e y sono uguali a 1, la funzione è uguale a 1 indipendentemente dal valore del letterale z.
Quindi, dovendo scegliere un'espressione booleana per rappresentare la funzione è meglio prendere la seconda.
E' più corta, ci sono meno operazioni e meno letterali da considerare.
La seconda espressione è una forma minimale della prima.
Nota. La forma minimale è molto utile per semplificare un circuito logico combinatorio perché riduce al minimo il numero delle porte ( operazioni ) e dei collegamenti ( letterali ). Nell'esempio precedente il secondo circuito è una semplice porta AND.
Come ridurre un'espressione booleana in forma minimale
Per semplificare l'espressione devo prima trasformarla in forma normale disgiuntiva (DNF).
Esempio
$$ xy(zy+v) $$
$$ xyzv+xyz $$
Nota. Un'espressione in forma normale disgiuntiva è composta da n prodotti di letterali sommati tra loro. I prodotti sono le clausole dell'espressione booleana.
Le principali regole di semplificazione sono due.
- Regola 1. Se due o più clausole contengono lo stesso prodotto al loro interno, elimino le clausole più lunghe. Ad esempio. $$ xyzv+xyz \\ xyz $$
Spiegazione. Secondo la legge di dominanza, la somma (v+1) è sempre uguale a 1. Quindi posso eliminarla. Il risultato finale è xyz. E' la clausola più corta tra quelle che contenevano il prodotto xyz.
$$ xyzv+xyz \\ xyz(v+1) \\ xyz(1) \\ xyz $$ - Regola 2. Se due prodotti diversi differiscono soltanto per un letterale, elimino il letterale differente e prendo soltanto i letterali in comune. $$ xyzv+xyz \overline{v} \\ xyz $$
Spiegazione. Secondo la legge dell'inverso qualsiasi letterale sommato con il suo complemento è uguale a 1. $$ xyzv+xyz \overline{v} \\ xyz(v+\overline{v}) \\ xyz(1) \\ xyz $$
Queste regole mi permettono di semplificare l'espressione booleana.
Ci sono comunque degli algoritmi di riduzione che standardizzano il processo di semplificazione dell'espressione booleana.
Uno dei più noti è l'algoritmo o mappe di Karnaugh.
