XKCD: Karnaugh

Amore e analisi dei circuiti, finalmente mano nella mano.

L’amore è sintetizzabile come un circuito logico?

Una mappa di Karnaugh serve a semplificare una espressione logica che rappresenta un circuito logico.
I circuiti logici sono composti da porte logiche che idealizzano le funzioni booleane (N)AND, (N)OR, X(N)OR, NOT: dati due bit -0 o 1- in ingresso restituiscono un valore binario a seconda della funzione secono la loro tabella di verità.

Mettendo più porte logiche assieme si va a formare un circuito che emula il funzionamento di una particolare espressione composta dalle operazioni logiche fondamentali. Spesso pero’ queste funzioni possono venire semplificate per eliminare operazioni e variabili che non influiscono sul risultato finale: uno dei metodi usati, per piccoli numeri di variabili -funziona in modo semplice fino a 4 variabili- è la mappa di Karnaugh.

Prendiamo l’esempio in figura: la funzione di partenza è l’Output in alto e il corrispondente circuito logico è quello sulla sinistra (composto solo da NOT, AND e un OR), ci sono tre variabili in gioco (A,B,C). Si costruisce una tabella a due entrate: le righe corrispondono ai possibili valori di A, le colonne ai possibili valori di B e C -in questo caso vediamo anche che quando ci sono due variabili vanno combinate in ordine 00, 01, 11, 10- e si guarda la tabella di verità della funzione proposta -non in figura- scrivendo per gli input il risultato della funzione nella casella (ad esempio per A=0, B=1, C=1 la funzione restituisce 1).
Una volta completa, andiamo a dare una occhiata alla tabella e raccogliamo gli uno in gruppi che hanno in comune lo stesso valore per una determinata variabile: nell’esempio col cerchio a linea piena sono raccolti i due uno che hanno A e C a 1, a linea tratteggiata i due uno che hanno A e B a uno e a linea puntinata i due uno che hanno A e C a uno. Questi gruppi verranno scritti con un AND tra le variabili del gruppo e con un OR dei gruppi.
Il risultato finale è quello che si vede qua sotto.

Vignetta originale su XKCD.