Nella lezione precedente abbiamo visto come l’algebra di Boole permetta di semplificare espressioni logiche attraverso l’applicazione sistematica di teoremi e proprietà. Quel metodo, pur corretto, presenta un limite pratico: non è sempre evidente quale teorema applicare e in quale ordine. Due persone che partono dalla stessa espressione possono percorrere strade diverse, arrivando a risultati equivalenti ma non immediatamente riconoscibili come tali.
La Mappa di Karnaugh — abbreviata K-map, dal nome del matematico Maurice Karnaugh che la introdusse nel 1953 mentre lavorava ai Bell Telephone Laboratories — risolve questo problema spostando la semplificazione dal piano algebrico a quello visivo. Invece di manipolare simboli, si lavora su una griglia in cui le semplificazioni diventano raggruppamenti di celle adiacenti, immediatamente riconoscibili a colpo d’occhio.
Il risultato è un’espressione minima in forma di Somma di Prodotti (Sum of Products, SOP), cioè un OR di termini AND. La K-map garantisce di trovare un’espressione minima in modo sistematico, senza dover indovinare quale legge applicare.
A cosa serve nel contesto della programmazione
Nel codice applicativo quotidiano — PHP, JavaScript, Python — la K-map non si usa direttamente. Si usa invece nella progettazione dell’hardware su cui il codice gira: processori, microcontrollori, circuiti logici programmabili. Conoscerla è utile per due ragioni. La prima è culturale: capire come si ottimizza la logica a livello hardware aiuta a comprendere perché i processori sono costruiti come sono. La seconda è metodologica: il ragionamento visivo della K-map — cercare pattern e raggruppamenti in una griglia — è una competenza che si trasferisce anche ad altri contesti, come l’ottimizzazione di query o la semplificazione di condizioni complesse nel codice.
Il Principio fondamentale: il Codice Gray
Il principio chiave della K-map non risiede nella griglia in sé, ma nell’ordine in cui le combinazioni di input vengono disposte sugli assi. Non si usa l’ordine binario naturale (00, 01, 10, 11), bensì il Codice Gray: una numerazione binaria in cui due valori consecutivi differiscono sempre e soltanto per un bit.
| Posizione | Binario naturale | Codice Gray |
|---|---|---|
| 0 | 00 | 00 |
| 1 | 01 | 01 |
| 2 | 10 | 11 |
| 3 | 11 | 10 |
Nel binario naturale, il passaggio dalla posizione 1 (01) alla posizione 2 (10) cambia entrambi i bit contemporaneamente. Nel Codice Gray, ogni passaggio modifica un solo bit.
Questa proprietà è fondamentale perché garantisce che due celle adiacenti nella mappa rappresentino due mintermini che differiscono per una sola variabile. Quando due mintermini differiscono per una sola variabile, quella variabile può essere eliminata: è esattamente il teorema di adiacenza, che afferma che A·B + A·B' = A. La K-map rende visibile questa operazione senza bisogno di applicarla algebricamente.
Struttura della K-map a due Variabili
Con due variabili (A e B) si hanno 2² = 4 mintermini, quindi una mappa con 4 celle.
| Cella (A, B) | Mintermine | Termine prodotto |
|---|---|---|
| (0, 0) | m0 | A’·B’ |
| (0, 1) | m1 | A’·B |
| (1, 0) | m2 | A·B’ |
| (1, 1) | m3 | A·B |
Struttura della K-map a tre Variabili
Con tre variabili (A, B, C) si hanno 2³ = 8 celle. La mappa diventa una griglia 2×4: la variabile A è disposta sull’asse verticale, mentre le due variabili B e C condividono l’asse orizzontale, ordinate secondo il Codice Gray (00, 01, 11, 10).
Nota cruciale: adiacenza toroidale
Le colonne BC=00 e BC=10 sono adiacenti, anche se si trovano ai lati opposti della mappa. Questo perché la mappa è concettualmente «avvolta» come un cilindro: il bordo destro tocca il bordo sinistro. Ignorare questa proprietà è l’errore più comune nella lettura della K-map e porta a non trovare i gruppi più grandi possibili.
Le Regole di Raggruppamento
Il cuore del metodo sta nella formazione dei gruppi. Ogni gruppo di celle con valore 1 deve rispettare le seguenti regole.
- Dimensione potenza di 2: i gruppi validi hanno dimensione 1, 2, 4 o 8 celle. Un gruppo da 3 o da 5 celle non è mai ammesso;
- Forma rettangolare: il gruppo deve formare un rettangolo (o un quadrato) sulla mappa, con celle contigue in orizzontale, in verticale o in entrambe le direzioni;
- Massimalità: ogni gruppo deve essere il più grande possibile. Un implicante più piccolo che potrebbe essere assorbito in uno più grande non va usato da solo, a meno che non sia necessario per coprire una cella altrimenti scoperta;
- Sovrapposizione consentita: una cella può appartenere a più gruppi contemporaneamente. Questa proprietà è utile per massimizzare la dimensione di ciascun gruppo;
- Adiacenza toroidale: i bordi opposti della mappa si toccano;
- Copertura completa: tutte le celle con valore 1 devono essere coperte da almeno un gruppo.
Come ricavare il Termine semplificato da un Gruppo
Una volta individuato un gruppo, il termine AND corrispondente si ricava osservando quali variabili non cambiano valore all’interno del gruppo:
- se una variabile vale sempre 0 nel gruppo, compare come complementata (ad esempio A’);
- se una variabile vale sempre 1 nel gruppo, compare non complementata (ad esempio A);
- se una variabile cambia valore (vale 0 in alcune celle e 1 in altre), non compare nel termine: è la variabile eliminata dalla semplificazione.
| Dimensione del gruppo | Variabili eliminate | Letterali nel termine |
|---|---|---|
| 1 cella (2⁰) | 0 | n (tutte presenti) |
| 2 celle (2¹) | 1 | n − 1 |
| 4 celle (2²) | 2 | n − 2 |
| 8 celle (2³) | 3 | n − 3 → F = 1 |
Dove n è il numero totale di variabili della mappa. Più grande è il gruppo, più semplice è il termine risultante.
Esempio completo a due Variabili
Sia data la funzione: F(A, B) = Σm(1, 2, 3), ovvero F vale 1 per i mintermini m1, m2, m3.
Passo 1: tabella di Verità
| A | B | F |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
Passo 2: K-map compilata con raggruppamenti
Passo 3: analisi dei gruppi e risultato
Gruppo verde — celle m1 e m3 (colonna B=1, entrambe le righe):
- A: vale 0 in m1 e 1 in m3 → cambia → eliminata;
- B: vale 1 in entrambe → costante 1 → rimane come B.
Termine: B
Gruppo arancione — celle m2 e m3 (riga A=1, entrambe le colonne):
- A: vale 1 in entrambe → costante 1 → rimane come A;
- B: vale 0 in m2 e 1 in m3 → cambia → eliminata.
Termine: A
Espressione finale: F = A OR B
La cella m3 appartiene a entrambi i gruppi: questo è corretto e consentito dalle regole. Il risultato è verificabile immediatamente: F vale 0 solo quando A=0 e B=0 (mintermine m0), e vale 1 in tutti gli altri casi — esattamente come un OR.
Esempio completo a tre Variabili
Sia data la funzione: F(A, B, C) = Σm(1, 3, 5, 7), ovvero F vale 1 ogni volta che C = 1.
Passo 1: tabella di Verità
| A | B | C | F |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 0 |
| 1 | 1 | 1 | 1 |
Passo 2: K-map compilata con raggruppamento
Passo 3: analisi del gruppo e risultato
Il gruppo verde comprende tutte e quattro le celle con valore 1: (A=0, BC=01), (A=0, BC=11), (A=1, BC=01), (A=1, BC=11), ovvero i mintermini m1, m3, m5, m7. Analizziamo le variabili:
- A: vale 0 nelle prime due celle e 1 nelle ultime due → cambia → eliminata;
- B: vale 0 in m1 e m5, vale 1 in m3 e m7 → cambia → eliminata;
- C: vale 1 in tutte e quattro le celle → costante a 1 → rimane come C.
Espressione finale: F = C
Un gruppo da 4 celle su 3 variabili elimina 2 variabili, lasciando un termine con un solo letterale. Il risultato è immediato: F vale 1 esattamente quando C vale 1, indipendentemente da A e B.
Errori comuni da evitare
Conoscere le insidie frequenti è utile quanto conoscere la procedura corretta. I seguenti errori compaiono spesso nelle prime applicazioni pratiche.
- Gruppi di dimensione non valida: formare gruppi da 3 o da 5 celle. Le dimensioni ammesse sono solo potenze di 2 (1, 2, 4, 8);
- Adiacenza toroidale dimenticata: le celle ai bordi opposti della mappa si toccano e spesso formano i gruppi più grandi. Ignorare questa proprietà porta a espressioni non minime;
- Gruppi non massimali: usare gruppi più piccoli quando ne esistono di più grandi che li comprendono. Il risultato è logicamente corretto ma non minimo;
- Celle scoperte: lasciare celle con valore 1 non coperte da alcun gruppo. Ogni «1» deve appartenere ad almeno un implicante.
Confronto tra Metodo algebrico e K-map
| Caratteristica | Metodo algebrico | K-map |
|---|---|---|
| Approccio | Simbolico, equazionale | Visivo, grafico |
| Scalabilità | Difficile oltre 4 variabili | Pratica fino a 4 variabili |
| Garanzia di minimalità | Dipende dall’abilità dell’utente | Sistematica se i gruppi sono massimali |
| Adatto a | Dimostrazioni teoriche, espressioni semplici | Progettazione pratica di circuiti |
| Contesto d’uso | Algebra, programmazione | Hardware, elettronica digitale |
La K-map e l’algebra booleana non sono alternative esclusive: conoscere entrambi i metodi permette di verificare i risultati dell’uno con l’altro, rafforzando la comprensione dei principi sottostanti. Per espressioni con più di quattro variabili si ricorre ad algoritmi automatici come il metodo di Quine-McCluskey, che eseguono la stessa operazione in modo computazionale.
Esercizi di Verifica
Esercizio 1 — K-map a due Variabili
Data la seguente tabella di verità per F(A, B), compila la K-map, identifica i gruppi e scrivi l’espressione minima.
| A | B | F |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
Dopo aver trovato l’espressione minima, verifica il risultato scrivendo il codice PHP che calcola F per tutte e quattro le combinazioni e confrontalo con la tabella.
Esercizio 2 — K-map a tre Variabili già compilata
La seguente K-map a tre variabili è già compilata. Identifica i gruppi, ricava i termini e scrivi l’espressione minima F(A, B, C).
Esercizio 3 — Dalla Tabella alla K-map
Data la seguente tabella di verità per F(A, B, C), costruisci la K-map a tre variabili, identifica tutti i gruppi massimali e scrivi l’espressione minima.
| m | A | B | C | F |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 1 | 1 |
| 2 | 0 | 1 | 0 | 0 |
| 3 | 0 | 1 | 1 | 1 |
| 4 | 1 | 0 | 0 | 0 |
| 5 | 1 | 0 | 1 | 1 |
| 6 | 1 | 1 | 0 | 1 |
| 7 | 1 | 1 | 1 | 1 |
Dopo aver trovato l’espressione minima, verifica il risultato con il codice PHP usando un ciclo che calcola F per tutte le combinazioni.
Esercizio 4 — Riflessione
Rispondi alle seguenti domande scrivendo almeno tre righe per ciascuna risposta.
- Perché nella K-map si usa il Codice Gray invece dell’ordine binario naturale? Cosa succederebbe se si usasse l’ordine binario normale?
- Qual è la differenza pratica tra semplificare un’espressione con le leggi algebriche di Boole e semplificarla con la K-map? In quale contesto preferiresti usare l’uno o l’altro metodo?
- La K-map garantisce di trovare sempre un’espressione minima. Perché questa garanzia è importante nella progettazione hardware ma meno critica nella scrittura di codice applicativo?