Sintesi di una funzione logica con le mappe di Karnaugh

    

Assegnata una funzione logica, la mappa di Karnaugh corrispondente non è altro che una rappresentazione grafica della tabella della verità della stessa funzione.

L'operazione più conveniente consiste nel marcare le variabili di ingresso con degli 1 quando esse non sono negate e con degli 0 quando esse sono negate, come indicato sotto:

Si riportano degli (1) in corrispondenza delle combinazioni delle variabili di ingresso evidenziate nella funzione.La tabella della verità è una sintesi del comportamento della variabile di uscita Y in corrispondenza di tutti i possibili valori delle variabili di ingresso. Dalla tabella della verità di una funzione si può subito ricavare la corrispondente mappa di Karnaugh.

La mappa di Karnaugh di una funzione ad n variabili di ingresso consiste in un rettangolo di 2ⁿ caselle, dove ogni casella corrisponde ad uno dei possibili stati (combinazioni) delle variabili di ingresso con la caratteristica che passando da una casella all'altra in ogni direzione (ma non in diagonale) cambia una sola delle variabili. Debbono essere considerate adiacenti anche le caselle di estremità di una riga o di una colonna, come se la mappa fosse disegnata su una superficie chiusa su se stessa. In ognuna delle caselle viene posto il valore assunto dalla funzione (variabile Y) booleana per quello stato (per quella combinazione delle variabili di ingresso).

Le regole che si seguono per la semplificazione sono:

1 Bisogna individuare il minor numero di gruppi (che copre tutti gli 1 della mappa).

2 Ciascun gruppo deve contenere il maggior numero di 1 adiacenti (il numero di 1 che costituisce un gruppo deve formare una potenza del 2, si scelgono perciò gruppi da due 1 o da quattro 1 etc..).

3 Come si è detto sono considerabili adiacenti le caselle di estremità.

4 Eventuali 1 isolati costituiscono un gruppo e debbono essere riportati integralmente.

5 Da ogni gruppo si estrae un termine che contiene le variabili di ingresso che non variano passando da una casella all’altra del raggruppamento stesso, ciascuna variabile sarà in forma vera o negata a secondo se vale 1 o 0 nel raggruppamento.

6 La funzione logica minimizzata sarà data dalla somma logica dei termini estratti dalla mappa.

Ad es. per il caso precedente:

Come si nota il minimo numero di gruppi è due, ciascun gruppo contiene tanti 1 sempre in ragione delle potenze del 2 (cioè 4 e 2 uno) nel primo gruppo orizzontale passando da una casella all’altra l ’unica variabile che non cambia è la C che rimane impostata a 0 per cui verrà estratta come termine C.

Nel gruppo verticale passando da una casella all’altra le nice variabili che non cambiano sono la A che rimane impostata a 0 (A) e la B che rimane impostata a 1 (B); verrà dunque estratto il termine AB; in definitiva la funzione semplificata sarà:



Supponiamo ora di dover semplificare una funzione con 4 variabili, la rappresentazione usuale della mappa sarà la seguente:

In questo caso si evidenziano le due celle non contigue (disgiunte di estremità) sulla seconda riga da cui viene estratto il termine
B C D e il termine isolato in basso a sinistra che deve essere riportato integralmente. Nella colonna verticale passando da una casella all’altra non cambiano le variabili AB che rimangono impostate a 1 (AB) mentre il gruppo da 4 quadrato non vede cambiare le Variabili A che rimane impostata a 1 e D che ugualmente rimane a 1 (AD).
La funzione risultante sarà:

Condizioni di indifferenza