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

Algebre booleane e progetto logico dei calcolatori digitali
Copertina Tutti i moduli · Sviluppo
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
Modifica il sommario

## Diagrammi di Venn

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 E$_i$ si associa la funzione caratteristica X$_i$.
Questo comporta la corrispondenza tra operazioni su insiemi e funzioni caratteristiche:
                $E_{i}\cup E_{j}\iff X_{i}+X_{j}$
                $E_{i}\cap E_{j}\iff X_{i}\cdot X_{j}$
                   ${\bar {E}}\iff {\bar {X}}_{i}$
Dati n insiemi E$_1$...E$_n$ rappresentati su un diagramma di Venn, essi definiscono 2$^n$ sottoinsiemi caratterizzati dalla loro inclusione o non inclusione in ciascuno degli insiemi E$_1$...E$_n$.
Ogni insieme esistente nel diagramma di Venn può essere definito mediante una selezione degli insiemi E$_1$...E$_n$:
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:
    $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})$
se ne deduce per X l'espressione:
             $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}$
Ci proponiamo di semplificare le espressioni di E e di X
    $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})=$
          $({\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 ({\bar {E}}_{1}\cap E_{2}\cap E_{3})\cup (E_{1}\cap E_{2}\cap E_{3})=$
          $[(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})=$
          $(E_{2}\cap E_{3})\cup ({\bar {E}}_{1}\cap E_{3})\cup (E_{1}\cap {\bar {E}}_{2}\cap {\bar {E}}_{3})$
    $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}$=
          $(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}$=
          $[(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}$=
          $X_{2}X_{3}+{\bar {X}}_{1}X_{3}+X_{1}{\bar {X}}_{2}{\bar {X}}_{3}$
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:
                $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$
                $X=X_{1}{\bar {X}}_{2}{\bar {X}}_{3}+X_{2}X_{3}+{\bar {X}}_{1}X_{3}$
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:
                            $X=A+A\cdot B$
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

La tavola della verità della funzione $X=(A+{\bar {B}})C$ 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. 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

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.
| Diagramma di Karnaugh a sei variabili | Diagramma di Karnaugh a cinque variabili |