2 DALLA LOGICA AI CIRCUITI DIGITALI

L’algebra booleana

Le variabili booleane

Le variabili booleane sono l’equivalente delle proposizioni semplici.

Vengono rappresentate con lettere e possono assumere solo due valori che, invece di essere vero e falso, sono 1 e 0.

Come accade per le proposizioni semplici, se una variabile booleana vale 1, allora non può valere 0 e viceversa.

Gli operatori logici

Gli operatori logici sono l’equivalente dei connettivi logici.

Nell’ambito dell’ ▶ algebra booleana vengono definiti quattro operatori logici fondamentali:

• negazione NOT: corrisponde alla negazione non della logica proposizionale. Esistono diverse notazioni per esprimere la negazione NOT, fra cui: NOT (x), x, x’, – x. La tabella di verità della negazione NOT è la stessa della negazione non: basta scrivere 1 al posto di V e 0 al posto di F;
  
  

  x	- x
  0	1
  1	0

  
  
• prodotto AND: corrisponde alla congiunzione e della logica proposizionale. Le diverse notazioni per esprimere il prodotto logico, sono: x AND y, xy, x · y. La tabella di verità del prodotto AND è la stessa della congiunzione e in cui, però, si scrivono 1 e 0 al posto di V e F;
  
  

  x	y	x ⋅ y
  0	0	0
  0	1	0
  1	0	0
  1	1	1

  
  
• somma OR: corrisponde alla disgiunzione o inclusivo. Esistono diverse notazioni per esprimere la somma logica, fra cui: x OR y, x + y. La tabella di verità della somma OR è la stessa della disgiunzione o inclusiva con 1 e 0 al posto di V e F;
  
  

  x	y	x + y
  0	0	0
  0	1	1
  1	0	1
  1	1	1

  
  
• somma XOR: corrisponde alla disgiunzione o esclusivo. Le notazioni per esprimerela sono: x XOR y, x EXOR y, x ⊕ y. La tabella di verità della somma XOR è la stessa della disgiunzione o esclusiva con 1 e 0 al posto di V e F. 
  
  

  x	y	x ⊕ y
  0	0	0
  0	1	1
  1	0	1
  1	1	0

Le funzioni logiche

Le funzioni logiche sono l’equivalente delle proposizioni composte.

Per esempio: – y · (x + y) · z

È importante ricordare che i diversi operatori inseriti in una funzione logica devono essere gestiti con le stesse regole di precedenza usate in matematica, quindi:

• NOT ha precedenza su AND e OR;
• AND ha precedenza su OR e di XOR.

Come nella matematica, per “forzare” una precedenza diversa tra gli operatori, si possono inserire le parentesi.

Analogamente a quanto visto per le proposizioni composte, per conoscere il valore booleano 0 o 1 dell’intera funzione logica possiamo utilizzare le tabelle di verità.

Introduzione ai circuiti digitali

Un ▶ interruttore è un componente che, se inserito in un circuito elettrico, è in grado di interrompere, oppure no, il flusso della corrente al suo interno.

La corrente elettrica è la quantità di carica elettrica che viene trasportata dagli elettroni attraverso i cavi dei circuiti elettrici nell’unità di tempo. Nel Sistema Internazionale viene misurata in ampere (A).

Gli elettroni sono in grado di muoversi liberamente all’interno dei metalli, come per esempio i fili di rame che costituiscono i circuiti elettrici, e vengono trascinati dalla differenza di potenziale (tensione elettrica), misurata in volt (V).

Fino ai primi anni dell’Ottocento gli interruttori utilizzati nei circuiti (non per accendere le lampadine, che furono inventate mezzo secolo più tardi!) erano meccanici e azionabili manualmente proprio come gli interruttori della luce che attualmente abbiamo in casa.

Con l’invenzione dei relè (interruttori elettromeccanici) e, successivamente, con l’introduzione delle valvole termoioniche (interruttori elettrici), l’azionamento degli interruttori incominciò a poter essere di tipo elettrico. I relè e le valvole, infatti, proprio come i moderni transistor, sono componenti azionabili elettricamente che, come gli interruttori, possono assumere solo due stati distinti aperto oppure chiuso.

Quando l’interruttore è aperto, la corrente che passa nel filo, smette di scorrere. Quando l’interruttore viene chiuso, il flusso di corrente riprende.

L’intuizione di far corrispondere i valori logici falso o vero ai due stati discreti 0 (circuito aperto) e 1 (circuito chiuso), spalancò le porte alla realizzazione dei circuiti elettronici binari digitali.

