Algebre booleane e progetto logico dei calcolatori digitali/Rappresentazione geometrica delle funzioni booleane e loro minimizzazione

Wikibooks, manuali e libri di testo liberi.
Jump to navigation Jump to search

Parte prima: Algebre booleane

1.1 IntroduzioneAlgebre booleane e progetto logico dei calcolatori digitali/Introduzione
1.2 Sistemi di numerazione, aritmetica binariaAlgebre booleane e progetto logico dei calcolatori digitali/Sistemi di numerazione, aritmetica binaria
1.3 CodiciAlgebre booleane e progetto logico dei calcolatori digitali/Codici
1.4 Teoria della commutazioneAlgebre booleane e progetto logico dei calcolatori digitali/Teoria della commutazione
1.5 Algebra delle classi - Algebra della logicaAlgebre booleane e progetto logico dei calcolatori digitali/Algebra delle classi - Algebra della logica
1.6 Algebre booleaneAlgebre booleane e progetto logico dei calcolatori digitali/Algebre booleane
1.7 Funzioni booleaneAlgebre booleane e progetto logico dei calcolatori digitali/Funzioni booleane
1.8 Rappresentazione geometrica delle funzioni booleane e loro minimizzazioneAlgebre booleane e progetto logico dei calcolatori digitali/Rappresentazione geometrica delle funzioni booleane e loro minimizzazione

Parte seconda: Circuiti logici e calcolatori digitali

2.1 Circuiti logici e di memoriaAlgebre booleane e progetto logico dei calcolatori digitali/Circuiti logici e di memoria
2.2 Circuiti di un calcolatore digitale (a)Algebre booleane e progetto logico dei calcolatori digitali/Circuiti di un calcolatore digitale (a)
2.3 Circuiti di un calcolatore digitale (b)Algebre booleane e progetto logico dei calcolatori digitali/Circuiti di un calcolatore digitale (b)
2.4 Progetto logico di un calcolatore digitaleAlgebre booleane e progetto logico dei calcolatori digitali/Progetto logico di un calcolatore digitale


Diagrammi di Venn[modifica]

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.

Venn diagram of subsets of three sets.png

Ogni insieme esistente nel diagramma di Venn può essere definito mediante una selezione degli insiemi E1...En:

Tavola di definizione di una funzione caratteristica.png

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.

Riunione di insiemi disgiuinti.png

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:

  1. riunione di 4 insiemi disgiunti (8.2a)
  2. 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]

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:

Tavola della verità (8.2)
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]

La tavola della verità della funzione a tre variabili ha 8 righe.

Tabella della verità per una funzione a tre variabili.png

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]

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.

Diagramma di Karnaugh a quattro variabili.png

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.

Diagramma di Karnaugh a sei variabili Diagramma di Karnaugh a sei variabili
Diagramma di Karnaugh a sei variabili
Diagramma di Karnaugh a cinque variabili