Mappe di Karnaugh

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.

Indice
Supera il Test di ingresso
Preparati alle prove di ammissione con i libri e corsi UnidTest

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.

Per definizione, una funzione booleana di n variabili è una funzione con valori booleani sia nel dominio che nel codominio. f:Bn→B. Non c’è un limite al numero delle variabili; esse però assumono solo valori booleani, ossia 0 e 1.
 

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ì.

Mappe di Karnaugh: semplificare ancora non sarebbe possibile?

Abbiamo usato il “filtro”di Karnaugh per rendere più semplice la funzione, ma con una regola di semplificazione si può fare di meglio. Così finalmente si arriverà alla forma minimale, non più riducibile. Per procedere basta ricordarsi del criterio usato nei gruppi definiti grazie alla mappa. Eliminare cioè le variabili che assumono entrambi i valori possibili.
 
Riprendendo in mano la forma residua xy + ¯xy si nota subito che ora il letterale a dare problemi è x. Appare prima in forma diretta e poi in forma negata. Ergo, non ci serve più. Togliendola resta un solo letterale, y, che mantiene il valore 1. La forma adesso  è y + y. Ma secondo un’altra regola dell’algebra booleana basta tenere y.
 
Usando la mappa non è stato possibile arrivare direttamente alla forma “y“. La semplificazione di Karnaugh infatti è limitata da quella che è la scelta dei gruppi che si vengono a formare. Questo dettaglio va sempre tenuto presente quando la si usa.
Entra all'università con UnidTest
Corsi in presenza
Scopri i corsi in 45 città e in diretta eLearning
Preparati online
Scopri i corsi on demand disponibili 24 ore su 24
Piattaforma Genius
Migliora le tue performance con la nostra piattaforma online
Condividi su
Facebook
LinkedIn
Email
WhatsApp
Scritto da
Categorie
Iscriviti alla newsletter

Ricevi i nostri migliori articoli, contenuti gratuiti, offerte riservate e tanto altro!

google news

Ricevi le nostre notizie da Google News

×

Inserisci i tuoi dati per scaricare il contenuto:

Torna in alto