Forme canoniche - mintermini, maxtermini, SOP e POS

Un'espressione booleana si può scrivere in molti modi equivalenti. Le forme canoniche (o normali) sono scritture standard che si ricavano meccanicamente dalla tabella di verità: non sono le più compatte, ma sono il punto di partenza ideale per minimizzare (Mappe di Karnaugh - implicanti e copertura minimaLa mappa di Karnaugh è la tabella di verità disposta in una griglia con righe e colonne in codice Gray, così che celle adiacenti (anche tra bordi opposti) differiscano in una sola variabile. Si raggruppano gli 1 in rettangoli di $2^k$ celle: ogni gruppo elimina $k$ variabili e dà un prodotto. Implicante primo = gruppo massimo; essenziale = unico a coprire un mintermine; la copertura minima contiene tutti gli essenziali più il minimo di altri primi (può non essere unica). Efficace fino a 4 variabili.Mappe di Karnaugh - implicanti e copertura minima →).

Mintermini

Un mintermine (minterm) è un prodotto (AND) in cui compare una e una sola volta ciascuna variabile della funzione, in forma diretta o negata. Ogni mintermine corrisponde a una riga della tabella di verità: vale $1$ per la combinazione di valori di quella riga e $0$ per tutte le altre. Si costruisce prendendo ciascuna variabile diretta se il suo bit nella riga è 1, negata se è 0. Se la riga è il numero $i$ (letto in binario con la prima variabile come bit più significativo) il mintermine si chiama $m_i$.

Con tre variabili $X,Y,Z$ ($X$ bit più significativo):

Con $n$ variabili ci sono $2^n$ mintermini (tanti quante le righe), non $n$ e non $2n-1$.

Maxtermini

Il maxtermine (maxterm) è il concetto duale: una somma (OR) che contiene una e una sola volta tutte le variabili, dirette o negate. Ogni maxtermine vale $0$ su una sola riga e $1$ su tutte le altre. Si costruisce con ciascuna variabile negata se il suo bit nella riga è 1, diretta se è 0 (è l'opposto della regola dei mintermini). Anche i maxtermini sono $2^n$ e corrispondono alle righe della tabella.

Relazione. Il mintermine e il maxtermine con lo stesso indice sono uno il complemento dell'altro: $\overline{m_i}=M_i$. Per $i=3$: $\overline{\overline X YZ}=X+\overline Y+\overline Z$ ✓ (De Morgan, Algebra di Boole - assiomi, teoremi e complemento di una funzioneL'algebra di Boole opera su variabili a due valori con AND, OR, NOT. Identità fondamentali (neutro, idempotenza, complemento, commutativa, associativa, distributiva in entrambe le forme), dualità (si scambiano AND/OR e 0/1), De Morgan $\overline{X+Y}=\overline X,\overline Y$, assorbimento $X+XY=X$, $X+\overline XY=X+Y$, adiacenza $XY+X\overline Y=X$, consenso $XY+\overline XZ+YZ=XY+\overline XZ$. Si dimostrano per induzione perfetta (tabella) o algebricamente. Il complemento di una funzione si ottiene con De Morgan o con duale + negazione dei letterali. Costo: numero di letterali o di ingressi delle porte.Algebra di Boole - assiomi, teoremi e complemento di una funzione →).

Forme canoniche di una funzione

Dalla tabella di verità di $F$:

• SOP canonica (Sum Of Products): somma dei mintermini delle righe in cui $F=1$. In breve $F=\sum m(\dots)$.
• POS canonica (Product Of Sums): prodotto dei maxtermini delle righe in cui $F=0$. In breve $F=\prod M(\dots)$.

Le due descrizioni sono complementari: gli indici della POS sono quelli che mancano nella SOP, perché i maxtermini della funzione sono i mintermini della funzione complementata. Le altre righe si possono ignorare perché non cambiano il risultato: nella SOP le righe con $F=0$ contribuirebbero con $0$, elemento neutro dell'OR; nella POS le righe con $F=1$ contribuirebbero con $1$, elemento neutro dell'AND.

Esempio svolto

$F=X\overline Y+YZ$. Tabella di verità (valutando l'espressione riga per riga):

$$F=\sum m(3,4,5,7)=\overline X YZ+X\overline Y\,\overline Z+X\overline YZ+XYZ$$ $$F=\prod M(0,1,2,6)=(X+Y+Z)(X+Y+\overline Z)(X+\overline Y+Z)(\overline X+\overline Y+Z)$$

Controllo con una riga: per $X=1,Y=1,Z=0$ (riga 6) il maxtermine $M_6=\overline X+\overline Y+Z=0+0+0=0$, quindi il prodotto vale $0$ e $F=0$ ✓.

Dalla espressione alla forma canonica

L'espressione data non è canonica se i termini non contengono tutte le variabili. Per espandere un prodotto a cui manca una variabile $W$ lo si moltiplica per $(W+\overline W)=1$: $X\overline Y=X\overline Y(Z+\overline Z)=X\overline YZ+X\overline Y\,\overline Z$. Per un termine somma mancante di $W$ si aggiunge $W\overline W=0$ e si usa la seconda distributiva. Più semplice è passare dalla tabella di verità, come sopra.

Esempio. $G=XY+\overline XZ$. Tabella: $G=1$ quando $XY=1$ (righe 6 e 7) oppure $\overline XZ=1$ (righe 1 e 3). Quindi $G=\sum m(1,3,6,7)=\prod M(0,2,4,5)$.

Forme SOP e POS minime e livelli dei circuiti

Le forme canoniche sono in genere ridondanti: ogni termine contiene tutte le variabili. Una SOP (o POS) semplificata ha meno letterali: per esempio $F=X\overline Y+YZ$ è una SOP, più corta della canonica $\sum m(3,4,5,7)$.

Un'espressione in forma SOP o POS si realizza con un circuito a due livelli di porte (un livello di AND e uno di OR per la SOP; OR e AND per la POS; si suppongono disponibili le variabili dirette e negate). Se l'espressione non è né SOP né POS servono più livelli: $F=A(B+CD)$ ha tre livelli; applicando la distributiva si ottiene la SOP $AB+ACD$, a due livelli. Le SOP si realizzano bene con NAND-NAND e le POS con NOR-NOR (Progettazione di una rete combinatoria - approccio gerarchico e porte NAND-NORUna rete combinatoria ha uscite che dipendono solo dagli ingressi presenti (nessuna memoria, nessuna retroazione); una sequenziale dipende anche dalla storia (stato, memoria, feedback). Progetto: specifiche, tabella di verità, funzione a costo minimo, diagramma logico, verifica. Con molti ingressi si usa l'approccio gerarchico (blocchi e sottoblocchi riusabili; regolarità). Blocchi base: funzioni di una variabile, vettori, enabling. Mappatura tecnologica: in CMOS NAND e NOR sono più compatte, quindi SOP $\to$ NAND-NAND e POS $\to$ NOR-NOR.Progettazione di una rete combinatoria - approccio gerarchico e porte NAND-NOR →).

Con $n$ variabili esistono $2^{2^n}$ funzioni diverse (ogni riga può valere 0 o 1): $256$ con $n=3$, $65\,536$ con $n=4$.

Errori comuni

• Costruire il mintermine con la regola dei maxtermini (o viceversa): mintermine diretta se 1, maxtermine diretta se 0.
• Scrivere nella POS gli indici degli 1 invece degli 0.
• Chiamare "forma canonica" una SOP semplificata: canonica significa che ogni termine contiene tutte le variabili.
• Dire che un mintermine è una somma, o che contiene le variabili "almeno una volta": una e una sola volta.