Le mappe di Karnaugh (K-map) sono un metodo grafico che permette di costruire semplicemente la forma minima di una funzione logica come somma di prodotti (nota 1). Pur essendo un metodo piuttosto "antico" ed adatto solo per tabelle con massimo quattro ingressi (nota 2) è ancora utilizzato.
Il metodo parte dalla scrittura della tabella di verità.
Le uscite della tabella vanno disposte in una griglia 4x4 oppure 4x2 oppure 2x2, con un numero di celle pari al numero di righe della tabella di verità; sui lati della griglia sono scritti i valori delle variabili di ingresso singolarmente (0 o 1) oppure a coppie, evitando il cambiamento contemporaneo di più bit tra righe o colonne successive (sequenza obbligatoria: 00, 01, 11, 10)
Le celle che contengono "1" devono essere raccolte in gruppi rettangolari contenenti 1, 2, 4 oppure 8 valori. Tali gruppi devono essere il più grande possibile e nel loro insieme coprire tutti gli "1" presenti nella griglia. Un gruppo può comprendere anche elementi della prima e dell'ultima riga o colonna (la mappa va immagina "cilindrica", sia in orizzontale che in verticale)
Ciascun raggruppamento genera il prodotto delle variabili che non cambiano all'interno del raggruppamento stesso, prese in forma normale oppure negata a seconda che il loro valore scritto sui bordi della cella sia "1" oppure "0".
Occorre infine scrivere una funzione booleana che somma i prodotti trovati al punto precedente
Consideriamo la seguente tabella di verità.
A | B | C | Q |
0 | 0 | 0 | 0 |
0 | 0 | 1 | 0 |
0 | 1 | 0 | 0 |
0 | 1 | 1 | 1 |
1 | 0 | 0 | 0 |
1 | 0 | 1 | 1 |
1 | 1 | 0 | 1 |
1 | 1 | 1 | 1 |
Usando la prima forma canonica tale tabella produce la funzione Q = (A·B·C) + (A·B·C) + (A·B·C) + (A·B·C).
Costruiamo la K-map, formata da 8 celle disposte 4x2, ponendo le combinazioni A e B sulle righe e C sulle colonne (nota 3):
Si noti l'ordine assunto dalla coppia di variabili A e B: è obbligatorio!
Raccogliamo tutti gli "1". Nell'esempio servono tre raggruppamenti di due 1 ciascuno, di seguito evidenziati:
La funzione semplificata è costituita da Q = (B·C) + (A·C) + (A·B), evidentemente più semplice della precedente, ma ad essa equivalente.
Consideriamo la seguente tabella di verità:
A | B | C | D | Q |
0 | 0 | 0 | 0 | 0 |
0 | 0 | 0 | 1 | 0 |
0 | 0 | 1 | 0 | 0 |
0 | 0 | 1 | 1 | 1 |
0 | 1 | 0 | 0 | 0 |
0 | 1 | 0 | 1 | 1 |
0 | 1 | 1 | 0 | 1 |
0 | 1 | 1 | 1 | 1 |
1 | 0 | 0 | 0 | 0 |
1 | 0 | 0 | 1 | 0 |
1 | 0 | 1 | 0 | 0 |
1 | 0 | 1 | 1 | 1 |
1 | 1 | 0 | 0 | 0 |
1 | 1 | 0 | 1 | 1 |
1 | 1 | 1 | 0 | 0 |
1 | 1 | 1 | 1 | 1 |
Attività autonoma: scrivere la prima forma canonica della tabella (lungo...).
Costruiamo la K-map corrispondente:
Si noti l'ordine assunto dalla coppia di variabili AB sulle righe e CD sulle colonne.
Raccogliamo gli "1". Nell'esempio sono presenti due raggruppamenti di quattro "1" ed uno di due "1", di seguito evidenziati:
La funzione semplificata è costituita da Q = (C·D) + (B·D) + (A·B·C), evidentemente più semplice della precedente, ma ad essa equivalente.
Consideriamo la seguente tabella di verità:
A | B | C | D | Q |
0 | 0 | 0 | 0 | 1 |
0 | 0 | 0 | 1 | 1 |
0 | 0 | 1 | 0 | 1 |
0 | 0 | 1 | 1 | 1 |
0 | 1 | 0 | 0 | 1 |
0 | 1 | 0 | 1 | 1 |
0 | 1 | 1 | 0 | 1 |
0 | 1 | 1 | 1 | 1 |
1 | 0 | 0 | 0 | 0 |
1 | 0 | 0 | 1 | 0 |
1 | 0 | 1 | 0 | 0 |
1 | 0 | 1 | 1 | 1 |
1 | 1 | 0 | 0 | 0 |
1 | 1 | 0 | 1 | 0 |
1 | 1 | 1 | 0 | 0 |
1 | 1 | 1 | 1 | 0 |
Attività: scrivere la prima forma canonica della tabella
Costruiamo la K-map corrispondente:
CD=00 | CD=01 | CD=11 | CD=10 | |
AB=00 | 1 | 1 | 1 | 1 |
AB=01 | 1 | 1 | 1 | 1 |
AB=11 | 0 | 1 | 0 | 0 |
AB=10 | 0 | 0 | 1 | 0 |
Si noti l'ordine assunto dalla coppia di variabili AB sulle righe e CD sulle colonne.
Raccogliamo gli "1". Nell'esempio sono presenti un raggruppamento di otto "1" ed uno di due "1", quest'ultimo tra la prima e l'ultima riga, essendo la mappa "cilindrica".
La funzione semplificata è costituita da Q = (A) + (B·C·D), evidentemente più semplice della precedente, ma ad essa equivalente.
Consideriamo la seguente K-map:
CD=00 | CD=01 | CD=11 | CD=10 | |
AB=00 | 0 | 1 | 0 | 0 |
AB=01 | 0 | 1 | 0 | 1 |
AB=11 | 0 | 1 | 0 | 0 |
AB=10 | 1 | 1 | 0 | 0 |
Possiamo individuare:
Consideriamo la seguente K-map:
CD=00 | CD=01 | CD=11 | CD=10 | |
AB=00 | 1 | 1 | 0 | 0 |
AB=01 | 1 | 1 | 0 | 1 |
AB=11 | 0 | 0 | 0 | 0 |
AB=10 | 1 | 0 | 0 | 1 |
Possiamo individuare:
Aprile 2013, Maurice Karnaugh incontra alcuni studenti della Saunders High School. Autore della fotografia e copyright non noti.
Pagina creata nel gennaio 2024
Ultima modifica: 29 gennaio 2025
Appunti scolastici - Versione 0.1029 - Gennaio 2025
Copyright 2012-2025, Vincenzo Villa (https://www.vincenzov.net)
Creative Commons | Attribution-ShareAlike 4.0 International (CC BY-SA 4.0)