Le mappe di Karnaugh — filoconduttore

Semplificare con l’algebra di Boole funziona, ma richiede occhio: bisogna vedere quale raccoglimento conviene. La mappa di Karnaugh rende la semplificazione un procedimento grafico e meccanico: si segnano gli 1, si cerchiano i gruppi, si legge il risultato.

La mappa

È la tabella di verità ripiegata in una griglia. Per tre variabili $A$ , $B$ , $C$ : le colonne portano le combinazioni di $AB$ , le righe i valori di $C$ .

	$AB$ =00	01	11	10
$C$ =0
$C$ =1

Le colonne non sono in ordine binario: la sequenza è $00,\,01,\,11,\,10$ — non $00,\,01,\,10,\,11$ . È codice Gray: fra colonne adiacenti cambia una sola variabile.

Non è pignoleria, è l’intero motivo per cui la mappa funziona: due caselle vicine differiscono per una variabile sola, quindi raggrupparle equivale al raccoglimento $X + \overline{X} = 1$ fatto a occhio. Con l’ordine binario la proprietà si rompe e la mappa non semplifica più niente.

Le regole dei raggruppamenti

Segnati gli 1 della funzione, si cerchiano a gruppi. Le regole:

i gruppi contengono solo 1, e sono rettangoli di 1, 2, 4 o 8 caselle — solo potenze di due;
i gruppi più grandi sono meglio: più caselle = meno variabili nel termine;
i gruppi possono sovrapporsi: uno stesso 1 può stare in più gruppi;
la mappa si richiude ai bordi: la prima e l’ultima colonna sono adiacenti (sempre per il codice Gray), quindi un gruppo può “uscire” da destra e rientrare da sinistra;
ogni 1 deve finire in almeno un gruppo.

Leggere un gruppo

Da ogni gruppo si legge un termine: si tengono solo le variabili che non cambiano dentro il gruppo, col loro valore (diretta se vale 1, negata se vale 0). Le variabili che cambiano spariscono.

Esempio — la funzione con questi 1:

	00	01	11	10
$C$ =0	1	1	1	1
$C$ =1			1	1

Gruppo 1: tutta la prima riga (4 caselle). Dentro, $A$ e $B$ assumono tutti i valori — spariscono. Resta solo $C = 0$ , quindi il termine è $\overline{C}$ .

Gruppo 2: il quadrato 2×2 delle colonne 11 e 10 (4 caselle). Dentro, $B$ e $C$ cambiano — spariscono. Resta $A = 1$ : termine $A$ .

y = A + \overline{C}

Sei termini di partenza, due lettere all’arrivo — e il gruppo 2 riusa due caselle già prese dal gruppo 1: la sovrapposizione è permessa e conviene, perché rende entrambi i gruppi più grandi.

Più grande il gruppo, più corto il termine: 1 casella → tre variabili, 2 caselle → due, 4 caselle → una, 8 caselle → la funzione vale 1.

L’errore da principiante è fare tanti gruppi piccoli “per sicurezza”: il risultato è corretto ma non semplificato. Prima cerca i gruppi da 4, poi da 2, e i singoli solo per gli 1 rimasti orfani.

Esercizio. Semplifica con la mappa la funzione a tre variabili che vale 1 nelle combinazioni ( $A$ , $B$ , $C$ ): (0,0,1), (0,1,1), (1,1,0), (1,1,1).

Mostra la soluzione

Costruisco la mappa segnando gli 1:

	$AB$ =00	01	11	10
$C$ =0			1
$C$ =1	1	1	1

Gruppo 1 (orizzontale, riga $C$ =1, colonne 00 e 01): dentro, $B$ cambia e sparisce; restano $A = 0$ e $C = 1$ : termine $\overline{A}\,C$ .

Gruppo 2 (verticale, colonna 11): $C$ cambia e sparisce; restano $A = 1$ e $B = 1$ : termine $AB$ .

y = \overline{A}\,C + AB

Verifica. Controllo una combinazione per gruppo più una a zero. Con $(0,1,1)$ : $\overline{A}C = 1$ ✓. Con $(1,1,0)$ : $AB = 1$ ✓. Con $(1,0,0)$ , che nella mappa è vuota: $\overline{A}C = 0$ e $AB = 0$ , quindi $y = 0$ ✓. La semplificata riproduce la tabella.