Strumenti Utente

Strumenti Sito


sezione_3c

3C - Algebra di Boole e circuiti combinatori

1 Variabili logiche e circuiti combinatori

Una variabile logica può assumere solo due valori, lo stato logico 0 o lo stato logico 1 (per una tensione il livello alto H o basso L).

In un circuito combinatorio, con variabili logiche in ingresso e uscita, il valore delle uscite dipende solo da quello degli ingressi.

La funzione logica svolta da un circuito combinatorio descrive il legame tra ingressi e uscite. Le funzioni logiche sono esprimibili:

  • con una tabella della verità, che riporta il valore delle uscite in corrispondenza di tutte le combinazioni degli ingressi, ordinati secondo la numerazione binaria
  • in forma sintetica con una espressione logica

2 Algebra di Boole

L'algebra di Boole è nata nel 1800 per risolvere problemi logici. Nel secolo successivo è stata applicata all'elettronica digitale facendo corrispondere alle variabili booleane, che possono essere vere o false, delle variabili logiche, che valgono 0 o 1.

Gli assiomi sui quali si fonda l'algebra di Boole sono i seguenti:

assioma duale
`1*1=1``0+0=0`
`1*0=0``0+1=1`
`0*1=0``1+0=1`
`0*0=0``1+1=1`
`bar 1 = 0``bar 0 = 1`

Gli operatori logici (non aritmetici!) che compaiono sono:

  • il prodotto logico AND
  • la somma logica OR
  • la negazione o complementazione logica NOT

Con gli operatori logici è possibile definire una espressione logica di una funzione (al posto della tabella della verità). Negli assiomi, e più in generale per ogni espressione logica, vale il principio della dualità: per ogni espressione logica vera anche la sua duale, ottenuta scambiando AND con OR e 0 con 1, risulta vera.

La figura 2 è particolarmente interessante perché mostra una interpretazione circuitale degli operatori logici appena definiti (per gli interruttori 0 corrisponde ad aperto e 1 a chiuso, per la lampada 0 a spento e 1 ad acceso).

Proprietà e teoremi dell'algebra di Boole

proprietà enunciato duale
commutativa`A+B=B+A``A*B=B*A`
associativa`(A+B)+C=A+(B+C)``(A*B)*C=A*(B*C)`
distributiva`A*(B+C)=(A*B)+(A*C)``A+(B*C)=(A+B)*(A+C)`1)
teorema annullamento`A+1=1``A*0=0`
teorema identità`A+0=A``A*1=A`
teorema complementi`A+bar A=1``A* bar A = 0`
teorema idempotenza`A+ A = A``A*A=A`
primo teorema assorbimento`A+(A*B)=A``A*(A+B)=A`
secondo teorema assorbimento`A+(bar A *B)=A+B``A*(bar A +B)= A*B`
teorema di De Morgan2)`bar(A+B)=bar A * bar B``bar (A*B)=bar A + bar B`

NB Quando si usano più operatori logici le precedenze sono: NOT → AND → OR

Extra

  • problema svolto 6 (espressioni logiche da minimizzare)

3 Funzioni logiche primarie

Le funzioni logiche AND, OR e NOT sono dette primarie perché combinandole è possibile realizzare qualsiasi altra funzione logica. Ognuna di esse ha un simbolo, una tabella della verità e una espressione logica.

Osserviamo che:

  • tranne che per la porta NOT le funzioni logiche possono avere più di due ingressi
  • per ogni funzione sono definiti dei simboli MIL e ANSI/IEEE3); i primi sono i più utilizzati

Funzione logica AND

La funzione logica AND - prodotto logico - si rappresenta col simbolo di figura 3a. La sua tabella della verità - figura 3c - mostra come l'uscita valga 1 solo se tutti gli ingressi valgono 1.

Funzione logica OR

La funzione logica OR - somma logica - si rappresenta col simbolo di figura 5a. La sua tabella della verità - figura 5c - mostra come l'uscita valga 1 se almeno uno degli ingressi vale 1.

Funzione logica NOT

