1Variabili logiche e circuiti combinatori

Si definisce variabile logica binaria una variabile che pu assumere solo due valori a cui si fa corrispondere,convenzionalmente, lo stato logico 0 e lo stato logico l. Una variabile logica pertanto un segnale binario inquanto nella variazione dello stato logico insita l'informazione.La posizione di un interruttore, che pu essere aperto (off) o chiuso (on), con la conseguente assenza opresenza di corrente, rappresenta una variabile logica; una tensione di tipo binario, che pu assumere solodue valori, quello alto (H = high) o quello basso (L = low), un altro esempio di variabile logica.Se si hanno due variabili logiche A e B, queste sono combinabili in quattro modi diversi (00-01-10-11). Ingenerale, detto n il numero delle variabili, le combinazioni sono 2n.

Circuiti combinatori

Si tratta di circuiti che presentano, in generale, pi ingressi e pi uscite, a ognuna delle quali corrispondeuna variabile logica binaria.A ogni combinazione delle variabili logiche in ingresso, presente in un dato istante, corrisponde, nello stessoistante, una ben determinata combinazione delle variabili logiche in uscita. In altri termini, noto lo statologico degli ingressi noto anche quello delle uscite nello stesso istante.La funzione logica di un circuito combinatorio, ovvero il legame ingressi-uscite dello stesso, esprimibileattraverso una tabella della verit, che riporta per ogni combinazione degli ingressi la corrispondentecombinazione delle uscite. La funzione logica di un circuito pu essere descritta in forma sintetica, oltre chetramite una tabella della verit, attraverso una o pi espressioni logiche che sfruttano le regole dellalgebra diBoole.

A Y B C

a) Generico circuito combinatorio

A B C Y0 0 0 10 0 1 00 1 0 10 1 1 01 0 0 11 0 1 01 1 0 11 1 1 1

b) Esempio di tabella della verit nel caso di tre ingressi ed una uscita

Algebra di BooleL'algebra booleana fu ideata da George Boole (1815-1864) per la soluzione di problemi logici, come la verit o la falsitdi affermazioni conseguenti ad altre secondo determinate regole. Le variabili booleane a cui corrispondono leaffermazioni vere/false sono variabili binarie e possono facilmente adattarsi al livello alto o basso di una tensione o a uninterruttore aperto o chiuso. Pertanto l'algebra booleana, con la sostituzione dell'affermazione vera/falsa con i valori 1/0,ben si adatta all'elettronica digitale binaria. L'algebra di Boole si basa sui seguenti assiomi:

CircuitoCombinatorio

2CBAY +=

L'operatore () detto operatore di prodotto logico (AND).L'operatore (+) detto operatore di somma logica (OR).Loperatore ( ) detto operatore di complementazione logica (NOT).Questi assiomi vanno accettati nella logica booleana e quindi non si devono interpretare secondo le regolematematiche abituali (sarebbe in questo caso assurdo porre 1 + 1 = 1).Un'interpretazione circuitale a questi assiomi pu essere data per mezzo della seguente figura:

Sfruttando le regole di quest'algebra possibile esprimere, in forma sintetica, la funzione logica di unqualunque circuito, attraverso una sua espressione logica. Ad esempio l'espressione

soddisfa la tabella della verit precedente (per verificarlo basta applicare a ogni possibile combinazione degliingressi gli assiomi booleani).

DualitSe una espressione logica vera, ovvero soddisfa gli assiomi di Boole, anche la sua duale vera.

Infatti, la prima colonna degli assiomi booleani sostituibile alla seconda se si scambia l'operatore AND conl'operatore OR, ogni 1 con uno 0 e ogni 0 con un 1 e, viceversa, possibile passare dalla seconda colonnaalla prima. Questa propriet detta della dualit ed valida per ogni espressione logica vera.

Propriet e teoremi dell'algebra di Boole

Propriet:

A+B = B+AAB = BA propriet commutativa

(A+B)+C = A+(B+C)(AB)C = A(BC) propriet associativa

(AB) + (AC) = A(B + C)(A + B)(A + C) = A + (BC)

propriet distributiva

01

000010001

111

=====

10

111101110000

==+=+=+=+

30

1

==+

AA

AA

( )( ) BABAA BABAA =+ +=+

Teoremi:

A+1=1A0 = 0

teorema di annullamento

A+0=AAl = A

teorema di identit

teorema dei complementi

A +A = AAA = A

