Mappe di Karnaugh

1. Che cos'è una mappa di Karnaugh

Una mappa di Karnaugh è una tavola di verità ridisegnata come griglia. Maurice Karnaugh la presentò ai Bell Labs nel 1953 come modo per semplificare i circuiti di commutazione a occhio, ed è tuttora il modo più rapido di minimizzare a mano una piccola funzione booleana: niente algebra, nessuna legge da ricordare, solo rettangoli.

Ogni cella della mappa contiene una riga della tavola di verità. Ciò che rende la mappa più di un riordinamento è l'ordine in cui quelle righe sono disposte: le celle vicine differiscono per esattamente una variabile.

Questa sola proprietà fa tutto il lavoro. Se due celle vicine sono entrambe vere, la variabile che cambia fra loro non può essere ciò che rende vera l'espressione: sparisce, e un solo termine copre entrambe le celle. Semplificare diventa disegnare i rettangoli più grandi possibile.

2. Perché le colonne sembrano fuori ordine

Le colonne di una mappa di Karnaugh non contano 00, 01, 10, 11. Vanno 00, 01, 11, 10: codice Gray riflesso, un ordinamento in cui ogni valore differisce dal successivo per un solo bit. Contare in binario metterebbe 01 accanto a 10, che differiscono per due bit, e le celle vicine non direbbero più nulla.

Anche i bordi sono vicini. La prima e l'ultima colonna differiscono per una variabile, e così la prima e l'ultima riga: un gruppo può quindi uscire da un bordo e continuare dall'altro, ed è per questo che i quattro angoli di una mappa a quattro variabili formano un unico gruppo. Una mappa di Karnaugh è in realtà disegnata su un toro; il foglio piatto è solo una comodità.

3. Raggruppare gli uni

Per leggere sulla mappa una somma di prodotti minima, copri ogni cella che contiene un 1 con gruppi rettangolari, seguendo quattro regole:

• Un gruppo è un rettangolo di 1, 2, 4, 8 … celle: una potenza di due per lato.
• Un gruppo può scavalcare i bordi della mappa, in orizzontale, in verticale o in entrambi i sensi.
• I gruppi possono sovrapporsi. Coprire due volte una cella non costa nulla; lasciarne una scoperta cambia la funzione.
• Rendi ogni gruppo il più grande possibile, poi usa il minor numero di gruppi che copra tutti gli uni.

Ogni gruppo diventa un termine. Lo si legge chiedendosi quali variabili restano uguali in tutto il gruppo: quelle compaiono nel termine - così come sono dove valgono 1, negate dove valgono 0 - e ogni variabile che cambia sparisce. Un gruppo di due celle perde una variabile, uno di quattro ne perde due, uno di otto ne perde tre. L'espressione minima è la disgiunzione dei termini.

4. Un esempio svolto

Prendiamo (A ∧ B) ∨ (¬A ∧ C) ∨ (B ∧ C ∧ D). La sua mappa ha quattro variabili: A e B sulle righe, C e D sulle colonne.

Due gruppi coprono tutti gli uni. Il primo è il blocco di quattro celle nelle due righe con A = 0 e nelle due colonne con C = 1: al suo interno cambiano sia B sia D, che quindi spariscono, e il termine è ¬A ∧ C. Il secondo è l'intera riga in cui A e B valgono 1, su tutte e quattro le colonne: C e D vi cambiano, e resta A ∧ B.

La forma minima è dunque (¬A ∧ C) ∨ (A ∧ B). Il terzo termine dell'espressione di partenza, B ∧ C ∧ D, è svanito: ogni cella che copriva era già coperta da uno dei due gruppi. È l'assorbimento, visto con gli occhi.

5. Implicanti primi ed essenziali

Un gruppo che non può essere ingrandito si chiama implicante primo. Elencare gli implicanti primi è la metà facile del problema; scegliere quali tenere è la metà che va storta.

Se una cella è coperta da un solo implicante primo, quell'implicante è essenziale: nessuna forma minima può farne a meno, perché nient'altro copre quella cella. Prendi prima gli implicanti essenziali, poi copri ciò che resta con il minor numero possibile degli altri gruppi.

Essere ingordi - prendere ogni volta il gruppo più grande ancora disponibile - è allettante e non funziona sempre. Su una tabella ciclica, dove nessun implicante è essenziale e ogni cella è coperta due volte, la scelta ingorda può finire con un termine in più della risposta migliore. La mappa di questo sito esplora invece tutte le scelte rimaste, cosa che con quattro variabili non costa nulla.

6. Raggruppare gli zeri, invece

Tutto quanto sopra funziona altrettanto bene sugli zeri. Coprili con gli stessi rettangoli, leggi ogni gruppo con i letterali negati - una variabile che vale 1 in tutto il gruppo compare negata, una che vale 0 compare così com'è - e unisci i gruppi con ∧ anziché con ∨.

Il risultato è un prodotto di somme: una congiunzione di disgiunzioni falsa esattamente nelle celle in cui l'espressione è falsa, e quindi vera in tutte le altre. Quale delle due forme sia più corta dipende dalla funzione - una formula con pochi uni ha una somma di prodotti corta, una con pochi zeri un prodotto di somme corto - perciò conviene leggerle entrambe sulla mappa prima di scegliere.

7. Mappe più grandi e condizioni indifferenti

Cinque e sei variabili si possono disegnare come due o quattro mappe a quattro variabili sovrapposte, considerando adiacenti le celle nella stessa posizione su strati vicini. Funziona, ma l'adiacenza che rendeva visivo il metodo diventa qualcosa da ricordare anziché da vedere. Oltre, l'algoritmo di Quine-McCluskey fa lo stesso lavoro in forma di tabella: è la versione meccanica esattamente di questo raggruppamento, ed è ciò che gira dietro le mappe di questo sito.

La progettazione hardware aggiunge un'altra idea. Alcune combinazioni d'ingresso non si presentano mai - una cifra decimale codificata in binario non è mai 1010 - così al progettista non importa cosa ne faccia il circuito. Quelle celle si segnano con una X e possono essere lette con l'uno o l'altro valore, quello che rende i gruppi più grandi. Le mappe di questa calcolatrice nascono da una formula, che dà un valore a ogni assegnazione: nessuna cella è mai indifferente.

8. Provaci

Scrivi nella calcolatrice un'espressione da due a quattro variabili e la sua mappa compare sotto la tavola di verità, con ogni gruppo cerchiato del proprio colore e la forma minima scritta sotto. Passa a prodotto di somme per vedere raggruppati gli zeri.