Algebra di Boole e mappe di Karnaugh: il metodo

Fine settembre 2026: al primo anno di ingegneria informatica o elettronica e informatica, il corso di Reti logiche (a volte dentro Architettura degli elaboratori o Fondamenti di informatica) ha aperto l’anno con l’algebra di Boole e sta entrando nelle mappe di Karnaugh — dopo l’avvio del semestre a metà settembre, al Politecnico di Milano il 14 settembre 2026. Dove è prevista una prova in itinere, cade tipicamente a fine ottobre-inizio novembre — al Politecnico dal 29 ottobre al 2 novembre 2026, circa cinque settimane da adesso — ed è quasi sempre lo scoglio su cui la logica combinatoria si gioca metà del voto. Lo stesso argomento, con un taglio più applicato, si incontra anche in terza negli istituti tecnici (Elettronica, Informatica, Meccanica), dentro Sistemi ed Elettronica.

Il problema tipico non è capire cosa sono AND, OR e NOT — quello è immediato. È che tra tavola di verità, forma algebrica e mappa di Karnaugh esistono tre rappresentazioni diverse della stessa funzione, e passare dall’una all’altra senza un metodo fisso porta quasi sempre a un errore banale: un raggruppamento sbagliato, un ordine dei bit non rispettato, un’adiacenza sui bordi dimenticata.

Porte logiche e tavole di verità

Le porte logiche fondamentali operano su variabili booleane (0 o 1) e restituiscono un valore booleano. Le tavole di verità qui sotto sono lo strumento base per definirle, con $A$ e $B$ variabili di ingresso:

E le porte a singolo ingresso o negate:

NAND e NOR sono AND e OR con l’uscita negata, ma meritano attenzione a parte perché sono funzionalmente complete: con la sola porta NAND (o la sola NOR) si può costruire qualsiasi funzione booleana, incluse AND, OR e NOT stesse — da qui la richiesta ricorrente in compito: “implementa la funzione usando solo porte NAND”.

Assiomi e teoremi che servono davvero

Oltre alle proprietà elementari (commutativa, associativa, distributiva — identiche a quelle dell’algebra ordinaria, con $\cdot$ al posto di “e” e $+$ al posto di “o”), tre risultati tornano continuamente nella semplificazione algebrica:

Teoremi di De Morgan, i più usati in assoluto:

In parole: la negazione di un AND è l’OR delle negazioni, e viceversa. È la legge che permette di convertire qualunque espressione in una forma implementabile con sole porte NAND o sole porte NOR.

Legge di assorbimento:

Utile per eliminare termini ridondanti in un’espressione già scritta, prima ancora di disegnare una mappa.

Teorema del consenso (o della ridondanza): se un’espressione contiene i termini $A\cdot B$, $\overline{A}\cdot C$ e $B\cdot C$, quest’ultimo è sempre ridondante e si può eliminare:

Questo teorema spiega perché a volte un’espressione “sembra” già minima ma in realtà contiene ancora un termine eliminabile — ed è uno dei motivi per cui conviene sempre passare dalla mappa di Karnaugh piuttosto che fidarsi solo della manipolazione algebrica a mano.

Dalla tavola di verità alle forme canoniche

Ogni funzione booleana può essere scritta in due forme canoniche equivalenti, entrambe derivabili meccanicamente dalla tavola di verità:

Forma SOP (Sum of Products, somma di prodotti): si prendono tutte le righe dove la funzione vale 1, si scrive per ciascuna il mintermine (il prodotto di tutte le variabili, negate se valgono 0 in quella riga) e si sommano tutti i mintermini.

Forma POS (Product of Sums, prodotto di somme): si prendono tutte le righe dove la funzione vale 0, si scrive per ciascuna il maxtermine (la somma di tutte le variabili, negate se valgono 1 in quella riga) e si moltiplicano tutti i maxtermini.

Esempio con due variabili: se $F=1$ solo quando $A=0,B=1$ e quando $A=1,B=1$, la forma SOP è

Le due forme sono sempre equivalenti (rappresentano la stessa funzione), ma quasi sempre una delle due porta a un circuito più semplice dell’altra a seconda di quante righe valgono 1 rispetto a quante valgono 0 — un altro motivo per verificare entrambe prima di scegliere come implementare.

Le mappe di Karnaugh: il metodo

La mappa di Karnaugh è una tavola di verità riorganizzata in una griglia, dove le celle adiacenti differiscono per una sola variabile. Per ottenere questa proprietà, le intestazioni di riga e colonna non seguono l’ordine binario normale (00, 01, 10, 11) ma il codice Gray:

Questo è il punto che genera più errori: usare l’ordine binario invece di quello Gray rompe la proprietà di adiacenza che rende utile la mappa, e porta a raggruppamenti scorretti.

Mappa a 2 variabili

Mappa a 3 variabili ($A$, $B$, $C$)

Mappa a 4 variabili ($A$, $B$, $C$, $D$)

Le regole dei raggruppamenti

1. Ogni gruppo deve contenere una potenza di 2 di celle a 1: 1, 2, 4, 8, 16 — mai 3, 6 o altri numeri.
2. Un gruppo può estendersi anche sui bordi opposti della mappa: la prima e l’ultima colonna sono adiacenti tra loro, così come la prima e l’ultima riga (e i quattro angoli di una mappa a 4 variabili sono tutti adiacenti fra loro).
3. I gruppi vanno fatti il più grandi possibile: un gruppo da 4 elimina più variabili di due gruppi da 2 che coprono le stesse celle.
4. La copertura deve essere minima: ogni cella a 1 deve essere coperta da almeno un gruppo, ma un gruppo che copre solo celle già coperte da altri gruppi più grandi è ridondante e va eliminato.
5. Da ogni gruppo si legge un termine prodotto: le variabili che non cambiano all’interno del gruppo compaiono nel termine (negate se valgono 0), quelle che cambiano spariscono.

Le condizioni di indifferenza (don’t care)

In molti problemi reali alcune combinazioni di ingresso non si verificano mai — nella codifica BCD (Binary-Coded Decimal) le combinazioni da 1010 a 1111 non rappresentano nessuna cifra decimale valida. Queste celle si indicano con una X (“don’t care”) nella mappa e si possono trattare come 0 o come 1, a seconda di cosa conviene per il raggruppamento più grande possibile: un margine di libertà che spesso semplifica la funzione finale. Solo le celle X realmente raggruppate contano come 1; una X lasciata fuori da ogni gruppo resta priva di significato.

Implementazione solo con porte NAND

Una volta ottenuta la forma SOP minima, per implementarla con sole porte NAND si nega due volte l’intera espressione (la doppia negazione non cambia nulla) e si distribuisce la negazione interna con De Morgan, trasformando ogni AND e OR in una combinazione di NAND. Il risultato pratico che si insegna quasi ovunque: ogni porta AND diventa una NAND seguita da un inverter, e ogni porta OR con ingressi negati diventa direttamente una NAND. Non serve rifare la dimostrazione ogni volta: una volta capito il principio, la conversione è meccanica.

I tre esercizi svolti

Esercizio 1 — semplificazione algebrica con De Morgan

Semplifica l’espressione:

Applico De Morgan al primo termine:

Quindi:

Raccolgo $A$:

Verifica per casi: se $A=0$, $F=0$ in entrambe le combinazioni di $B$ (si può controllare sostituendo direttamente nell’espressione di partenza); se $A=1$, $F=1$ in entrambe. Coerente con $F=A$.

Esercizio 2 — mappa di Karnaugh a 3 variabili

Data la funzione con mintermini $F(A,B,C)=\sum (0,1,2,3,6)$ (cioè $F=1$ per quei mintermini, 0 altrove), trova la forma minima.

Mappa (righe $A$, colonne $BC$ in ordine Gray 00-01-11-10):

Raggruppamenti: l’intera riga $A=0$ forma un gruppo da 4, dove $A$ resta 0 e $B$, $C$ cambiano entrambi → termine $\overline{A}$. La cella $m_6$ ($A=1,B=1,C=0$) sembra isolata, ma è adiacente a $m_2$ ($A=0$, $BC=10$), che sta nella stessa colonna: un gruppo da 2 verticale in cui cambia solo $A$ e restano fissi $B=1$, $C=0$ → termine $B\cdot \overline{C}$. Che $m_2$ sia già coperta dal primo gruppo non conta: una cella può stare in più gruppi, e usarla qui fa sparire un letterale.

Se avessi lasciato $m_6$ da sola avresti scritto $F=\overline{A}+AB\overline{C}$: giusta, ma con un letterale in più. È lo stesso risultato che dà l’algebra, perché $\overline{A}+AX=\overline{A}+X$.

Verifica su $m_6$ ($A=1,B=1,C=0$): $B\overline{C}=1$ → $F=1$. Corretto. Su $m_4$ ($A=1,B=0,C=0$, deve dare 0): $\overline{A}=0$, $B\overline{C}=0$ → $F=0$. Corretto. Su $m_7$ ($A=1,B=1,C=1$, deve dare 0): $\overline{A}=0$, $B\overline{C}=0$ → $F=0$. Corretto.

Esercizio 3 — mappa a 4 variabili con don’t care (BCD)

