Le Mappe di Karnaugh

Concetti Chiave

Il metodo delle mappe di Karnaugh fornisce una rappresentazione visiva delle funzioni booleane, facilitando la loro minimizzazione.
Le mappe di Karnaugh sono particolarmente utili per funzioni con un numero ridotto di variabili (fino a 4 o 5).
La minimizzazione tramite K-map si basa sull'identificazione di gruppi di 1 adiacenti, che possono essere combinati per formare termini più semplici.
I termini più semplici prendono il nome di sotto-cubi e possono essere composti in modo da coprire più mintermini ma sempre in numero pari ad una potenza di due: 1, 2, 4, 8.

Il Metodo delle Mappe di Karnaugh

La complessità delle porte logiche digitali che implementano una funzione booleana è direttamente correlata alla complessità dell'espressione algebrica che descrive la funzione. Sebbene la rappresentazione della tabella di verità di una funzione sia unica, quando è espressa algebricamente può apparire in molte forme diverse, ma equivalenti. Le espressioni booleane possono essere semplificate con mezzi algebrici come visto nella lezione sui teoremi dell'algebra booleana.

Tuttavia, questa procedura di minimizzazione è scomoda, perché manca di regole specifiche per predire ogni passo successivo nel processo manipolativo. Il metodo delle mappe presentato in questa lezione fornisce una procedura semplice e diretta per minimizzare le funzioni booleane. Questo metodo può essere considerato come una forma pittorica di una tabella di verità. Il metodo delle mappe è anche conosciuto come il metodo della mappa di Karnaugh o K-map.

Una K-map è un diagramma composto da quadrati, con ogni quadrato che rappresenta un mintermine della funzione che deve essere minimizzata. Poiché qualsiasi funzione booleana può essere espressa come somma di mintermini, ne consegue che una funzione booleana è riconosciuta graficamente nella mappa dall'area racchiusa da quei quadrati i cui mintermini sono inclusi nella funzione. Infatti, la mappa presenta un diagramma visivo di tutti i modi possibili in cui una funzione può essere espressa in forma standard. Riconoscendo vari modelli, l'utente può derivare espressioni algebriche alternative per la stessa funzione, da cui può essere selezionata la più semplice.

Le espressioni semplificate prodotte dalla mappa sono sempre in una delle due forme standard: somma di prodotti o prodotto di somme. Si assumerà che l'espressione algebrica più semplice sia quella che ha un numero minimo di termini con il minor numero possibile di letterali in ogni termine. Questa espressione produce un diagramma circuitale con un numero minimo di porte e il numero minimo di input a ogni porta. Vedremo successivamente che l'espressione più semplice non è unica: è talvolta possibile trovare due o più espressioni che soddisfano i criteri di minimizzazione. In tal caso, qualsiasi soluzione è soddisfacente.

Mappe di Karnaugh a due Variabili

Una mappa di Karnaugh a due variabili è mostrata nella figura che segue:

Ci sono quattro mintermini per due variabili; quindi, la mappa consiste di quattro quadrati, uno per ogni mintermine. La mappa è ridisegnata di seguito per mostrare la relazione tra i quadrati e le due variabili $x$ e $y$ :

**Figura 2:** Mappa di Karnaugh a due variabili ridisegnata per mostrare la relazione tra le variabili e i mintermini delle singole celle

Lo 0 e l'1 marcati in ogni riga e colonna designano i valori delle variabili. La variabile $x$ appare complementata nella riga 0 e non complementata nella riga 1. Similmente, $y$ appare complementata nella colonna 0 e non complementata nella colonna 1.

Se marchiamo i quadrati i cui mintermini appartengono a una data funzione, la mappa a due variabili diventa un altro modo utile per rappresentare qualsiasi delle 16 funzioni booleane di due variabili.

Come esempio, la funzione AND, $f(x,y) = xy$ , è mostrata nella figura seguente:

**Figura 3:** Mappa di Karnaugh della funzione AND a due variabili

Poiché $xy$ è uguale al mintermine $m_3$ , un 1 è posto all'interno del quadrato che appartiene a $m_3$ .

Analogamente, la funzione OR, $f(x, y) = x + y$ è rappresentata nella mappa della figura che segue da tre quadrati marcati con 1:

**Figura 4:** Mappa di Karnaugh della funzione OR a due variabili

Questi quadrati corrispondono ai singoli mintermini della seguente espressione algebrica:

m_1 + m_2 + m_3 = x'y + xy' + xy = x + y

I tre quadrati avrebbero potuto essere determinati anche dall'unione dei quadrati della variabile $x$ nella seconda riga e quelli della variabile $y$ nella seconda colonna, che racchiude l'area appartenente a $x$ o $y$ :

**Figura 5:** Mappa di Karnaugh della funzione OR a due variabili: Sottocubi evidenziati rispettivi a x e y

In ogni esempio, i mintermini per cui la funzione è vera sono marcati con un 1.

Mappe di Karnaugh a Tre Variabili

Una mappa di Karnaugh a tre variabili è mostrata nella figura che segue:

Ci sono otto mintermini per tre variabili binarie; quindi, la mappa consiste di otto quadrati. Si noti che i mintermini sono disposti, non in una sequenza binaria, ma in una sequenza simile al codice di Gray.

La caratteristica di questa sequenza è che solo un bit cambia valore da una colonna adiacente alla successiva.

Per evidenziare questa caratteristica, ridisegniamo la mappa nella figura che segue:

**Figura 7:** Mappa di Karnaugh a Tre Variabili: Evidenziazione dei mintermini

In figura, la mappa è marcata con mintermini numerati in ogni riga e ogni colonna per mostrare la relazione tra i quadrati e le tre variabili. Per esempio, il quadrato assegnato a $m_5$ corrisponde alla riga 1 e alla colonna 01. Quando questi due numeri sono concatenati, danno il numero binario 101, il cui equivalente decimale è 5. Ogni cella della mappa corrisponde a un mintermine unico, quindi un altro modo di guardare al quadrato $m_5 = xy'z$ è considerarlo nella riga marcata $x$ e nella colonna appartenente a $y'z$ (colonna 01). Si noti che ci sono quattro quadrati in cui ogni variabile è uguale a 1 e quattro in cui ognuna è uguale a 0. La variabile appare non complementata nei primi quattro quadrati e complementata negli ultimi.

Per comprendere l'utilità della mappa nel semplificare le funzioni booleane, dobbiamo riconoscere la proprietà di base posseduta dai quadrati adiacenti: Qualsiasi due quadrati adiacenti nella mappa differiscono per una sola variabile, che è complementata in un quadrato e non complementata nell'altro (I quadrati che sono vicini su una diagonale non sono considerati adiacenti).

Per esempio, $m_5$ e $m_7$ giacciono in due quadrati adiacenti. La variabile $y$ è complementata in $m_5$ e non complementata in $m_7$ , mentre le altre due variabili sono le stesse in entrambi i quadrati. Dai postulati dell'algebra booleana, ne consegue che la somma di due mintermini in quadrati adiacenti può essere semplificata a un singolo termine prodotto consistente di solo due letterali. Per chiarire questo concetto, consideriamo la somma di due quadrati adiacenti come $m_5$ e $m_7$ :

m_5 + m_7 = xy'z + xyz = xz(y' + y) = xz

Qui, i due quadrati differiscono per la variabile $y$ , che può essere rimossa quando viene formata la somma dei due mintermini. Quindi, qualsiasi due mintermini in quadrati adiacenti (verticalmente o orizzontalmente, ma non diagonalmente, adiacenti) che sono messi in OR insieme causeranno una rimozione della variabile dissimile.

I prossimi quattro esempi spiegano la procedura per minimizzare una funzione booleana con una mappa di Karnaugh.

Esempio 1

Semplificare la funzione booleana che segue:

F(x, y, z) = \Sigma(2, 3, 4, 5)

Per prima cosa costruiamo la mappa di Karnaugh inserendo un 1 in ogni quadrato del mintermine corrispondente. Questo è mostrato nella figura che segue, in cui i quadrati per i mintermini 010, 011, 100, e 101 sono marcati con 1:

**Figura 8:** Esempio 1: Mappa di Karnaugh

Il passo successivo è trovare possibili quadrati adiacenti. Questi sono indicati nella mappa da due rettangoli colorati, ognuno che racchiude due 1:

Il rettangolo in alto a destra rappresenta l'area racchiusa da $x'y$ . Quest'area è determinata osservando che l'area di due quadrati è nella riga 0, corrispondente a $x'$ , e nelle ultime due colonne, corrispondenti a $y$ . Similmente, il rettangolo in basso a sinistra rappresenta il termine prodotto $xy'$ . (La seconda riga rappresenta $x$ e le due colonne di sinistra rappresentano $y'$ ).

La somma di quattro mintermini nei quadrati ombreggiati può essere sostituita da una somma di solo due termini prodotto. La somma logica di questi due termini prodotto dà l'espressione semplificata

F = x'y + xy'

Sotto-cubi Adiacenti

In certi casi, due quadrati nella mappa sono considerati adiacenti anche se non si toccano. Nella figura che segue, $m_0$ è adiacente a $m_2$ e $m_4$ è adiacente a $m_6$ perché i loro mintermini differiscono per una variabile:

Questa differenza può essere prontamente verificata algebricamente:

m_0 + m_2 = x'y'z' + x'yz' = x'z'(y' + y) = x'z'

m_4 + m_6 = xy'z' + xyz' = xz'(y' + y) = xz'

Di conseguenza, dobbiamo modificare la definizione di quadrati adiacenti per includere questo e altri casi simili. Lo facciamo considerando la mappa come disegnata su una superficie in cui i bordi destro e sinistro si toccano per formare quadrati adiacenti.

Esempio 2

Semplifichiamo la funzione booleana

F(x, y, z) = \Sigma(3, 4, 6, 7)

La mappa per questa funzione è mostrata nella figura seguente:

**Figura 11:** Esempio 2: Mappa di Karnaugh

Ci sono quattro quadrati marcati con 1, uno per ogni mintermine della funzione.

Adesso segniamo i quadrati adiacenti come in figura:

Due quadrati adiacenti ombreggiati nella terza colonna sono combinati per dare un termine a due letterali $yz$ . I restanti due quadrati con 1 sono anche adiacenti per la nuova definizione. Questi due quadrati ombreggiati, quando combinati, danno il termine a due letterali $xz'$ . La funzione semplificata diventa quindi:

F(x, y, z) = yz + xz'

Combinazioni di quattro mintermini

Consideriamo ora qualsiasi combinazione di quattro quadrati adiacenti nella mappa a tre variabili. Qualsiasi tale combinazione rappresenta la somma logica di quattro mintermini e risulta in un'espressione con solo un letterale. Come esempio, la somma logica dei quattro mintermini adiacenti 0, 2, 4, e 6 si riduce al singolo termine letterale $z'$ :

**Figura 13:** Combinazione di quattro mintermini

m_0 + m_2 + m_4 + m_6 = x'y'z' + x'yz' + xy'z' + xyz'

= x'z'(y' + y) + xz'(y' + y)

= x'z' + xz' = (x' + x)z' = z'

Il numero di quadrati adiacenti che possono essere combinati deve sempre rappresentare un numero che è una potenza di due, come 1, 2, 4, e 8.

Man mano che più quadrati adiacenti sono combinati, otteniamo un termine prodotto con meno letterali.

Un quadrato rappresenta un mintermine, dando un termine con tre letterali.

Due quadrati adiacenti rappresentano un termine con due letterali.

Quattro quadrati adiacenti rappresentano un termine con un letterale.

Otto quadrati adiacenti racchiudono l'intera mappa a tre variabili e producono una funzione che è sempre uguale a 1.

Esempio 3

Semplifichiamo la funzione booleana:

F(x, y, z) = \Sigma(0, 2, 4, 5, 6)

La mappa per $F$ è mostrata nella figura:

**Figura 14:** Esempio 3: Mappa di Karnaugh

Troviamo i quadrati adiacenti come mostrato nella figura che segue:

Prima, combiniamo i quattro quadrati adiacenti nella prima e ultima colonna per dare il singolo termine letterale $z'$ . Il restante quadrato singolo, che rappresenta il mintermine 5, è combinato con un quadrato adiacente che è già stato usato una volta. Questo non è solo permissibile ma anche piuttosto desiderabile, perché i due quadrati adiacenti danno il termine a due letterali $xy'$ e il quadrato singolo rappresenta il mintermine a tre letterali $xy'z$ .

La funzione semplificata è quindi:

F(x, y, z) = z' + xy'

Esempio 4

Se una funzione non è espressa in forma somma-di-mintermini, è possibile usare la mappa per ottenere i mintermini della funzione e poi semplificare la funzione a un'espressione con un numero minimo di termini. È necessario, tuttavia, assicurarsi che l'espressione algebrica sia in forma somma-di-prodotti. Ogni termine prodotto può essere tracciato nella mappa in uno, due, o più quadrati. I mintermini della funzione sono poi letti direttamente dalla mappa.

Chiariamo meglio con il prossimo esempio.

Per la funzione booleana

F = A'C + A'B + AB'C + BC

(a) Si esprima questa funzione come somma di mintermini.
(b) Si trovi l'espressione somma-di-prodotti minimale.

Si noti che $F$ è una somma di prodotti, ma non una somma di mintermini. Tre termini prodotto nell'espressione hanno due letterali e sono rappresentati in una mappa a tre variabili da due quadrati ciascuno.

La funzione può essere rappresentata su di una mappa di karnaugh in questo modo:

**Figura 16:** Esempio 4: Mappa di Karnaugh

I due quadrati corrispondenti al primo termine, $A'C$ , sono situati nella figura di sopra nella coincidenza di $A'$ (prima riga) e $C$ (due colonne centrali) per dare i quadrati 001 e 011. Si noti che, nel marcare 1 nei quadrati, è possibile trovare un 1 già posto lì da un termine precedente. Questo accade con il secondo termine, $A'B$ , che ha 1 nei quadrati 011 e 010. Il quadrato 011 è comune con il primo termine, $A'C$ , però, quindi solo un 1 è marcato in esso. Continuando in questo modo, determiniamo che il termine $AB'C$ appartiene al quadrato 101, corrispondente al mintermine 5, e il termine $BC$ ha due 1 nei quadrati 011 e 111. La funzione ha un totale di cinque mintermini, come indicato dai cinque 1 nella mappa della figura di sopra.

I mintermini sono letti direttamente dalla mappa come 1, 2, 3, 5, e 7. La funzione può essere riespressa in forma somma-di-mintermini come

F(A, B, C) = \Sigma(1, 2, 3, 5, 7)

L'espressione somma-di-prodotti, come originariamente data, ha troppi termini. Può essere semplificata, come indicato dai quadrati ombreggiati nella mappa che segue:

L'espressione risultante sarà:

F = C + A'B

Esempio 5

Semplifichiamo la funzione booleana:

F(x, y, z) = \Sigma(0, 1, 6, 7)

Disegniamo la mappa di Karnaugh relativa:

**Figura 18:** Esempio 5: Mappa di Karnaugh

Troviamo la copertura con i sotto-cubi più grandi:

In tal caso, il sotto-cubo rosso corrisponde al termine $x'y'$ mentre quello verde al termine $xy$ . Per cui la forma minimizzata della funzione risulta:

F(x, y, z) = x'y' + xy

Esempio 6

Semplifichiamo la funzione booleana:

F(x, y, z) = \Sigma(0, 1, 2, 5)

Disegniamo la mappa di Karnaugh relativa:

**Figura 20:** Esempio 6: Mappa di Karnaugh

Troviamo la copertura con i sotto-cubi più grandi:

Qui, il sotto-cubo rosso corrisponde al termine $x'z'$ mentre quello verde al termine $y'z$ . L'espressione minimizzata della funzione risulta:

F(x, y, z) = x'z' + y'z

Esempio 7

Semplifichiamo la funzione booleana:

F(x,y,z) = \Sigma(0, 2, 3, 4, 6)

Disegniamo la mappa di Karnaugh relativa:

**Figura 22:** Esempio 7: Mappa di Karnaugh

Troviamo la copertura con i sotto-cubi più grandi:

In tal caso, il sotto-cubo rosso corrisponde alla singola variabile complementata $z'$ . Il sotto-cubo verde, invece, rappresenta il termine $x'y$ .

La funzione minimizzata risulta quindi:

F(x,y,z) = z' + x'y

Mappe di Karnaugh a Quattro Variabili

La mappa per le funzioni booleane di quattro variabili binarie ( $w$ , $x$ , $y$ , $y$ ) è mostrata nella figura seguente, che elenca i 16 mintermini e i quadrati assegnati a ciascuno:

**Figura 24:** Mappa di Karnaugh a Quattro Variabili

Nella figura la mappa è disegnata per mostrare la relazione tra i quadrati e le quattro variabili.

Le righe e le colonne sono numerate in una sequenza di codice di Gray, con solo una cifra che cambia valore tra due righe o colonne adiacenti. Il mintermine corrispondente a ogni quadrato può essere ottenuto dalla concatenazione del numero di riga con il numero di colonna. Per esempio, i numeri della terza riga (11) e della seconda colonna (01), quando concatenati, danno il numero binario 1101, l'equivalente binario del decimale 13. Quindi, il quadrato nella terza riga e seconda colonna rappresenta il mintermine $m_{13}$ .

La minimizzazione della mappa di funzioni booleane a quattro variabili è simile al metodo usato per minimizzare le funzioni a tre variabili. I quadrati adiacenti sono definiti come quadrati uno accanto all'altro (verticalmente o orizzontalmente, ma non diagonalmente). Inoltre, la mappa è considerata come giacente su una superficie con i bordi superiore e inferiore, così come i bordi destro e sinistro, che si toccano per formare quadrati adiacenti. Per esempio, $m_0$ e $m_2$ formano quadrati adiacenti, così come $m_3$ e $m_{11}$ . La combinazione di quadrati adiacenti che è utile durante il processo di semplificazione è facilmente determinata dall'ispezione della mappa a quattro variabili:

Un quadrato rappresenta un mintermine, dando un termine con quattro letterali.
Due quadrati adiacenti rappresentano un termine con tre letterali.
Quattro quadrati adiacenti rappresentano un termine con due letterali.
Otto quadrati adiacenti rappresentano un termine con un letterale.
Sedici quadrati adiacenti producono una funzione che è sempre uguale a 1.

Nessun'altra combinazione di quadrati può semplificare la funzione. I prossimi due esempi mostrano la procedura usata per semplificare le funzioni booleane a quattro variabili.

Esempio 8

Proviamo a semplificare la funzione booleana a quattro variabili che segue:

F(w, x, y, z) = \Sigma(0, 1, 2, 4, 5, 6, 8, 9, 12, 13, 14)

Poiché la funzione ha quattro variabili, deve essere usata una mappa a quattro variabili. I mintermini elencati nella somma sono marcati con 1 nella mappa della figura che segue:

**Figura 25:** Esempio 8: Mappa di Karnaugh

Otto quadrati adiacenti ombreggiati marcati con 1 possono essere combinati per formare il termine a un letterale $y'$ (Il sotto-cubo rosso nella figura di sotto). I restanti tre 1 sulla destra non possono essere combinati per dare un termine semplificato; devono essere combinati come due o quattro quadrati adiacenti. Maggiore è il numero di quadrati combinati, minore sarà il numero di letterali nel termine. In questo esempio, i due 1 superiori sulla destra sono combinati con i due 1 superiori sulla sinistra per dare il termine $w'z'$ (Il sotto-cubo verde). Si noti che è permesso usare lo stesso quadrato più di una volta. Ora rimaniamo con un quadrato marcato con 1 nella terza riga e quarta colonna (quadrato 1110). Invece di prendere questo quadrato da solo (che darà un termine con quattro letterali), lo combiniamo con quadrati già usati per formare un'area di quattro quadrati adiacenti. Questi quadrati compongono le due righe centrali e le due colonne terminali, dando il termine $xz'$ (Il sotto-cubo giallo). La funzione semplificata risulta essere quindi:

F = y' + w'z' + xz'

Il numero di termini e il numero di letterali è stato ridotto.

Esempio 9

Si semplifichi la funzione booleana:

F = A'B'C' + B'CD' + A'BCD' + AB'C'

L'area nella mappa coperta da questa funzione consiste dei quadrati marcati con 1 nella figura che segue:

**Figura 27:** Esempio 9: Mappa di Karnaugh

La funzione ha quattro variabili e, come espressa, consiste di tre termini con tre letterali ciascuno e un termine con quattro letterali. Ogni termine con tre letterali è rappresentato nella mappa da due quadrati. Per esempio, $A'B'C'$ è rappresentato nei quadrati 0000 e 0001:

**Figura 28:** Esempio 9: Termine A'B'C'

La funzione può essere semplificata nella mappa prendendo gli 1 nei quattro angoli per dare il termine $B'D'$ :

**Figura 29:** Esempio 9: Implicante agli Angoli B'D'

Questo è possibile perché questi quattro quadrati sono adiacenti quando la mappa è disegnata su una superficie con i bordi superiore e inferiore, così come i bordi sinistro e destro, che si toccano. I due 1 di sinistra nella riga superiore sono combinati con i due 1 nella riga inferiore per dare il termine $B'C'$ :

**Figura 30:** Esempio 9: Secondo implicante B'C'

L'1 rimanente può essere combinato in un'area di due quadrati per dare il termine $A'CD'$ :

**Figura 31:** Esempio 9: Ultimo Implicante A'CD'

La copertura completa della funzione è mostrata nella figura che segue:

**Figura 32:** Esempio 9: Copertura completa

La funzione semplificata ha meno termini, con meno letterali:

F = B'D' + B'C' + A'CD'

Esempio 10

Semplifichiamo la funzione booleana:

F(w, x, y, z) = \Sigma(0, 1, 3, 8, 9, 10, 11, 12, 13, 14, 15)

Per prima cosa, disegniamo la mappa di Karnaugh relativa a questa funzione riportando tutti i mintermini come 1 nella mappa stessa:

**Figura 33:** Esempio 10: Mappa di Karnaugh

Individuiamo ora gli implicanti. Il primo implicante è dato dal sotto-cubo di dimensione $2 \times 4$ indicato nella figura che segue e che corrisponde al termine $w$ :

**Figura 34:** Esempio 10: Primo Implicante w

Il secondo implicante è dato dal sotto-cubo di dimensione $2 \times 2$ indicato nella figura che segue e che corrisponde al termine $x'y'$ :

**Figura 35:** Esempio 10: Secondo Implicante x'y'

Il terzo implicante è dato dal sotto-cubo di dimensione $2 \times 2$ indicato nella figura che segue e che corrisponde al termine $x'z$ :

**Figura 36:** Esempio 10: Terzo Implicante x'z

La funzione minimizzata risulta essere, quindi, la seguente:

F = w + x'y' + x'z

Nella figura che segue è riportata la copertura completa:

Esempio 11

Si semplifichi la funzione booleana che segue:

F(w, x, y, z) = \Sigma(0, 2, 4, 6, 8, 10, 11)

Come fatto per gli altri esempi, il primo passo consiste nel disegnare la mappa di Karnaugh relativa a questa funzione:

**Figura 38:** Esempio 11: Mappa di Karnaugh

Individuiamo, adesso, gli implicanti della funzione.

Il primo implicante raccoglie tutti gli 1 agli angoli della mappa di Karnaugh. Tale implicante è riportato nella figura che segue e rappresenta il termine $x'z'$ :

**Figura 39:** Esempio 11: Primo implicante relativo al termine x'z'

Il secondo implicante è dato dal sotto-cubo di dimensione $2 \times 2$ indicato nella figura che segue e che corrisponde al termine $w'z'$ :

**Figura 40:** Esempio 11: Secondo implicante relativo al termine w'z'

L'ultimo implicante, invece, è dato dal sotto-cubo di dimensione $1 \times 2$ che individua il termine $wx'y$ ed è mostrato nella figura che segue:

**Figura 41:** Esempio 11: Terzo implicante relativo al termine wx'y

La funzione risulta essere quindi:

F(w, x, y, z) = x'z' + w'z' + wx'y

Di seguito è riportata la copertura completa:

**Figura 42:** Esempio 11: Copertura completa

Mappe di Karnaugh con più di Quattro Variabili

Le mappe per più di quattro variabili non sono così semplici da usare come le mappe per quattro o meno variabili. Una mappa a cinque variabili necessita di 32 quadrati e una mappa a sei variabili necessita di 64 quadrati. Quando il numero di variabili diventa grande, il numero di quadrati diventa eccessivo e la geometria per combinare quadrati adiacenti diventa più complessa.

Per tal motivo, quando si ha a che fare con funzioni con più di quattro variabili, è consigliabile utilizzare tecniche alternative di semplificazione, come l'algoritmo di Quine-McCluskey che vedremo nelle prossime lezioni.