teorema di idempotenza

A+(AB) = AA(A + B) = A

primo teorema dell'assorbimento

secondo teorema dell'assorbimento

teorema di De Morgan

Grazie alla dualit tutte le propriet e tutti i teoremi sono esprimibili per mezzo di due relazioni.

Teorema di Shannon

Una estensione del teorema di De Morgan il teorema di Shannon che afferma che il complemento di unaespressione logica ottenibile complementando le singole variabili e scambiando tra loro le operazioni disomma e prodotto.

Questi teoremi sono tutti facilmente dimostrabili semplicemente verificandone la validit per ognuna dellepossibili combinazioni delle variabili logiche (per la dualit basta ovviamente verificare per ogni teoremauna sola espressione).

Esempio: De Morgan.

A B A+B

0 0 0 1 1 1 10 1 1 0 1 0 01 0 1 0 0 1 01 1 1 0 0 0 0

Tali teoremi possono anche essere dimostrati per deduzione ossia provando l'identit dell'espressionemediante l'applicazione successiva di altri teoremi o propriet.Esempio:nel caso del primo teorema dell'assorbimento, raccogliendo la A si ottiene A + (AB) = A(1 + B),ma poich (1 + B) vale 1 per il teorema dell'annullamento e A1 vale A per il teorema d'identit.

BABA

BABA

+==+

BA + BA A B

4Funzioni logiche primarie

I circuiti capaci di svolgere le operazioni logiche assiomatiche AND OR - NOT realizzano delle funzionilogiche primarie in quanto, combinando opportunamente pi circuiti di questo tipo, possibile realizzare unafunzione logica comunque complessa.

Funzione logica AND

La funzione logica AND: simbolo classico (a), simbolo secondo le norme ANSI/IEEE (b) e tabella dellaverit (c).

Osservando la tabella, si pu notare che l'uscita a l solo se tutte le entrate sono a 1.

Funzione logica OR

La funzione logica OR: simbolo classico (a), simbolo secondo le norme ANSI/IEEE (b) e tabella della verit(c).

Dalla tabella della verit si nota che in questo caso si ha 1 in uscita ogni volta che si ha l in uno degliingressi.

Funzione logica NOTLa funzione logica NOT realizza l'assioma della complementazione e quindi se l'ingresso 1, l'uscita 0 eviceversa.

Funzione logica NOT: simbolo classico (a), simbolo ANSI/IEEE (b) e tabella della verit.

5Il problema della minimizzazione

Una certa funzione logica pu essere ottenuta con diverse soluzioni circuitali, a ognuna delle qualicorrisponde una diversa espressione logica; in linea generale, la soluzione circuitale migliore quella a cuicorrisponde l'espressione logica minima, ovvero realizzabile con il numero minimo possibile di funzionilogiche primarie. Per minimizzare una espressione logica si possono applicare le propriet dell'algebra diBoole, anche se si tratta di una tecnica "per tentativi" non sempre agevole da utilizzare.

Esempio di minimizzazione:

Dove si applicata rispettivamente la propriet distributiva, il teorema dellannullamento e quello diidentit.

Dove si applicata rispettivamente la propriet distributiva, il teorema dei complementi e quellodidentit.

Altre funzioni logiche

La funzione NAND

Un NAND facilmente ricavabile facendo seguire a un AND un NOT, le uscite sono i complementi diquelle di un AND.

Funzione logica NAND: simboli, equivalenza logica e tabella della verit.

La funzione NOR

Tale funzione si ottiene facendo seguire un NOT a un OR. In questo caso le uscite sono i complementi dellecorrispondenti di un OR.

Funzione logica NOR: simboli, equivalenza logica, tabella della verit.

( ) ABCAABBCACAABCABY +=++=++= 1

( ) ( ) 1=+=+++=+++= AABBABBAABBABABAY

6La funzione OR esclusivo (EX-OR)

L'OR esclusivo a due ingressi un circuito capace di riconoscere se due ingressi sono diversi (uscita = 1) osono uguali (uscita = 0).

EX-OR: simbolo classico (a), ANSI/IEEE (b) e tabella della verit (c).

Ad esclusione della quarta combinazione, la tabella della verit corrisponde a quella di un OR a due ingressi.

Per un numero di ingressi qualsiasi n si pu verificare che un'operazione di OR esclusivo fornisce l'uscita a lse dispari il numero di l in ingresso, fornisce invece 0 in uscita se il numero di l pari.Volendo anche possibile definire la EX-NOR, ottenibile facendo seguire a un EX-OR un NOT; questafunzione anche detta funzione coincidenza (Y = l se gli ingressi sono uguali).