La funzione logica NOT - negazione o complementazione logica - si rappresenta col simbolo di figura 7a. La sua tabella della verità - figura 7c - mostra come l'uscita corrisponda al valore dell'ingresso negato.

Il problema della minimizzazione

Una funzione logica può essere realizzata con soluzioni circuiti diverse tra loro. La soluzione migliore è quella che usa meno funzioni logiche possibili. Il problema della minimizzazione di una funzione logica consiste proprio nel trovare la soluzione circuitale che fa uso del numero minore di porte logiche. Si può minimizzare una funzione

  • per tentativi, applicando con le regole dell'algebra di Boole
  • con un procedimento meccanico, usando le mappe di Karnaugh

4 Altre funzioni logiche

Dalle funzioni logiche primarie si ricavano altre funzioni utili.

La funzione NAND

La funzione logica NAND - AND negato - si rappresenta col simbolo di figura 10a. La sua tabella della verità - figura 10c - mostra come l'uscita valga 0 solo se tutti gli ingressi valgono 1. Il cerchio che segue il simbolo della porta AND rappresenta la negazione.

La funzione NOR

La funzione logica NOR - OR negato - si rappresenta col simbolo di figura 11a. La sua tabella della verità - figura 11c - mostra come l'uscita valga 1 solo se tutti gli ingressi valgono 0.

La funzione OR esclusivo (EX-OR)

La funzione logica EX-OR (anche indicata come XOR) si rappresenta col simbolo di figura 12a. La sua tabella della verità - figura 12c - mostra come l'uscita valga 1 se è dispari il numero di 1 in ingresso.

Osservazioni:

  • nel caso di due soli ingressi l'uscita vale 1 se i due ingressi sono diversi tra loro
  • esclusa l'ultima riga la funzione EX-OR corrisponde alla OR
  • l'operatore EX-OR è indicato dal simbolo ⊕

La funzione EX-NOR

La funzione logica EX-NOR (indicata anche con XNOR) corrisponde alla funzione EX-OR negata e si rappresenta col simbolo di figura 13a. La sua tabella della verità - figura 13c - mostra come l'uscita valga 1 se è pari il numero di 1 in ingresso. Nel caso di due soli ingressi l'uscita vale 1 se gli ingressi sono uguali tra loro.

Extra

  • non solo teoria 2:circuito che somma due numeri binari da due bit

5 Gruppi universali

I gruppi universali permettono di realizzare qualunque funzione logica. Sono un gruppo universale le funzioni primarie - AND, OR e NOT - ma anche la sola funzione NAND e la sola funzione NOR.

Verifica dell'universalità dei NAND

La figura 15 mostra come collegando insieme i due ingressi di una porta si ottiene la funzione NOT.

La fiugra 16 mostra come ottenere la funzione AND facendo seguire alla NAND la funzione NOT realizzata come in figura 15.

La funzione OR è più difficile da ottenere ma si dimostra, utilizzando il teorema di de Morgan che:

`A+B =bar (bar (A+B))=bar ( bar A*bar B )`

che porta alla soluzione circuitale di figura 17.

Verifica dell'universalità dei NOR

La figura 18 mostra come collegando insieme i due ingressi di una porta si ottiene la funzione NOT.

La funzione OR è allora ottenibile facendo seguire alla NOR la funzione NOT realizzata come in figura 18, come in figura 19.

La funzione AND si ottiene con un procedimento simile a quanto visto per realizzare la funzione OR con le NAND, come mostrato in figura 20.

Gli esempi 6 e 7 mostrano come realizzare una funzione logica utilizzando un solo tipo di porte logiche (NAND e NOR rispettivamente). Questa soluzione permette di semplificare il circuito e risparmiare sul numero di componenti utilizzati. Ad esempio la figura 28 mostra come sia più conveninete la soluzione con sole porte NAND perché anche se il numero di porte logiche è maggiore il circuito può essere realizzato con un solo integrato invece che tre.

