Vai al contenuto
← Algebra booleana · Lezione 3
Algebra Booleana · Lezione 3

Dalla tabella
all'espressione minima

Partiamo da una tabella di verità e ricaviamo l'espressione che la descrive. Le forme canoniche ci danno un metodo sistematico; le mappe di Karnaugh ci aiutano a semplificare il risultato. Lavoreremo con un massimo di 4 variabili e con i don't care, fino a progettare un rilevatore di numeri primi.

1
Capitolo 1

Dalla tabella all'espressione

Finora la strada era: espressione → tabella. Ma quando progettiamo un circuito si parte dall'altra parte: so cosa deve fare il circuito (la tabella) e cerco l'espressione.

Le domande sono due, in sequenza. Esiste sempre un'espressione che produce una tabella data? Sì, e si scrive in modo meccanico: sono le forme canoniche. È la più semplice? Quasi mai, ed è per questo che esistono le mappe di Karnaugh: la forma canonica può contenere termini ridondanti, che la mappa aiuta a individuare.

2
Capitolo 2

Mintermini, maxtermini, SOP e POS

📘 Mintermini e SOP

Un mintermine è un prodotto (AND) di tutte le variabili, ciascuna negata o no, che vale 1 per una sola riga della tabella. La somma di prodotti (SOP) è l'OR dei mintermini delle righe in cui l'uscita è 1.

Esempio. Uscita = 1 nelle righe ABC=001, 011, 100ABC=001,\ 011,\ 100. I mintermini: A‾ B‾ C\overline{A}\,\overline{B}\,C, A‾ B C\overline{A}\,B\,C, A B‾ C‾A\,\overline{B}\,\overline{C}. SOP:

F=A‾ B‾ C+A‾ B C+A B‾ C‾F=\overline{A}\,\overline{B}\,C+\overline{A}\,B\,C+A\,\overline{B}\,\overline{C}

(Ogni riga con 0 → variabile negata; con 1 → variabile diretta.) La costruzione è puramente meccanica, basta applicare la regola a ciascuna riga. Il risultato descrive la funzione, ma può essere ulteriormente semplificato.

📘 Maxtermini e POS

Specularmente, il maxtermine è un OR di tutte le variabili che vale 0 per una sola riga, e la POS (prodotto di somme) è l'AND dei maxtermini delle righe in cui l'uscita è 0, con la convenzione opposta: riga con 1 → variabile negata. SOP e POS descrivono la stessa funzione da due lati; per semplificare, di solito si parte dalla SOP.

La notazione compatta elenca solo i numeri di riga: la funzione dell'esempio è F=Σm(1,3,4)F=\Sigma m(1,3,4), «somma dei mintermini 1, 3, 4», e la sua POS è ΠM(0,2,5,6,7)\Pi M(0,2,5,6,7). È il modo in cui gli esercizi (e lo strumento del corso) assegnano le funzioni: il numero di riga, letto in binario, dice il valore delle variabili.

💡 Quale delle due?

Se la tabella ha pochi 1, conviene la SOP (pochi mintermini); se ha pochi 0, la POS. Nel prossimo capitolo vedremo come semplificare l'espressione ottenuta.

3
Capitolo 3

Le mappe di Karnaugh

La SOP canonica può essere semplificata con le leggi di Boole. La mappa di Karnaugh dispone i mintermini in modo da rendere visibili le combinazioni che si possono semplificare.

📘 La mappa di Karnaugh

È la tabella di verità disposta in una griglia in cui celle adiacenti differiscono per una sola variabile (codice Gray). Si raggruppano gli 1 in blocchi rettangolari di dimensione potenza di 2 (1, 2, 4, 8), il più grandi possibile, anche con avvolgimento ai bordi. Ogni gruppo diventa un prodotto semplificato.

Perché il codice Gray. Le colonne si ordinano 00, 01, 11, 10, non in binario. Questa disposizione è necessaria perché tra celle vicine cambia un solo bit, quindi due 1 adiacenti sono due mintermini che differiscono per una sola variabile, che è esattamente la sagoma XB+XB‾=XXB+X\overline{B}=X della lezione 2. Raggruppare queste celle equivale ad applicare l'identità. E l'adiacenza continua oltre il bordo: prima e ultima colonna si toccano, come su un cilindro.