I circuiti digitali sono circuiti elettronici che utilizzano solo due livelli di tensione (generalmente 0 e 5 V), che identificano i due livelli logici 0 e 1.

Nel 1938 Claude Shannon dimostrò che un segnale elettrico che attraversa un circuito costituito da interruttori, segue le stesse regole logiche dell’algebra booleana.

Cerchiamo di capire meglio il concetto con alcuni semplici esempi.

esempio

1. Consideriamo un circuito costituito da due interruttori in serie.

La corrente attraversa prima un interruttore e poi l’altro e arriva “in fondo” solo se entrambi gli interruttori sono chiusi, cioè se sia A sia B valgono 1. Basta che uno dei due interruttori sia aperto (cioè valga 0) perché la corrente non riesca più ad arrivare “in fondo”.

La logica descritta è quella del prodotto AND: la corrente che parte da sinistra, arriva a destra solo se entrambi gli interruttori sono chiusi.

2. Consideriamo un circuito costituito da due interruttori in parallelo.

La corrente, come se fosse acqua in un tubo, può arrivare in fondo scorrendo attraverso l’interruttore C, l’interruttore D o entrambi. Non arriva “in fondo” solo quando C e D sono entrambi aperti. La logica appena descritta è quella della somma OR: la corrente che parte da sinistra, non arriva a destra solo se entrambi gli interruttori sono aperti.

Le porte logiche

I circuiti digitali che abbiamo appena considerato sono costituiti da interruttori ideali che possono essere realizzati con relè, valvole, transistor o altro.

Dal punto di vista teorico è possibile inserire un circuito ideale (per esempio quello che realizza il prodotto AND) all’interno di un dispositivo ideale, chiamato porta logica, come nel seguente esempio.

Quando sia ad A sia a B viene dato in input 1, cioè a entrambi viene detto di rimanere chiusi, la corrente che proviene da sinistra riesce a uscire dalla porta logica (output 1). Se invece a uno dei due interruttori viene dato in input 0 (interruttore aperto), la corrente che proviene da sinistra non riesce a uscire dalla porta logica (output 0).

Ignorando i dettagli del circuito contenuto nella porta logica e spostando sulla sinistra gli input, potremmo immaginare la porta logica AND con il seguente schema.

Grazie a questo sforzo di astrazione ci siamo avvicinati alla rappresentazione di una porta logica AND usata in elettronica digitale.

In modo analogo è possibile realizzare una porta logica per ciascun operatore logico (NOT, OR, XOR) e distinguerle utilizzando forme diverse. In elettronica digitale le porte logiche non hanno la forma rettangolare, ma vengono rappresentate con forme specifiche diverse, inoltre a ciascuna porta logica viene associata la propria logica di funzionamento descritta dalla relativa tabella di verità.

Nella tabella a pagina seguente elenchiamo alcuni dei simboli utilizzati e le relative logiche di funzionamento in riferimento a due input generici x e y.

La porta logica della negazione NOT ha un solo ingresso perché il NOT è un operatore logico unario.

Volendo dare una definizione di porta logica potremmo dire che si tratta di un dispositivo elettronico (idealizzato) che, partendo da input binari, realizza una funzione logica (applicando degli operatori logici) producendo output binari.

Le porte logiche negate

Le porte logiche possono essere composte fra di loro per ottenere output differenti.

Se inseriamo una porta logica NOT subito dopo un’altra porta NOT l’output finale è nuovamente il valore di partenza della variabile booleana.

Possiamo quindi dire che la doppia negazione afferma, cioè applicando due volte l’operatore di negazione NOT, la variabile booleana torna ad avere il valore di verità iniziale.

Se, invece, inseriamo una porta NOT dopo una porta AND otteniamo come output complessivo la negazione di AND.

Esiste una porta logica che contiene il circuito appena descritto: la porta logica NAND (AND Negato), che ha la seguente forma e la cui logica di funzionamento viene descritta dalla corrispondente tabella di verità (visibile nella tabella a pagina seguente).

Analogamente, se inseriamo una porta logica NOT dopo una porta logica OR ottieniamo come output complessivo la negazione di un OR.

Anche in questo caso esiste una porta logica che contiene il circuito: la porta logica NOR (OR Negato), che ha la seguente forma e la cui logica di funzionamento viene descritta dalla corrispondente tabella di verità (visibile nella tabella a pagina seguente).

Infine, inserendo una porta logica NOT dopo una porta logica XOR ottieniamo come output complessivo la negazione di un XOR.

