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.
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.
Mintermini, maxtermini, SOP e POS
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 . I mintermini: , , . SOP:
(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.
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 è , «somma dei mintermini 1, 3, 4», e la sua POS è . È 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.
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.
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 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 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.
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.
Clicca le celle per mettere gli 1 (righe = , colonne = in codice Gray). La forma minima viene calcolata dal vivo. Ora gli 1 sono dove : la minima è semplicemente (quattro mintermini, una lettera).
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.
Quattro variabili, don't care, implicanti
Con 4 variabili la mappa è 4×4: righe e colonne , 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.
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 in SOP), poi si nega con De Morgan. Utile quando gli 0 sono pochi.
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.
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 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:
Passo 2. La mappa (righe , colonne , in Gray; 1 sui mintermini 2, 3, 5, 7; X su 10–15):
| AB\CD | 00 | 01 | 11 | 10 |
|---|---|---|---|---|
| 00 | 0 | 0 | 1 | 1 |
| 01 | 0 | 1 | 1 | 0 |
| 11 | X | X | X | X |
| 10 | 0 | 0 | X | X |
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 e cambiano, restano e → termine . Il secondo prende m5 e m7 e le estende alle X m13 e m15: restano e → termine .
Passo 4. L'espressione minima:
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 () → ✓; 3, 5, 7 ✓; 9 () → entrambi i termini a 0 ✓ (il 9 non è primo).
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.
Verifica finale
Otto domande sulla lezione. Rispondi a tutte, poi premi «Correggi». Puoi sempre riprovare.
La funzione minima è pronta. Nella prossima lezione la useremo per progettare circuiti con porte logiche, compresi quelli che eseguono somme binarie.
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!
Il tuo riscontro
Com’è andata questa lezione?
Dimmi cosa è chiaro e dove la spiegazione può migliorare.