Mappe di Karnaugh: come semplificare una funzione logica
Mentre quasi tutti hanno visto almeno una tabella di verità, le mappe di Karnaugh sono meno note ai più. Fra di loro sono legate, infatti le mappe non sono altro che una rappresentazione grafica alternativa delle tabelle di verità. Partendo dalla tabella di una funzione booleana, questa rappresentazione serve a ridurne la complessità.
Ma senza confonderci troppo le idee, meglio partire dall’inizio.
Mappe di Karnaugh e le funzioni booleane
L’ideatore delle omonime mappe fu Maurice Karnaugh (pronunciato carnò), ingegnere impiegato nel campo delle comunicazioni. Mentre lavorava presso i Bell Laboratories inventò questa nuova rappresentazione grafica per le funzioni logiche. Poche regole per ridurle in forma minima.
Le funzioni di cui si parla sono definire booleane. Sono considerate isomorfe rispetto ai circuiti digitali, ossia ogni circuito può essere espresso tramite questa funzione e viceversa. Per progettare un circuito e per le branche della crittografia e delle telecomunicazioni sono dunque indispensabili.
Se consideriamo 0 e 1 come falso e vero, ossia valori di verità, posso trovare agevolmente il valore della funzione.Basta infatti costruire la corrispondente tabella di verità. Ad ogni combinazione delle variabili andrà assegnato il valore 0 o 1.
Ma quante saranno le combinazioni? Basta guardare il numero di variabili. Una variabile può assumere due valori, quindi in totale saranno 2n combinazioni. Se le tavole di verità di due funzioni booleane sono uguali fra loro, anche le due funzioni sono uguali. Passiamo pra alla mappa di Karnaugh, la forma alternativa.
Disegnare la mappa
La mappa consiste in una griglia rettangolare composta da 2n caselle. In ogni casella viene segnata una combinazione delle variabili, detta anche clausola. Per riuscire a trovare la mappa corrispondente alla funzione booleana comunque è necessario che essa sia nella sua forma disgiuntiva.
Ogni funzione booleana infatti presenta due forme: disgiuntiva (DNF) e conguntiva (CNF). Nella prima le clausole della funzione sono rappresentate tramite congiunzioni letterali, sommate fra loro.
Considerando tre variabili x, y e u ad esempio la DNF di una funzione potrebbe essere xyu + xyū +¯xy.
Prendendo come esempio la forma disgiuntiva di poco fa, si scelgono due gruppi di lettere per costruire la mappa. Ad esempio xy e u: a questo punto si disegna una tabella con otto caselle. Poiché la terza clausola però manca di un letterale occorre riscrivere l’espressione in altro modo. Quindi mantenendo la u e la x negata verrebbe xyu + xyū + ¯xyu – ¯xyū.
Sulle colonne i valori u (ossia 0 e 1) e sulle righe quelli della coppia xy. Quindi due caselle verticali e quattro per ogni riga orizzontale. In cima alla prima riga riporto le combinazioni della coppia: 00, 01, 10 e 11. A questo punto basandosi sulla serie di clausole dell’espressione di prima si possono segnare nella mappa di Karnaugh le celle corrispondenti.
L’espressione xyu + xyū + ¯xyu – ¯xyū corrisponde alle quattro combinazioni 111, 110, 011, 010. Ora è possibile raggruppare i simboli per gruppi: ne vengono due fatti da due combinazioni sovrapposte fra di loro nella griglia.
Trasformare i gruppi
Adesso ogni gruppo formato va trasformato in una congiunzione con un semplice passaggio. Il passaggio prevede di eliminare le variabili (dette anche letterali) se esse assumono in contemporanea sia il valore 0 che il valore 1. Dato che nella mappa appena costruita i gruppi sono fatti da due elementi sovrapposti, bsognerà fare questo passaggio due volte. Ma andiamo per ordine:
- Nel caso del primo gruppo abbiamo 011 e 010. In lettere sono ¯xyu – ¯xyū , poiché il letterale u assume entrambi i valori. Quindi lo si elimina e si tiene la coppia ¯xy, che rimane 01 in tutte e due le combinazioni.
- Nel secondo gruppo sono compresi 111 e 110. Di nuovo ad essere eliminata è u, che assume prima valore 1 nella pricma clausoal e zero nella seconda, essendo negata. La coppia che si salva è 11, cioè xy.
Rispetto all’inizio quindi abbiamo tenuto due clausole su quattro. La mappa di Karnaugh è servita al suo scopo semplificando la forma disgiuntiva della funzione booleana. Ora l’espressione risulta xy + ¯xy. Anche le porte del circuito in cui si può tradurre si sono ridotte diventando solo 4. Due porte AND con una porta OR e una porta NOT.
La tavola di verità a sua volta si ridurrebbe da quattro a tre colonne, considerando solo x e y come variabili. Però i valiri 0 e 1 delle coppie rimaste rimarrebbero tali, anche senza u. Una prova del 9 molto utile si può ricavare così.