La porta logica che contiene questo circuito è la porta logica XNOR (XOR Negato o NOR esclusivo), che ha seguente forma e la cui logica di funzionamento viene descritta dalla corrispondente tabella di verità (visibile nella tabella a pagina seguente).

Le porte logiche universali

Qualunque funzione logica booleana può essere realizzata utilizzando e combinando solo porte logiche NAND. Per questo motivo la porta logica NAND viene chiamata porta logica universale.

Per esempio, la funzione logica NOT può essere realizzata utilizzando una porta logica NAND, fornendo in input lo stesso valore a entrambi i suoi ingressi.

La correttezza di questa affermazione è facilmente verificabile: basta osservare la tabella di verità della porta NAND e constatare che, poiché gli input sono sempre uguali (y = x), occorre considerare solo le righe evidenziate.

In questo modo, quando in input viene dato x = 0 (quindi anche y = 0) allora l’output è 1 (cioè NOT x); quando invece in input viene dato x = 1 (quindi anche y = 1) allora in uscita abbiamo 0 (ancora NOT x).

La funzione logica AND può essere realizzata utilizzando una porta NAND seguita da una negazione NOT.

Abbiamo appena visto come ottenere un NOT utilizzando una porta NAND, per cui, è possibile ottenere la logica AND, con due porte NAND come nello schema a lato.

Ottenere la funzione logica OR utilizzando solo porte NAND non è altrettanto intuitivo, ma è possibile utilizzando i teoremi di De Morgan.

Gli studi di Boole, alla base dell’algebra booleana che abbiamo descritto, furono influenzati da quelli del logico britannico Augustus De Morgan (1806-1871), noto per aver formulato i due omonimi teoremi.

Il primo teorema di De Morgan dice che la negazione di un prodotto AND è equivalente alla somma OR delle due variabili booleane negate:

 x · y  = x  + y 

Il secondo teorema di De Morgan afferma che la negazione di una somma OR è equivalente al prodotto AND delle due variabili booleane negate:

 x + y  = x  · y 

Verifichiamo il secondo teorema usando le tabelle di verità.

Il secondo teorema di De Morgan afferma che per ottenere un NOR di due input x e y è possibile usare un AND, inserendolo fra la negazione dei due ingressi.

Prima di enunciare i due teoremi di De Morgan, stavamo cercando di ottenere un OR combinando solo porte NAND. Se neghiamo le ultime due colonne della tabella di verità otteniamo che l’uguaglianza continua a essere rispettata e che possiamo riscriverla, come segue:

x + y = x · y 

tenendo conto del fatto che la negazione del NOR non è altro che un OR mentre la negazione dell’AND non è altro che un NAND. Possiamo scrivere che la funzione logica OR (al primo membro) può essere realizzata componendo le porte NAND come illustrato dallo schema (come indicato dal secondo membro).

Utilizzando il primo teorema di De Morgan, con un ragionamento analogo possiamo concludere che anche la porta logica NOR è una porta logica universale e può essere usata per ottenere tutte le altre funzioni logiche booleane.

Nella tabella sono elencati i circuiti equivalenti che consentono di realizzare le principali funzioni logiche utilizzando le porte universali.

Le reti logiche

Come abbiamo visto, la funzione logica x NAND y può essere realizzata collegando una porta AND a una porta NOT secondo il seguente schema.

In generale qualunque funzione logica booleana f può essere realizzata “fisicamente” collegando tra loro le diverse porte logiche. Lo schema complessivo che si ottiene prende il nome di rete logica.

Le reti logiche sono circuiti costituiti dal collegamento di porte logiche, che realizzano “fisicamente” le funzioni logiche dell’algebra booleana.

Dalle porte logiche ai circuiti integrati

Consideriamo la rete logica in figura, fornita di quattro ingressi (A, B, C, D) e quattro uscite (U₁, U₂, U₃, U₄) possiamo scrivere le funzioni logiche in output:

Come sappiamo, teoricamente sarebbe possibile realizzare tutte le porte logiche utilizzando un’unica porta logica universale (per esempio la porta NAND). Quindi i produttori di circuiti integrati potrebbero realizzare un unico chip e ridurre i costi, grazie a una produzione più omogenea.

Tuttavia risulta molto più conveniente produrre chip che contengano direttamente porte logiche generiche perché combinando più porte universali, si ottengono circuiti integrati che occupano un’area maggiore, consumano più corrente elettrica e si surriscaldano più facilmente.

Le scelte tecnologiche compiute dalle aziende durante la fase di progettazione dei circuiti integrati, quindi, non sono così scontate come si potrebbe pensare.