Volendo è possibile seguire una procedura per ridurre funzioni logiche espresse come somma di prodotti (o prodotto di somme) con sole porte NAND o NOR come negli esempi 8, 9 e 10. Per farlo bisogna:

  • esprimere la funzione logica come somma di prodotti o come prodotto di somme
  • fare una doppia negazione della funzione
  • applicare il teorema di De Morgan per ottenere un'espressione con solo NAND o solo NOR

6 Livelli logici e circuiti

Nei circuiti digitali gli stato logici 0 e 1 vengono associati a un livello di tensione alto H o basso L. I valori alto e basso corrispondono in realtà a due intervalli separati da un fascia “proibita” che devone essere evitata per non avere incertezza nello stato logico.

Si parla di:

  • logica positiva, se 0 corrisponde al livello basso L e 1 a quello alto H
  • logica negativa, se 0 corrisponde al livello alto H e 1 a quello basso L

La logica positiva è quella più utilizzata. In logica negativa la funzione svolta da circuito è duale rispetto a quella in logica positiva (una NAND diventa una NOR, ecc.).

7 Il concetto di porta logica

Le funzioni logiche vengono anche chiamate porte logiche (logic gates) perché il loro funzionamento può anche essere interpretato come quello di un interruttore che lascia passare o blocca un segnale digitale. Ad esempio, se nella figura 30 usiamo uno dei due ingressi per un segnale digitale e l'altro come terminale di controllo, vediamo che l'uscita replica il segnale digitale quando il segnale di controllo è alto4).

8 Forme canoniche

Dalla tavola della verità è possibile ricavare due espressioni canoniche che descrivono la funzione come:

  • somma di prodotti (mintermini)
  • prodotto di somme (maxtermini)

dove un mintermine è il prodotto di tutte le variabili logiche di ingresso, eventualmente complementate e un maxtermine è la somma di tutte le variabili logiche di ingresso, eventualmente complementate.

Prima forma canonica

Per ricavare dalla tabella della verità l'espressione della funzione nella prima forma canonica, cioè come somma di mintermini, bisogna:

  • considerare le sole combinazioni dove l'uscita vale 1
  • esprimere per ogni combinazione il relativo mintermine come prodotto delle variabili in ingresso eventualmente complementate se nella combinazione valgono zero
  • sommare i mintermini

Ad esempio per la tabella di figura 33 bisogna considerare le righe 1, 2, 5 e 7, dove l'uscita vale 1. Sommando i mintermini corrispondenti alle quattro combinazioni si ottiene:

`Y = bar A bar B bar C + bar A bar B C + A bar B bar C + A B bar C`

Seconda forma canonica

Per ricavare dalla tabella della verità l'espressione della funzione nella seconda forma canonica, cioè come prodotto di maxtermini, bisogna:

  • considerare le sole combinazioni dove l'uscita vale 0
  • esprimere per ogni combinazione il relativo maxtermine come somma delle variabili in ingresso eventualmente complementate se nella combinazione valgono 1
  • fare il prodotto logico dei maxtermini

Ad esempio, sempre per la tabella di figura 33, bisogna considerare le righe 3, 4, 6 e 8, dove l'uscita vale 0. Il prodotto logico dei maxtermini corrispondenti alle quattro combinazioni è:

`Y = (A + bar B + C)(A+ bar B + C)(bar A + B + bar C)(bar A + bar B + bar C)`

Extra

  • non solo teoria 3: un gioco dove bisogna indovinare una combinazione di bit (stile Mastermind) e una serratura a combinazione digitale (qui la simulazione).

9 Le mappe di Karnaugh

Le mappe di Karnaugh sono una rappresentazione alternativa alla tabella della verità di una funzione logica. Si usano quando le variabili in ingresso sono al massimo quattro e permettono, con un procedimento, di esprimere la funzione logica come somma di prodotti o prodotto di somme in forma minima (col minor numero di operatori logici possibile).