EX-NOR: simbolo classico (a), ANSI/IEEE (b) e tabella della verit (c).

Gruppi universali

I circuiti AND-OR-NOT costituiscono, nel loro insieme, un gruppo universale in quanto combinandoopportunamente queste funzioni primarie possibile ottenere qualunque funzione logica, comunquecomplessa.Anche i gruppi AND-NOT e OR-NOT sono universali, di conseguenza i NAND da soli gi costituiscono ungruppo universale e cos pure i NOR. Per dimostrare quest'ultima affermazione basta verificare che tutte e trele funzioni primarie sono ottenibili con solo NAND o solo NOR.

Forme canoniche

Data una espressione logica possibile minimizzarla e risalire al corrispondente circuito; procedendo inmodo inverso ovviamente possibile, noto il circuito, ricavare la sua corrispondente espressione logica.Vediamo, per, come nota la tabella della verit sia possibile risalire da questa a una espressione logica chela soddisfi, da cui ricavare il circuito.

7Prima forma canonica

Supponiamo di volere realizzare una rete combinatoria che soddisfi la seguente tabella della verit:

A B C Y0 0 0 10 0 1 10 1 0 00 1 1 01 0 0 11 0 1 01 1 0 11 1 1 0

Consideriamo inizialmente le combinazioni degli ingressi a cui corrisponde un l in uscita e scriviamo perognuna di queste un'espressione capace di dare l solo in corrispondenza della combinazione di ingressoscelta:

combinazione 000:combinazione 100:

combinazione 001:combinazione 110:

Possiamo osservare che ogni espressione logica stata ottenuta facendo il prodotto delle tre variabili presecomplementate se valgono 0 e non complementate se valgono l. Questi singoli prodotti sono dettimintermini.Se ora si vuole ricavare l'espressione che soddisfa la tabella delle verit, basta sommare i mintermini; cosfacendo avremo l in uscita ogni volta che si verificher una delle quattro combinazioni desiderate, negli altricasi l'uscita sar 0:

Questa espressione detta prima forma canonica.

Generalizzando si pu affermare che una generica espressione logica, a n variabili di ingresso e una di uscita, sempre esprimibile nella forma canonica somma di mintermini; questi ultimi sono tanti quante lecombinazioni degli ingressi a cui corrisponde l in uscita e sono caratterizzati dal fatto di contenere tutte levariabili di ingresso tra loro moltiplicate, prese complementate se valgono 0 o non complementate sevalgono l.

La prima forma canonica non per, in generale, una espressione minima, perci si dovr procedere ad unapossibile semplificazione.

Seconda forma canonica

Riferendoci sempre alla precedente tabella della verit possiamo ora procedere nel modo seguente:individuato gli 0 in uscita si scrivono le espressioni capaci di dare 0 solo in corrispondenza dellacombinazione considerata; queste espressioni logiche vengono dette maxtermini e si ottengono sommando letre variabili, prese complementate se valgono l e non complementate se valgono 0. L'espressione che siottiene facendo il prodotto logico di tutti i maxtermini soddisfa la tabella della verit ed detta secondaforma canonica

CBAY

CBAY

==

CBAY

CBAY

==

CBACBACBACBAY +++=

( ) ( ) ( ) ( )CBACBACBACBAY ++++++++=

8Generalizzando si pu dire che una generica espressione logica a n variabili di ingresso e una di uscita, sempre esprimibile nella forma canonica prodotto di maxtermini; questi ultimi sono tanti quante lecombinazioni degli ingressi a cui corrisponde 0 in uscita e sono caratterizzati dal fatto di contenere tutte levariabili in ingresso tra loro addizionate, prese complementate se valgono l o non complementate se valgono0.

Anche la seconda forma canonica non in linea generale minima.In conclusione ogni circuito combinatorio a un'uscita sempre esprimibile attraverso due diverse formecanoniche, eventualmente minimizzabili.

Le mappe di Karnaugh