Un circuito deve accendere un segnale $F$ quando l’ingresso a 4 bit $ABCD$ (codifica BCD) rappresenta una cifra maggiore o uguale a 5. Le combinazioni da 1010 a 1111 (10-15) non si presentano mai: sono don’t care.

$F=1$ per $5,6,7,8,9$ (mintermini $m_5,m_6,m_7,m_8,m_9$); don’t care per $10$–$15$ ($m_{10}$–$m_{15}$); $F=0$ per $0,1,2,3,4$.

Mappa (righe $AB$, colonne $CD$, entrambe in ordine Gray):

Qui i don’t care fanno la differenza: li usi come 1 ogni volta che ti permettono di allargare un gruppo, e li ignori quando non servono. Tre gruppi coprono tutti gli 1:

• Gruppo 1 — da 8: le due righe $AB=11$ e $AB=10$ intere (quattro X più $m_8$, $m_9$ e le X $m_{10}$, $m_{11}$). In quelle righe $A=1$ è fisso e $B$, $C$, $D$ cambiano tutti → termine $A$.
• Gruppo 2 — da 4: righe $AB=01,11$, colonne $CD=01,11$: $m_5,m_7,m_{13},m_{15}$. Fissi $B=1$ e $D=1$ → termine $B\cdot D$.
• Gruppo 3 — da 4: righe $AB=01,11$, colonne $CD=11,10$: $m_7,m_6,m_{15},m_{14}$. Fissi $B=1$ e $C=1$ → termine $B\cdot C$.

Senza sfruttare le X fino in fondo si arriva facilmente a $F=BD+A\overline{C}+BC\overline{D}$: è una funzione corretta (dà gli stessi valori su tutte le cifre da 0 a 9), ma non è minima — tre letterali in più e una porta a tre ingressi. In verifica vale meno punti, ed è l’errore tipico di chi disegna i gruppi partendo dagli 1 senza chiedersi se una X li farebbe crescere.

Verifica su $m_9$ ($1001$: $A=1$) → $F=1$. Corretto. Su $m_4$ ($0100$: $A=0,B=1,C=0,D=0$): $B\cdot D=0$, $B\cdot C=0$ → $F=0$. Corretto. Su $m_6$ ($0110$): $B\cdot C=1$ → $F=1$. Corretto.

Gli errori che costano punti

• Ordine binario invece di Gray sulle intestazioni della mappa: rompe l’adiacenza e porta a raggruppamenti che sembrano validi ma non lo sono.
• Gruppi da 3 o da 6: solo potenze di 2 (1, 2, 4, 8…) sono raggruppamenti validi.
• Dimenticare l’adiacenza sui bordi e sugli angoli: la mappa “si chiude ad anello” su ogni dimensione, e molti studenti trattano i bordi come limiti invece che come confini che si toccano.
• Gruppi ridondanti: un gruppo piccolo le cui celle sono già tutte coperte da gruppi più grandi va tolto, altrimenti la forma non è minima.
• Trattare una X non raggruppata come se contasse comunque come 1: solo le X effettivamente incluse in un gruppo contribuiscono alla funzione finale.

Dove porta dopo

L’algebra di Boole e le mappe di Karnaugh sono il fondamento della logica combinatoria: il passo successivo tipico nel programma è la logica sequenziale (flip-flop, registri, contatori), che si costruisce proprio sopra i circuiti combinatori qui semplificati. Se ti serve rivedere prima la rappresentazione dei numeri con cui questi circuiti lavorano davvero — interi con segno, virgola mobile — il metodo passo passo è in complemento a 2 e virgola mobile, mentre per il quadro più ampio di come questi blocchi si inseriscono nella CPU il riferimento è architettura di Von Neumann e CPU.

Come lavoro su questo argomento in lezione

Con i miei studenti la prima regola che fisso è: mai passare direttamente dall’espressione algebrica alla semplificazione a occhio. Si scrive prima la tavola di verità o si individuano i mintermini, poi si disegna sempre la mappa con l’ordine Gray scritto esplicitamente in testa a righe e colonne — è un secondo che evita l’errore più comune di tutti. Una simulazione dedicata a Reti logiche non c’è ancora sul sito: se vuoi allenarti nel frattempo su altre materie universitarie trovi la categoria in simulazioni per l’università.

Per il quadro delle materie di informatica che seguo trovi la pagina di informatica, e per l’affiancamento universitario in generale quella delle ripetizioni universitarie. Se le mappe di Karnaugh restano un punto debole dopo aver provato questo metodo, scrivimi dai contatti: la prima chiamata conoscitiva è gratuita e dura mezz’ora.