💡 Regola dei gruppi

Più grande è il gruppo, più corto è il termine (spariscono le variabili che dentro il gruppo cambiano). Un gruppo di 2 elimina 1 variabile, uno di 4 ne elimina 2, e così via. Ogni 1 dev'essere coperto da almeno un gruppo; i gruppi devono essere il più grandi possibile, e il meno possibile.

LaboratorioKarnaugh a 3 variabili

Clicca le celle per mettere gli 1 (righe = AA, colonne = BCBC in codice Gray). La forma minima viene calcolata dal vivo. Ora gli 1 sono dove C=1C=1: la minima è semplicemente CC (quattro mintermini, una lettera).

⚠️ Tre errori da evitare nelle mappe

Ordinare le colonne in binario (00, 01, 10, 11) invece che in Gray: le adiacenze non corrispondono più al cambiamento di un solo bit. Dimenticare che prima e ultima colonna sono adiacenti (e prima e ultima riga): il gruppo «a cavallo del bordo» sfugge. Fare gruppi da 3 o da 6: solo potenze di 2.

4
Capitolo 4

Quattro variabili, don't care, implicanti

Con 4 variabili la mappa è 4×4: righe ABAB e colonne CDCD, entrambe in Gray. Le adiacenze al bordo ora valgono in tutte le direzioni, e i quattro angoli sono adiacenti tra loro (sul cilindro chiuso formano un quadrato da 4).

Due nomi che mettono ordine nel raggruppare: un implicante primo è un gruppo che non può essere allargato; un implicante primo è essenziale se copre almeno un 1 che nessun altro gruppo copre. Il metodo: prima si prendono tutti gli essenziali, poi si coprono gli 1 rimasti col minor numero di primi. È lo stesso criterio che il minimizzatore del laboratorio applica per te.

📘 Don't care (X)

Righe della tabella che non si verificheranno mai (o il cui valore non interessa): nella mappa si segnano X e ogni X può valere 0 o 1, come conviene (dentro un gruppo se lo allarga, fuori se non serve). Questa libertà può consentire gruppi più grandi e quindi espressioni più semplici, come vedremo nel prossimo progetto.

La minimizzazione POS è la stessa mossa sugli 0: si raggruppano gli 0 (ottenendo F‾\overline{F} in SOP), poi si nega con De Morgan. Utile quando gli 0 sono pochi.

💡 E oltre le 4 variabili?

A 5–6 variabili la mappa diventa un esercizio di pazienza; oltre, impraticabile. Lì il lavoro lo fa l'algoritmo di Quine-McCluskey: stessa idea (fondere termini che differiscono per un bit, scegliere gli essenziali, coprire il resto), ma sistematica e programmabile. Non si fa a mano: basta sapere che esiste, ed è esattamente ciò che gira dentro il laboratorio di questa pagina e lo strumento del corso.

Per le mappe a 4 variabili, coi gruppi colorati e i passaggi mostrati, c'è lo strumento del corso: Mappe di Karnaugh.

5
Capitolo 5

Progetto svolto: i primi in BCD

Il progetto del corso in aula, svolto per intero: la cifra BCD in ingresso (4 bit) è un numero primo? Dalla specifica all'espressione minima, con tutti i passaggi.

Passo 1. La tabella. In BCD i 4 bit ABCDA B C D codificano le cifre 0–9; le combinazioni 10–15 non esistono → don't care. I primi tra 0 e 9 sono 2, 3, 5, 7:

F=Σm(2,3,5,7)+d(10,11,12,13,14,15)F=\Sigma m(2,3,5,7) + d(10,11,12,13,14,15)

Passo 2. La mappa (righe ABAB, colonne CDCD, in Gray; 1 sui mintermini 2, 3, 5, 7; X su 10–15):

AB\CD00011110
000011
010110
11XXXX
1000XX

Passo 3. I gruppi. Bastano due gruppi da 4, entrambi possibili solo grazie alle X. Il primo prende m2 e m3 (riga in alto) e le ripiega sul bordo con m10 e m11 (riga in basso, entrambe X): le righe 00 e 10 sono adiacenti per avvolgimento. Dentro il gruppo AA e DD cambiano, restano B=0B=0 e C=1C=1 → termine B‾ C\overline{B}\,C. Il secondo prende m5 e m7 e le estende alle X m13 e m15: restano B=1B=1 e D=1D=1 → termine B DB\,D.