Abbiamo visto come sia possibile effettuare la minimizzazione usando le regole dell'algebra di Boole, anchese tale operazione non sempre risulta agevole ed intuitiva.Un metodo sistematico che offre il vantaggio di essere particolarmente semplice e comodo e permette diarrivare partendo dalla tabella della verit o (e ci fa lo stesso) da una espressione canonica a espressioniminime del tipo somma di prodotti o del tipo prodotti di somme dato dalle mappe di Karnaugh che risultaparticolarmente agevole per un numero di variabili non superiore a quattro.Karnaugh presuppone di conoscere la tabella della verit (o una forma canonica); tramite questa si costruisceuna mappa che ne , in forma diversa, un equivalenteOgni mappa contiene un numero di caselle pari alle 2n combinazioni delle n variabili dingresso. Le casellecon un lato in comune sono dette adiacenti; si devono considerare tali anche le caselle alle estremit opposte,come se la mappa si richiudesse su se stessa.Le caselle devono essere disposte in modo che passando da una qualsiasi di queste a una sua adiacente, lungouna riga o una colonna, cambi il valore di una sola variabile (, in effetti, tale condizione che stabilisceladiacenza o meno di due caselle assumendo cos un significato non solo geometrico).Per rappresentare una funzione logica con una mappa, se si fa riferimento alla prima forma canonica, siscrive l nelle caselle che corrispondono alle combinazioni delle variabili di ingresso per le quali la funzionevale l, e nelle caselle lasciate vuote si sottintendono gli 0. In modo analogo si scrivono solo gli 0 se si fariferimento alla seconda forma canonica.Per comprendere il metodo si supponga di dovere minimizzare la seguente funzione espressa nella primaforma canonica:

Ricordando la definizione di mintermine si vede che le combinazioni degli ingressi a cui corrisponde 1 inuscita sono: 110-111-011Una volta individuate queste combinazioni facile costruire la mappa:

C\AB 00 01 11 100 11 1 1

Consideriamo il raggruppamento indicato con il tratteggio di colore blu: a questi due 1 nella funzionecanonica corrisponde la somma:

Possiamo notare che nel raggruppamento considerato A e B non variano spostandosi da una casella all'altra,mentre C che varia corrisponde alla variabile semplificata.

BCAABCCABY ++=

( ) ABCCABABCCABY =+=+=

9Analogamente, al raggruppamento indicato con il tratteggio di colore rosso corrisponde la semplificazione:

Anche in questo caso la variabile eliminata quella che varia passando da una casella all'altra. Inconclusione la minimizzazione porta alla seguente funzione:

Y = AB + BCA questo risultato si arrivati considerando il mintermine ABC due volte, questo sempre possibile inquanto, per il teorema di idempotenza, la somma di pi mintermini uguali non altera la funzione logica.

Come minimizzare con una mappa di 1Riassumendo, la minimizzazione con le mappe di Karnaugh, qualora siano evidenziati gli 1, si effettua nelseguente modo:a) si individuano tutti i possibili raggruppamenti rettangolari di 1 adiacenti, che ne contengano il maggior

numero possibile, ma sempre in quantit potenza del 2 (l-2-4-8-16);b) si sceglie il minimo numero di raggruppamenti possibile per considerare tutti gli 1 della mappa almeno

una volta;c) a ogni raggruppamento si fa corrispondere un prodotto delle sole variabili che hanno lo stesso valore in

tutte le caselle; queste variabili vanno complementate se valgono 0 e non complementate se valgono 1 (levariabili che cambiano valore spostandosi da una casella allaltra dello stesso raggruppamento vannosemplificate);

d) l'espressione minima pari alla somma dei termini ricavati al punto c).

Esempio:Realizzare un circuito in forma minima che soddisfi questa tabella.

A B C Y0 0 0 10 0 1 00 1 0 10 1 1 11 0 0 11 0 1 11 1 0 01 1 1 0

La funzione canonica risulta:

C\AB 00 01 11 100 1 1 11 1 1

La forma minima risulta essere:

( ) BCAABCABCBCAY =+=+=

CBACBABCACBACBAY ++++=

CBBABAY ++=

10

Oppure equivalentemente:

C\AB 00 01 11 100 1 1 11 1 1

Per cui abbiamo

Nella figura seguente sono riportate due possibili soluzioni tra loro equivalenti:

Esempio:

C\AB 00 01 11 100 1 1 1 11 1 1

Come minimizzare con una mappa di 0

