Algebre booleane e progetto logico dei calcolatori digitali/Rappresentazione geometrica delle funzioni booleane e loro minimizzazione
Diagrammi di Venn
[modifica | modifica sorgente]I diagrammi di Venn sono una rappresentazione grafica delle relazioni tra insiemi, e in particolare delle operazioni di unione, intersezione e complementazione. Si è visto inoltre che ogni algebra di insiemi con le operazioni sopra citate è un'algebra di Boole. Ne segue che questi diagrammi di Venn possono essere utilizzati per rappresentare le operazioni sulle funzioni di commutazione che formano esse stesse un'algebra di Boole. Per fare ciò è sufficiente utilizzare la seguente corrispondenza tra gli insiemi e le funzioni booleane: ad ogni insieme Ei si associa la funzione caratteristica Xi.
Questo comporta la corrispondenza tra operazioni su insiemi e funzioni caratteristiche:
Dati n insiemi E1...En rappresentati su un diagramma di Venn, essi definiscono 2n sottoinsiemi caratterizzati dalla loro inclusione o non inclusione in ciascuno degli insiemi E1...En.
Ogni insieme esistente nel diagramma di Venn può essere definito mediante una selezione degli insiemi E1...En:
La funzione caratteristica E definita nella tavola (8.1) è quindi rappresentata dall'insieme E dal diagramma di Wenn (8.2).
E è dato dagli insiemi colorati.
L'insieme E può essere anche definito mediante una espressione:
se ne deduce per X l'espressione:
Ci proponiamo di semplificare le espressioni di E e di X
- =
- =
- =
Ma la semplificazione si può ottenere anche osservando che l'insieme E può essere ottenuto come:
- riunione di 4 insiemi disgiunti (8.2a)
- riunione di 3 insiemi disgiunti (8.2b)
Considerando quindi semplicemente il diagramma di Wenn si ottiene:
espressioni ottenute in precedenza in via algebrica.
Riassumendo, il digramma di Wenn permette di sostituire le operazioni algebriche con l'esame delle configurazioni geometriche, e questo metodo può essere utilizzato soprattutto per la semplificazione delle espressioni.
Diagrammi di Karnaugh
[modifica | modifica sorgente]Esporremo ora il metodo per la semplificazione delle funzioni dovuto a Karnaugh. Tale metodo ci permetterà di eseguire le minimizzazioni con una certa speditezza, ed è conveniente applicarlo a funzioni con al massimo 6 variabili.
Per poter applicare questo procedimento, è necessario conoscere le rappresentazioni delle funzioni col metodo di Karnaugh. Rappresentazioni che permettono di visualizzare una funzione sotto forma di superficie e sono una applicazione della teoria degli insiemi-Nelle tavole della verità abbiamo visto che, nelle colonne delle variabili, ad ogni riga corrisponde un valore possibile della variabile presa in considerazione.
Nei diagrammi di Karnaugh, anziché far corrispondere una riga, per ogni valore della variabile, si fa corrispondere una superficie delimitata da un quadretto. Costruiamo per esempio il diagramma di Karnaugh per una funzione X dipendente da due variabili:
![](http://upload.wikimedia.org/wikipedia/commons/thumb/4/47/Tavola_della_verit%C3%A0_%288.2%29.png/220px-Tavola_della_verit%C3%A0_%288.2%29.png)
![](http://upload.wikimedia.org/wikipedia/commons/a/ac/Diagramma_di_Karnaugh_di_due_variabili.png)
La tavola (8.2) della verità di questa funzione ha quattro righe, corrispondenti alle 4 possibili combinazioni dei valori assunti dalle variabili.
Il diagramma di Karnaugh corrispondente avrà due righe e 4 caselle, essendo i valori di A (prima variabile) posti sopra le caselle orizzontalmente ed i valori della seconda variabile posti a fianco in verticale.
Nei quadretti interni distribuiremo i valori assunti dalla funzione. La tavola della verità (8.2) avrà il diagramma affiancato.
I diagrammi di Karnaugh per tre, quattro o più variabili
[modifica | modifica sorgente]La tavola della verità della funzione a tre variabili ha 8 righe.
![](http://upload.wikimedia.org/wikipedia/commons/a/a8/Diagramma_di_Karnaugh_per_una_funzione_a_tre_variabili.png)
Il corrispondente diagramma di Karnaugh avrà 8 caselle, ognuna associata ad una delle 8 combinazioni possibili, poste su due colonne e 4 righe. A una variabile si assegnano le due colonne, una per il valore 0 l'altra per il valore 1; alle altre variabili si fanno corrispondere le 4 righe, ognuna relativa alle combinazioni:
- 0 0, 0 1, 1 1, 1 0
Notiamo che nella tavola della verità le combinazioni sono:
- 0 0, 0 1, 1 0, 1 1
mentre nei diagrammi di Karnaugh avremo le ultime due cifre invertite (vedere tabella 8.4).
Poiché a ogni casella corrisponde il valore che la funzione assume per i particolari valori delle variabili, è stato scelto opportunamente l'ordine delle righe per fare in modo che, passando da un quadratino al successivo, si abbia il cambiamento di una sola variabile.
Diagramma di Karnaugh a quattro variabili
[modifica | modifica sorgente]Una tabella della verità a quattro variabili ha 16 righe corrispondenti a tutte le possibili combinazioni. Il Diagramma di Karnaugh avrà 16 caselle, disposte su quattro righe e quattro colonne. Si assegneranno le quattro colonne alle possibili combinazioni delle prime due variabili e le quattro righe alle combinazioni 00,01, 11, 10 delle altre due.
Se le variabili fossero 5 o 6 si userebbero dei Diagrammi multipli: la forma qui proposta non è l'unica ma quella di uso più corrente.