Mappe di Karnaugh
Semplifica una funzione booleana vedendo i raggruppamenti, non solo leggendo il risultato.
💡 Come si usa: ogni clic su una casella la fa girare
fra 0, 1 e X
(non mi interessa). L'espressione si ricalcola da sola a ogni
modifica.
I pallini colorati negli angoli delle caselle dicono a
quali gruppi appartiene quella casella: un pallino per gruppo, con lo
stesso colore del termine nell'elenco qui sopra. Una casella con due
pallini sta in due gruppi, ed è normale.
A cosa serve. Una funzione booleana si puo` semplificare con l’algebra, a forza di regole. La mappa di Karnaugh fa la stessa cosa guardandola: si dispongono i valori in una griglia fatta apposta perché due caselle vicine differiscano per una sola variabile, e allora ogni rettangolo di caselle a 1 diventa un pezzo dell’espressione — con dentro solo le variabili che nel rettangolo non cambiano.
Perché le colonne vanno 00, 01, 11, 10. Non è un errore di ordinamento: è il codice Gray. In quest’ordine fra una colonna e la successiva cambia un bit solo, che è esattamente la condizione perché due caselle accostate si possano unire. Con l’ordine naturale (00, 01, 10, 11) fra la seconda e la terza cambierebbero due bit, e il metodo non funzionerebbe.
La mappa è una ciambella. I bordi sono
attaccati: l’ultima colonna è vicina alla prima, e con
quattro variabili anche l’ultima riga è vicina alla prima.
Per questo i quattro angoli formano un gruppo valido.
Provalo: imposta 4 variabili e scrivi B'D'.
Le regole dei gruppi. Un gruppo deve contenere un numero di caselle che sia una potenza di due (1, 2, 4, 8…), dev’essere rettangolare e conviene sempre farlo più grande possibile: ogni raddoppio elimina una variabile dal termine. I gruppi possono sovrapporsi, e spesso devono.
La X vuol dire «non mi interessa». Sono le combinazioni che nel circuito non capitano mai: si possono contare come 1 quando fa comodo per allargare un gruppo, e ignorare quando non serve. Sono un regalo, non un problema.
Far funzionare il codice è una cosa, capirlo un'altra
Percorsi personalizzati di Informatica con un docente di ruolo: reti, logica e programmazione spiegate a partire da come funzionano davvero.