Esercizio 16minimizzazione di una funzione data per mintermini (tema d'esame giugno 2026)

---

Teoria usata: 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 →, Mappe di Karnaugh - POS, condizioni di don't care e paritàPer la POS minima si raggruppano gli 0 della mappa, si ottiene la SOP minima di $\overline F$ e si scrive $F$ come prodotto di somme (variabile diretta se vale 0 nel gruppo, negata se vale 1). Le condizioni di don't care (X) sono combinazioni di ingresso che non si presentano o la cui uscita è indifferente: si usano come 1 o come 0 a seconda di quel che allarga i gruppi (mai raggruppamenti fatti solo di X). Le funzioni XOR a più variabili (disparità) e XNOR (parità) hanno mappa a scacchiera: non si semplificano con i gruppi.Mappe di Karnaugh - POS, condizioni di don't care e parità →, Forme canoniche - mintermini, maxtermini, SOP e POSUn mintermine è un prodotto che contiene una e una sola volta tutte le variabili (dirette o negate) e vale 1 su una sola riga della tabella di verità; un maxtermine è la somma duale e vale 0 su una sola riga; con $n$ variabili ci sono $2^n$ mintermini e $2^n$ maxtermini, e $\overline{m_i}=M_i$. Forma canonica SOP = somma dei mintermini delle righe con $F=1$; POS = prodotto dei maxtermini delle righe con $F=0$. Le forme canoniche si ricavano sempre dalla tabella ma sono ridondanti: servono come punto di partenza per la minimizzazione. SOP e POS si realizzano con circuiti a due livelli.Forme canoniche - mintermini, maxtermini, SOP e POS →.

Passo 1: mappa di Karnaugh

Funzione completamente specificata (nessun don't care): $y=1$ nelle celle $0,1,2,3,4,5,7,14,15$ e $0$ nelle altre $7$ ($6,8,9,10,11,12,13$). Righe $dc$, colonne $ba$ (codice Gray):

Passo 2: implicanti primi

• $\overline d\,\overline c$: la riga $dc=00$ (celle $0,1,3,2$);
• $\overline d\,\overline b$: le celle $0,1,4,5$ (righe $dc=00$ e $01$, colonne $ba=00$ e $01$);
• $\overline d\,a$: le celle $1,3,5,7$ (righe $00$ e $01$, colonne $01$ e $11$);
• $c\,b\,a$: le celle $7,15$ (colonna $ba=11$, righe $01$ e $11$);
• $d\,c\,b$: le celle $14,15$ (riga $dc=11$, colonne $11$ e $10$).

Passo 3: essenziali e copertura minima

• $\overline d\,\overline c$ è essenziale: la cella $2$ è coperta solo da lui;
• $\overline d\,\overline b$ è essenziale: la cella $4$ è coperta solo da lui;
• $d\,c\,b$ è essenziale: la cella $14$ è coperta solo da lui.

Questi tre coprono le celle $0,1,2,3,4,5,14,15$. Resta scoperta la cella $7$, che si copre con $\overline d\,a$ (2 letterali) oppure con $c\,b\,a$ (3 letterali): si sceglie $\overline d\,a$. Le tre scelte forzate più questa danno la copertura minima, unica: $$y=\overline d\,\overline c+\overline d\,\overline b+\overline d\,a+d\,c\,b$$ (4 prodotti, 9 letterali). Raccogliendo $\overline d$: $y=\overline d\,(\overline c+\overline b+a)+d\,c\,b$: con $d=0$ la funzione vale $\overline c+\overline b+a$ (è $0$ solo per $c=b=1,a=0$, cioè la cella $6$), con $d=1$ vale $c\,b$.

Passo 4: forma POS e verifica

Gli $0$ sono nelle celle $6,8,9,10,11,12,13$. I gruppi di zeri: $\{8,9,10,11\}$ ($d\,\overline c$), $\{8,9,12,13\}$ ($d\,\overline b$), e la cella $6$ isolata ($\overline d\,c\,b\,\overline a$). Per De Morgan (si negano i letterali e si scambiano prodotti e somme): $$y=(\overline d+c)(\overline d+b)(d+\overline c+\overline b+a).$$ Costo in ingressi (inverter compresi): SOP $3\cdot2+3+4+3=16$; POS $2+2+4+3+3=14$: qui la POS costa un po' meno.

Verifica: si controlla la tabella completa con un programma ($16$ righe). Esempi: cella $7$ ($0111$): $\overline d\,a=1$ $\Rightarrow$ $y=1$ ✓; cella $6$ ($0110$): $\overline d\,\overline c=0$, $\overline d\,\overline b=0$, $\overline d\,a=0$, $d\,c\,b=0$ $\Rightarrow$ $y=0$ ✓; cella $15$: $d\,c\,b=1$ ✓.

Errori comuni

• Coprire la cella $7$ con $c\,b\,a$ (più letterali) o scegliere due implicanti per la stessa cella.
• Non vedere che $\overline d\,\overline c$ comprende la cella $2$ (adiacente alla $0$ attraverso il bordo delle colonne).
• Includere la cella $6$ per errore ($\overline d\,\overline c$ non la copre perché $c=1$).