Passo 4. L'espressione minima:

F=B‾ C+B DF=\overline{B}\,C+B\,D

Da 4 mintermini a 4 letterali l'uno, a due termini da due letterali: è il lavoro delle X, che hanno trasformato gruppi da 2 in gruppi da 4. Entrambi i gruppi sono implicanti primi essenziali (m2 lo copre solo il primo, m5 solo il secondo), e insieme coprono tutti gli 1: il metodo del capitolo 4, applicato per intero. Controlla sulle cifre vere: 2 (00100010) → B‾C=1\overline{B}C=1 ✓; 3, 5, 7 ✓; 9 (10011001) → entrambi i termini a 0 ✓ (il 9 non è primo).

💡 Per approfondire

Il riferimento classico per forme canoniche, Karnaugh e porte è M. Morris Mano, Digital Design (capp. 2–4). E per verificare le tue mappe: lo strumento del corso mostra i gruppi colorati passo per passo.

6
Capitolo 6

Verifica finale

Otto domande sulla lezione. Rispondi a tutte, poi premi «Correggi». Puoi sempre riprovare.

1. La SOP (somma di prodotti) si costruisce dai…
SOP = OR dei mintermini dove l'uscita vale 1. La POS, specularmente, lavora sulle righe con lo 0.
2. Nel mintermine, una riga in cui la variabile vale 0 diventa…
0 → negata, 1 → diretta: così il prodotto vale 1 esattamente su quella riga.
3. Σm(1,3,5) significa…
È la notazione compatta della SOP: i numeri di riga, letti in binario, danno i valori delle variabili.
4. Le colonne della mappa di Karnaugh si ordinano…
Tra celle vicine deve cambiare un solo bit: è ciò che rende il raggruppamento una semplificazione.
5. I gruppi validi in una mappa sono…
1, 2, 4, 8… e prima/ultima colonna (e riga) sono adiacenti: la mappa è chiusa come un cilindro.
6. Un gruppo di 4 celle elimina…
Spariscono le variabili che dentro il gruppo cambiano: 2 celle → 1 variabile, 4 → 2, 8 → 3.
7. Un don't care (X) nella mappa…
Le X possono ampliare i gruppi: nel rilevatore di primi, le X di 10–15 trasformano gruppi da 2 in gruppi da 4.
8. Quando le variabili sono più di 5–6, la minimizzazione si fa…
Stessa idea della mappa, ma sistematica e programmabile: è ciò che gira dentro il laboratorio e lo strumento.

La funzione minima è pronta. Nella prossima lezione la useremo per progettare circuiti con porte logiche, compresi quelli che eseguono somme binarie.

★
Riepilogo

Tutto su una pagina

Forme canoniche

  • Mintermine: AND di tutte le variabili, 1 su una riga
  • SOP: OR dei mintermini (uscita 1) · 0→negata, 1→diretta
  • POS: AND dei maxtermini (uscita 0)
  • Σm(...) e ΠM(...): i numeri di riga

Karnaugh

  • Colonne in Gray: 00, 01, 11, 10
  • Gruppi: potenze di 2, più grandi possibile, meno possibile
  • I bordi si toccano; i 4 angoli sono un gruppo
  • Gruppo di 2ᵏ celle → spariscono k variabili

Raffinamenti

  • Implicante primo: gruppo non allargabile
  • Essenziale: copre un 1 che nessun altro copre → si prende sempre
  • X (don't care): 0 o 1 come conviene
  • POS minima: raggruppa gli 0, poi De Morgan

Oltre le 4 variabili

  • Quine-McCluskey: fondi, trova i primi, copri
  • Lo fa il calcolatore, non la mano
  • Strumento del corso: mappe 4 var coi gruppi colorati

Algebra Booleana · Lezione 3 · Dalla tabella all'espressione minima · buono studio!

Tengo corsi di programmazione, analisi dati e intelligenza artificiale per aziende ed enti di formazione, in aula e da remoto. Scopri come insegno e quali materiali uso a lezione.