In modo del tutto analogo si procede evidenziando gli 0:a) si individuano tutti i possibili raggruppamenti rettangolari di 0 adiacenti, che ne contengano il maggiornumero possibile, ma sempre in quantit potenza del 2;b) si sceglie il minimo numero di raggruppamenti necessari, per considerare tutti gli 0 almeno una volta;c) a ogni raggruppamento si fa corrispondere una somma delle sole variabili che hanno lo stesso valore intutte le caselle; le variabili vanno complementate se valgono l e non complementate se valgono 0;d) l'espressione minima il prodotto dei termini ricavati al punto c).

Esempio:

CD\AB 00 01 11 1000 001 0 011 0 010 0

BABACAY ++=

( ) ( )DBADBY +++=

BABACY ++=

11

Caso con pi di quattro variabiliCon opportuni accorgimenti possibile estendere il metodo anche a funzioni logiche con pi di quattrovariabili. Per esempio, nel caso di cinque variabili si possono considerare due sottomappe riferite allevariabili A, B, C, D, una con E = 0 e una con E = 1. I raggruppamenti nelle sottomappe vengono realizzati alsolito modo, ma bisogna tener presente che gli 1 occupanti le stesse posizioni nelle due sottomappe vannoconsiderati adiacenti (infatti varia solo E). In pratica, si deve immaginare le due sottomappe sovrapposte intrasparenza.

In sintesi:1. Per realizzare il circuito combinatorio corrispondente a una tabella della verit necessario ricavare

un'espressione logica che la soddisfa: la prima e la seconda forma canonica sono le espressioni pifacilmente ricavabili da una tabella della verit e che la soddisfano.

2. Se l'espressione logica non minima, prima di procedere alla realizzazione del circuito corrispondenteconviene minimizzarla.

3. La minimizzazione tramite l'applicazione delle regole dell'algebra di Boole pu risultare difficile ecomunque scomoda; pi adatto pu risultare (fino a 6 variabili) l'uso delle mappe di Karnaugh.

4. Se in una tabella della verit esistono delle condizioni di indifferenza (se per una o pi combinazionidingresso sia indifferente che luscita risulti 0 o 1), queste vanno usate in modo da ottimizzare laminimizzazione.

Laboratorio

Si propone la verifica sperimentale della tabella della verit di un NAND a due ingressi.Strumenti e materiali necessari: Alimentatore stabilizzato; IC 7400 (oppure IC 4011), due resistori da 1 kOhm, un resistore da 100 Ohm, un LED; Bread-board.

Fasi operative: Realizzazione del circuito, come da piano di montaggio seguente; Taratura dellalimentatore e collegamento al circuito; Verifica sperimentale della tabella di verit.

Circuito per la verifica della tabella della verit di una NAND, visualizzazione del livello alto.

12

Esercizi di verifica

Cosa si intende per circuiti combinatori? I circuiti logici AND-OR-NOT costituiscono, nel loro insieme, un gruppo universale. Cosa intendiamo

con questaffermazione e quali altri gruppi universali conosci? Per cosa utili la minimizzazione? Minimizzare usando lalgebra di Boole, le seguenti espressioni logiche:

Si proponga una realizzazione circuitale, con soli NAND, della seguente espressione logica:

Data la seguente tabella della verit, si ricavino le corrispondenti forme canoniche (I et II),proponendone per ognuna di esse una realizzazione circuitale.

A B C D Y0 0 0 0 10 0 0 1 00 0 1 0 10 0 1 1 00 1 0 0 10 1 0 1 00 1 1 0 10 1 1 1 01 0 0 0 11 0 0 1 01 0 1 0 11 0 1 1 01 1 0 0 01 1 0 1 11 1 1 0 11 1 1 1 1

Ricavare, utilizzando i mintermini, lespressione minima corrispondente alla precedente tabella dellaverit.

DCBCBBAy ++=

( ) .;

CABCABCBAY

ABBABABAY

++++=+++=

13

Realizzare il circuito combinatorio corrispondente alla seguente tabella della verit, utilizzandoesclusivamente lIC 74150:

A B C D Y0 0 0 0 10 0 0 1 10 0 1 0 10 0 1 1 00 1 0 0 00 1 0 1 00 1 1 0 10 1 1 1 11 0 0 0 11 0 0 1 01 0 1 0 01 0 1 1 11 1 0 0 01 1 0 1 11 1 1 0 01 1 1 1 1

Ricavare dalla seguenti Mappe di Karnaugh le corrispondenti funzioni minime

CD\AB 00 01 11 1000 1 101 1 111 1 110 1 1

CD\AB 00 01 11 1000 0 001 0 0 011

10 0 0 0 0