Le Mappe di Karnaugh, sono state ideate per risolvere il problema della riduzione delle espressioni booleane in quanto esse hanno un approccio risolutivo più complesso rispetto alle espressioni dell'algebra ordinaria. Vedremo nel corso di queste lezioni, che lavorare con tale strumento è indispensabile per la cosiddetta sintesi delle reti combinatorie, le quali sono a fondamento della costruzione di un qulunque circuito digitale.

Una mappa di Karnaugh è essenzialmente una matrice, fatta di righe e colonne con alcune proprietà che la contraddistinguono rispetto ad una semplice matrice intesa come tabella di numeri. Consideriamo una funzione booleana a due variabili(ad esempio la ben nota somma logica or). Un modo di rappresentare tale funzione(come abbiamo visto) consiste nel riportare il valore della funzione per tutte le configurazioni di 1 e 0 che possono assumere le variabili indipendenti in una tabella di verità. Questo metodo è chiamato tabulare ed è possibile solo perchè il dominio delle funzioni booleane è finito ovvero {0, 1}! Un altro metodo di rappresentazione delle funzioni booleane è il metodo di Karnaugh. Nella figura è mostrata la rappresentazione della medesima funzione or in una mappa a 2 variabili x ed y. Possiamo subito mettere in evidenza alcune proprietà fondamentali.
  • Definiamo con ordine della mappa il numero di variabili che compaiono in essa. L'ordine di una mappa lo indicheremo con il simbolo \( \partial \). Nell'esempio appena visto l'ordine è 2.
  • Definiamo cardinalità di una mappa, il numero di celle che compongono tale mappa.
Esiste una semplice relazione che lega il numero di celle con l'ordine. Tale relazione non puo che essere una potenza ovvero, la cardinalità è pari a 2 elevato all'ordine.

$${\Large card(M) = 2^{\partial(M)} }$$
$$ \diamond $$