Data una tabella di verità si dicono forme canoniche due procedimenti standard per trovare un'espressione logica (non minima) corrispondente.
Per rappresentare una generica tabella di verità mediante la prima forma canonica bisogna:
- considerare solo le righe della tabella in corrispondenza delle quali l'uscita vale 1;
- ognuna di tali righe corrisponde a un prodotto logico AND (detto mintermine) di tutte le variabili, prese negate se valgono zero e dirette se valgono uno;
- l'uscita è data dalla somma logica OR di tutti i mintermini così individuati.
Facciamo un esempio. Consideriamo la seguente tabella di verità:
| A | B | C | U |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 1 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 0 | 1 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 0 |
Consideriamo tutte le righe(tre) in corrispondenza delle quali l'uscita vale 1 e scriviamo per ognuna di esse il mintermine corrispondente:
L'espressione logica in forma canonica si ottiene facendo la somma (OR) dei mintermini trovati:
U = A.B.C + A.B.C + A.B.C
Non è difficile verificare che questa espressione logica corrisponde alla tabella data.
Per la seconda forma canonica bisogna:
- considerare solo le righe della tabella in corrispondenza delle quali l'uscita vale 0;
- ognuna di tali righe corrisponde a una somma logica OR (detto maxtermine) di tutte le variabili, prese negate se valgono uno e dirette se valgono zero;
- l'uscita è data dal prodotto logico AND di tutti i maxtermini così individuati.
Sempre con riferimento alla tabella precedente, la seconda forma canonica è la seguente:
U = (A+B+C).(A+B+C).(A+B+C).(A+B+C).(A+B+C)
Un modo forse più semplice per ricordare e scrivere la seconda forma canonica, consiste nel considerare la somma negata dei mintermini di tutte le righe in cui compare uno zero. Nel nostro esempio si avrebbe:
U = A.B.C + A.B.C + A.B.C + A.B.C + A.B.C
Non è difficile verificare (usando i teoremi di De Morgan) che le due scritture sono equivalenti.
In generale la prima forma canonica è preferibile (produce un'espressione logica più ridotta) quando, come in questo caso, il numero degli uno in uscita in tabella è inferiore al numero degli zeri; in caso contrario, se gli zeri sono più degli uno, la seconda forma canonica è preferibile.
La scrittura in una delle due forme canoniche consente di trovare abbastanza rapidamente una espressione logica corrispondente a una tabella di verità, ma non garantisce affatto che tale espressione sia anche quella minima.
Infatti in generale è spesso possibile (usando i teoremi dell'algebra booleana) procedere a ulteriori riduzioni della forma canonica. Per esempio, considerando la prima forma canonica:
U = A.B.C + A.B.C + A.B.C
raccogliendo C (inverso della proprietà distributiva) abbiamo:
U = (A.B + A.B + A.B).C
da cui procedendo ancora a raccogliere A nella parentesi tonda:
U = (A.B + A.(B + B)).C
ma essendo B + B = 1 (assioma del completamento):
U = (A.B + A.(1)).C
da cui ancora:
U = (A.B + A).C
da cui infine usando il secondo teorema dell'assorbimento abbiamo:
U = (A + B).C
Non è difficile verificare che quest'ultima espressione corrisponde ancora alla tabella di verità di partenza.
Facendo riferimento sempre alla stessa tabella, supponiamo ora di utilizzare la seconda forma canonica. Il calcolo risulta un po' più complesso in questo caso per il fatto che nella nostra tabella di verità ci sono più 0 che 1 e dunque la prima forma canonica è preferibile. Abbiamo dunque:
U = (A+B+C).(A+B+C).(A+B+C).(A+B+C).(A+B+C)
Possiamo raccogliere A+B fra i primi due termini e A+C fra gli ultimi due:
U = (A+B+C.C).(A+B+C).(A+C+B.B)
da cui possiamo eliminare i prodotti logici che contengono una variabile e la sua negazione (che dà sempre zero come risultato):
U = (A+B).(A+B+C).(A+C)
Adesso raccogliamo A fra i primi due termini:
U = (A+B.(B+C)).(A+C)
da cui, applicando la proprietà distributiva del prodotto rispetto alla somma:
U = (A+B.B+B.C)).(A+C)
Semplificando:
U = (A+B.C).(A+C)
e svolgendo i prodotti:
U = A.A+B.C.A+A.C+B.C.C = B.C.A+A.C = (B.A+A).C
Da cui infine, applicando il teorema dell'assorbimento, abbiamo:
U = (B + A).C
Come si vede abbiamo riottenuto la stessa espressione logica a cui eravamo arrivati usando la prima forma canonica, anche se in questo secondo caso la semplificazione è stata un po' più laboriosa.
Una delle maggiori difficoltà che lo studente incontra semplificando la seconda forma canonica è che le operazioni di raccoglimento della somma rispetto al prodotto non sono intuitive, in quanto non hanno nessuna corrispondenza con l'algebra ordinaria. Un metodo per aggirare il problema consiste nello scrivere la seconda forma canonica come normale somma dei prodotti e negando poi tutta l'espressione:
U = A.B.C + A.B.C + A.B.C + A.B.C + A.B.C
A questo punto è possibile procedere con la semplificazione dell'espressione sotto il segno di negazione:
U = A.B.(C
+ .C)
+ A.B.C + A.C.(B+B) =
= A.B.
+ A.B.C + A.C =
= A.(B+B.C) + AC =
= A.(B+C) + AC =
= A.B+A.C + AC =
= A.B+C
(A+A) =
= A.B+C
A questo punto possiamo infine applicare il teorema di De Morgan e ottenere di nuovo la nostra espressione minima:
U = A.B+C = (A + B).C
Un metodo standard per la ricerca automatica dell'espressione AND-OR
minima di una tabella di verità è quello delle
mappe di Karnaugh.
Online Karnaugh Map: un sito per la sintesi automatica delle tabelle di verità col metodo delle mappe di K.
Sito realizzato in base al template offerto da
http://www.graphixmania.it