Nella mappa di Karnaugh gli ingressi sono disposti sia in orizzontale che in verticale e, con più di due ingressi, vengono raggruppati come mostrato in figura 36. Le possibili combinazioni degli ingressi sono indicate nei due assi e ordinati in modo tra due combinazioni successive cambi un solo valore5). La tabella si riempie indicando il valore dell'uscita - 1 o 0 - per le varie combinazioni.

Per minimizzare una funzione logica espressa nella prima forma canonica (eventualmente ricavabile dalla tabella della verità) si procede così:

  • si individuano dei rettangoli costituiti da un numero di caselle pari a una potenza di 2 (quindi 1, 2, 4, 8 caselle) contenenti tutte il valore 1; i rettangoli possono essere formati anche unendo le caselle agli estremi della mappa (ad esempio una all'estrema sinistra e una all'estrema destra della stessa riga)
  • per ogni rettangolo scrivere il prodotto delle variabili di ingresso che non cambiano valore, negando la variabile se il suo valore è 0
  • l'espressione minimizzata della funzione logica si ottiene come somma di questi prodotti

Nell'individuare i “rettangoli” bisogna prendere quelli più grandi possibili che permettono di “coprire” tutti gli 1 con meno rettangoli.

L'esempio 12 mostra come applicare il procedimento: dalla tabella della verità si ricava la prima espressione canonica, poi costruita la mappa si individuano 2 possibili soluzioni equivalenti (3 rettangoli da 2 caselle) e quindi i termini da sommare. E' proposto anche il circuito che realizza la funzione con delle porte logiche.

Volendo ottenere una espressione minima come prodotto di somme si procede così:

  • si individuano dei rettangoli costituiti da un numero di caselle pari a una potenza di 2 (quindi 1, 2, 4, 8 caselle) contenenti tutte il valore 0; i rettangoli possono essere formati anche unendo le caselle agli estremi della mappa (ad esempio una all'estrema sinistra e una all'estrema destra della stessa riga)
  • per ogni rettangolo scrivere la somma delle variabili di ingresso che non cambiano valore, negando la variabile se il suo valore è 1
  • l'espressione minimizzata della funzione logica si ottiene come prodotto di queste somme

Si veda l'esempio 13 per la seconda forma canonica.

Considerando anche i casi particolari:

  • se la funzione da minimizzare è un prodotto di somme (o una somma di prodotti) ma non è canonica si può sempre ricondurre a una forma canonica
  • se nella tabella della verità il valore di una variabile è indifferente (indicato con la X) si può riempire la mappa di Karnaugh scegliendo il valore più “comodo” ai fini della minimizzazione

Extra: verificare gli esercizi al PC

In Multisim è disponibile lo strumento virtuale Logic Converter. Questo strumento è utilissimo perché permette di ricavare:

  • l'espressione logica da una tavola della verità, sia in forma canonica che in forma minima
  • la tabella della verità dall'espressione logica
  • il circuito con porte logiche (volendo anche con sole porte NAND) a partire dalla espressione logica
  • l'espressione logica o la tabella della verità dal circuito con porte logiche

Questo strumento permette di verificare facilmente tutti gli esercizi del testo. A questo scopo conviene utilizzare le porte TIL (Technology Indipendend Logic) che non specificano la famiglia logica ma si comportano che porte logiche ideali, disponibili nel gruppo Misc Digital.

Torna all'indice.

1)
NB non in aritmetica!
2)
vale anche per 3 o più termini
3)
qui un confronto e una spiegazione dei simboli
4)
Gli altri circuiti funzionamno in maniera simile ma con piccole variazioni (la porta è aperta con segnale di controllo basso oppure il segnale viene trasmesso ma invertito)
5)
non sono ordinati secondo il sistema di numerazione binario ma secondo il Codice_Gray
Questo sito Web utilizza i cookie. Utilizzando il sito Web, l'utente accetta la memorizzazione dei cookie sul proprio computer. Inoltre riconosci di aver letto e compreso la nostra Informativa sulla privacy. Se non sei d'accordo, lascia il sito.Maggiori informazioni sui cookie
sezione_3c.txt · Ultima modifica: 2023/02/23 13:59 da admin