Algebre booleane e progetto logico dei calcolatori digitali/Rappresentazione geometrica delle funzioni booleane e loro minimizzazione: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
allineo |
refusi e modifiche minori |
||
Riga 1:
{{Algebre booleane e progetto logico dei calcolatori digitali}}
[[Categoria:Algebre booleane e progetto logico dei calcolatori digitali|Rappresentazione geometrica delle funzioni booleane e loro minimizzazione]]▼
{{Avanzamento|100%|24 settembre 2016}}▼
== Diagrammi di Venn ==
I diagrammi di Venn sono una rappresentazione grafica delle relazioni tra insiemi,
Questo comporta la corrispondenza tra operazioni su insiemi e funzioni caratteristiche:
:::::'''<math>E_i\cup E_j\iff X_i+ X_j</math>'''<br/>▼
:::::<math>E_i\cap E_j\iff X_i\cdot X_j</math><br/>▼
:::::
Dati '''n''' insiemi '''E<sub>1</sub>...E<sub>n</sub>''' rappresentati su un diagramma di Venn, essi definiscono 2<sup>n</sup> sottoinsiemi caratterizzati dalla loro '''inclusione''' o '''non inclusione''' in ciascuno degli insiemi '''E<sub>1</sub>...E<sub>n</sub>'''.<br/>▼
▲Dati '''n''' insiemi '''E<sub>1</sub>...E<sub>n</sub>''' rappresentati su un diagramma di Venn, essi definiscono 2<sup>n</sup> sottoinsiemi caratterizzati dalla loro '''inclusione''' o '''non inclusione''' in ciascuno degli insiemi '''E<sub>1</sub>...E<sub>n</sub>'''.
[[File:Venn diagram of subsets of three sets.png]]
Ogni insieme esistente nel diagramma di Venn può essere definito mediante una selezione degli insiemi '''E<sub>1</sub>...E<sub>n</sub>''':
[[File: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).
[[File:Riunione di insiemi disgiuinti.png]]
▲La funzione caratteristica '''E''' definita nella tavola (8.1) è quindi rappresentata dall'insieme E dal diagramma di Wenn (8.2).<br/>
▲E è dato dagli insiemi colorati.<br/>
L'insieme '''E''' può essere anche definito mediante una espressione:<br/>▼
:<math>E=(\bar E_1\cap \bar E_2\cap E_3)\cup (\bar E_1\cap E_2\cap E_3)\cup (E_1\cap \bar E_2\cap \bar E_3)\cup (E_1\cap E_2\cap E_3)</math
se ne deduce per '''X''' l'espressione:<br/>▼
::::<math>X=\bar X_1\bar X_2 X_3+\bar X_1 X_2 X_3+X_1\bar X_2\bar X_3+X_1 X_2 X_3</math><br/>▼
Ci proponiamo di semplificare le espressioni di '''E''' e di '''X'''
:<math>E=(\bar E_1\cap \bar E_2\cap E_3)\cup (\bar E_1\cap E_2\cap E_3)\cup (E_1\cap \bar E_2\cap \bar E_3)\cup (E_1\cap E_2\cap E_3)=</math><br/>▼
:::<math>[(E_1\cap \bar E_1)\cup (E_2\cap E_3)]\cup [\bar E_1\cap ( E_2\cup \bar E_2)\cap E_3]\cup (E_1\cap \bar E_2\cap \bar E_3)=</math><Br/>▼
▲:::<math>
▲:::<math>[(E_1\cap \bar E_1)\cup (E_2\cap E_3)]\cup [\bar E_1\cap ( E_2\cup \bar E_2)\cap E_3]\cup (E_1\cap \bar E_2\cap \bar E_3)=</math
:::<math>(E_2\cap E_3)\cup (\bar E_1\cap E_3)\cup (E_1\cap \bar E_2\cap \bar E_3)</math>
:::<math>(X_1 X_2 X_3+\bar X_1 X_2 X_3)+(\bar X_1 \bar X_2 X_3+\bar X_1 X_2 X_3)+X_1 \bar X_2 \bar X_3</math>=
▲:<math>X=\bar X_1 \bar X_2 X_3+\bar X_1 X_2 X_3+X_1 \bar X_2 \bar X_3+X_1 X_2 X_3</math>=<br/>
▲:::<math>(X_1 X_2 X_3+\bar X_1 X_2 X_3)+(\bar X_1 \bar X_2 X_3+\bar X_1 X_2 X_3)+X_1 \bar X_2 \bar X_3</math>=<br/>
▲:::<math>[(X_1 +\bar X_1)X_2 X_3]+[\bar X_1 (X_2+\bar X_2)X_3]X_1 \bar X_2 \bar X_3</math>=<br/>
:::<math>X_2 X_3+\bar X_1 X_3+X_1 \bar X_2 \bar X_3</math>
Ma la semplificazione si può ottenere anche osservando che l'insieme '''E''' può essere ottenuto come:
::1)riunione di 4 insiemi disgiunti (8.2a)<br/>▼
Considerando quindi semplicemente il diagramma di Wenn si ottiene:
:::::<math>E=(E_1\cap\bar E_2\cap\bar E_3)\cup(E_2\cap E_3)\cup(\bar E_1\cap E_3)\ \ \ \ \ e\ di\ conseguenza</math
:::::<math>X=X_1\bar X_2\bar X_3+X_2 X_3+\bar X_1 X_3</math>
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 ==
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:<br/>▼
▲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:
[[File:Tavola della verità (8.2).png|
:::::::::<math>X=A+A\cdot B</math><br/>▼
La tavola (8.2) della verità di questa funzione ha quattro righe, corrispondenti alle 4 possibili combinazioni dei valori assunti dalle variabili.
[[File:Diagramma di Karnaugh di due variabili.png|right]]
Il diagramma di Karnaugh corrispondente
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 ===
[[File:Tabella della verità per una funzione a tre variabili.png|right]]
[[File:Diagramma di Karnaugh per una funzione a tre variabili.png|right]]
La tavola della verità della funzione <math>X=(A+\bar B)C</math> a tre variabili ha '''8''' righe.
Il corrispondente diagramma di Karnaugh avrà '''8''' caselle, ognuna associata ad una delle '''8''' combinazioni possibili, poste su due colonne e '''4''' righe. Ad 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:
▲Il corrispondente diagramma di Karnaugh avrà '''8''' caselle, ognuna associata ad una delle '''8''' combinazioni possibili, poste su due colonne e '''4''' righe. Ad 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:<br/>
▲::::::::::'''0 0''', '''0 1''', '''1 1''', '''1 0'''<br/>
▲Notiamo che nella tavola della verità le combinazioni sono:<br/>
▲::::::::::'''0 0''', '''0 1''', '''1 0''', '''1 1'''<br/>
▲mentre nei diagrammi di Karnaugh avremo le ultime due cifre invertite (vedere tabella 8.4).<br/>
Poiché ad 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.
Line 92 ⟶ 108:
[[File:Diagramma di Karnaugh a quattro variabili.png|right]]
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 cui proposta non è l'unica ma quella di uso più corrente.
[[File:Diagramma di Karnaugh a sei vbariabili.png|right]]<br/>▼
[[
▲[[Categoria:Algebre booleane e progetto logico dei calcolatori digitali|Rappresentazione geometrica delle funzioni booleane e loro minimizzazione]]
▲{{Avanzamento|100%|24 settembre 2016}}
| |||