Reti Combinatorie

Reti Logiche T
Ingegneria Informatica
 Generica rete logica
Rete logica: Modello astratto che assume come primitive alcune
semplici elaborazioni di segnali binari (gate) e realizza comportamenti
più complessi. Nel seguito definiremo procedimenti per stabilire
1. quale struttura realizza un dato comportamento (sintesi)
2. quale comportamento ha una data struttura (analisi)

𝑥0 𝑧0
Rete
⋮ Logica ⋮
con 𝑛 ingressi
𝑥𝑛−1 e 𝑚 uscite 𝑧𝑚−1

Convenzioni: ingressi a sinistra, uscite a destra,

nomi dei segnali di ingresso/uscita della rete indicati all’interno della rete

2
 Trascodifica BCD/7 Segmenti

a
a
b
D
Convertitore c f b
C
di codice d g
B
BCD / 7 segmenti e
A e c
f
g d

“0” “1” “2” “3” “4” “5” “6” “7” “8” “9”

• Questo convertitore è un esempio di macchina combinatoria: le 7 uscite

(abcdefg) sono univocamente determinate dal valore corrente dei 4
ingressi (DCBA) che codificano un numero senza segno tra 0 e 9.
• Es: DCBA=0001 -> abcdefg = 1001111
3
 Esempi di connessione
• Dato un bus N[3..0], in cui è memorizzato un numero senza segno con il
bit più significativo in posizione 3, come deve essere collegato al
convertitore per ottenerne la rappresentazione a 7 segmenti?

a a
b b
N3 D N0 D
Convertitore c Convertitore c
N2 C N1 C
di codice d di codice d
N1 B N2 B
BCD / 7 segmenti e BCD / 7 segmenti e
N0 A N3 A
f f
g g

✓ ? 4
 Esempi di macchine combinatorie

× 1 2 3 …. 8 9
1 1 2 3 …. 8 9
2 2 4 6 …. 16 18
3 3 6 9 …. 24 27
…………………………….
…………………………….
8 8 16 24 …. 64 72
9 9 18 27 …. 72 81

la tavola pitagorica il dizionario

5
 La cassaforte

• Macchina con 2 ingressi (𝒙, 𝒚) e una

uscita (𝒛) 𝑥
• 𝒛=0/1: cassaforte chiusa/aperta
• 𝒛=1 con ingresso 11 se e solo se la 𝑧 𝑦
sequenza vista in ingresso è stata
quella corretta, ovvero
𝒙𝒚 = 00 – 10 – 11
• È un esempio di riconoscitore di
sequenze

• Con ingresso 11, 𝒛 = 0 o 1 ?

• L’informazione è insufficiente a
determinare il comportamento della 𝑥
SAFE 𝑧
macchina, dipende anche dalla storia, 𝑦
è quindi una macchina sequenziale
6
 Combinatoria vs. Sequenziale

• Rete (o macchina) combinatoria: l’uscita dipende unicamente dagli

ingressi correnti

• Rete (o macchina) sequenziale: l’uscita non è univocamente

determinata dagli ingressi correnti, ma dipende anche dalla storia
passata (sequenza di ingressi visti in precedenza) e/o dallo scorrere
del tempo

• Come faccio a capire se una rete va realizzata come combinatoria o

sequenziale? Se in presenza di una stessa configurazione di
ingressi la rete deve fornire 2 o più uscite diverse, allora è una rete
sequenziale, altrimenti è una rete combinatoria

7
 Altri esempi
dipende solo da i

i 9 25 49
u= i u 3 5 7

moneta 0.50 1
dipende dagli ingressi
(monete) precedenti
stampa

dipende dal tempo

V G R
t
8
 Composizione e decomposizione
La disposizione in serie e/o in parallelo di reti logiche
combinatorie è ancora una rete logica combinatoria

Per progettare una rete con 𝑚 uscite si possono quindi

progettare 𝑚 reti con una sola uscita, operanti in parallelo

𝑥0 rete 𝑧0 = 𝐹0 (𝑥0 , 𝑥1 , … , 𝑥𝑛−1 )

⋮ combinatoria ⋮
𝑥𝑛−1 complessiva 𝑧𝑚−1 = 𝐹𝑚−1 (𝑥0 , 𝑥1 , … , 𝑥𝑛−1 )

𝑥0 rete
⋮ combinatoria 𝑧0
𝑥𝑛−1 #0 𝑧0 = 𝐹0 (𝑥0 , ⋯ , 𝑥𝑛−1 )
ቐ ⋮
...

𝑥0 rete
𝑧𝑚−1 = 𝐹𝑚−1 (𝑥0 , ⋯ , 𝑥𝑛−1 )
⋮ combinatoria 𝑧𝑚−1
𝑥𝑛−1 #m-1
9
 Comportamento & Struttura
Comportamento sintesi Struttura
(cosa fa la rete) (come è realizzata la rete)
analisi
Descrizione in linguaggio Espressione
naturale
«la rete ha uscita 𝑧=1
quando 𝑥 è uguale a 𝑦 e
𝑧 = 𝑥 ≡𝑦 𝑥 ⊕𝑤
diverso da 𝑤»
o, in modo equivalente,
Tabella della verità
𝑤 𝑥 𝑦 𝑧 Schema logico
0 0 0 0 𝑤
0 0 1 0
0 1 0 0 𝑧
0 1 1 1 𝑥
… … … … 𝑦
10
 Funzioni complete e incomplete
Funzione completa di 𝑛 variabili binarie 𝑧 = 𝐹(𝑥0 , 𝑥1 , … , 𝑥𝑛−1 ):
per ognuna delle 2𝑛 configurazioni degli ingressi, è definito il valore
dell’uscita 𝑧.

Esempi: decoder, sommatore, selettore a n vie (multiplexer)

Funzione incompleta o non completamente specificata:

vi è almeno una configurazione degli ingressi per cui non è specificato il
valore dell’uscita, o perché tali configurazioni non possono presentarsi o
perché non interessa il valore dell’uscita nel caso in cui si presentino

Esempi: convertitore BCD/7 segmenti, encoder

11
 Tabella della verità
• Descrive univocamente il comportamento di una rete combinatoria a 𝑛
ingressi (ovvero di una funzione 𝐹 di 𝑛 variabili binarie 𝑥0, 𝑥1 , … , 𝑥𝑛−1 )
• Nel caso di funzioni non completamente specificate si possono avere
– Meno righe, evitando di riportare le configurazioni di input che non possono presentarsi
– Il simbolo − (don’t care) nelle uscite (invece di 0 o 1) ad indicare una condizione di
indifferenza
• NOTA BENE: Una struttura che realizza un comportamento è
sempre completamente specificata, ovvero l’uscita avrà valore 0 o
1 per ogni configurazione di ingresso. La presenza di un don’t care
nella specifica del comportamento da al progettista la libertà di
scegliere se essa varrà 0 o 1 per quella configurazione.
𝒏 + 𝟏 colonne
𝑥0 𝑥1 … 𝑥𝑛−1 𝐹(𝑥0 , 𝑥1 , … , 𝑥𝑛−1 )
0 0 … 0 0 oppure 1 oppure −
0 0 … 1 0 oppure 1 oppure −
𝟐𝒏 righe
⋮ ⋮ ⋱ ⋮ ⋮
(se completamente
1 1 … 0 0 oppure 1 oppure −
specificata)
1 1 … 1 0 oppure 1 oppure −
12
 Il convertitore BCD/7 Segmenti
• Sono in realtà 7 funzioni in parallelo di 4
ingressi
a(D,C,B,A)
b(D,C,B,A)
…
g(D,C,B,A)

• Descrizione in linguaggio naturale non è

univoca: «6» a cosa equivale?
??

Solo la tabella della verità ci permette di descrivere in

modo non ambiguo il comportamento di una macchina
combinatoria

13
 Convertitore BCD/7 Segmenti
7 funzioni di 4 variabili

D C B A a b c d e f g
a
0 0 0 0 0 0 0 0 0 0 1 a
D b
Convertitore
0 0 0 1 1 0 0 1 1 1 1 C c f b
BCD / d
0 0 1 0 0 0 1 0 0 1 0 B g
7 segmenti e
0 0 1 1 0 0 0 0 1 1 0 A
f e c
0 1 0 0 1 0 0 1 1 0 0 g d
0 1 0 1 0 1 0 0 1 0 0
0 1 1 0 1 1 0 0 0 0 0
Segmento attivo se segnale «0» (uscite
0 1 1 1 0 0 0 1 1 1 1
attive basse), quindi, per esempio, 8 ->
1 0 0 0 0 0 0 0 0 0 0
1 0 0 1 0 0 0 1 1 0 0
uscite tutte «0»
1 0 1 0 - - - - - - -
1 0 1 1 - - - - - - - Le configurazioni che non possono
1 1 0 0 - - - - - - - presentarsi in input possono non essere
1 1 0 1 - - - - - - - riportate oppure utilizzo per l’uscita il
1 1 1 0 - - - - - - - simbolo che rappresenta una condizione
1 1 1 1 - - - - - - - di «indifferenza» (don’t care) 14
 Funzioni di 𝑛 variabili
• Abbiamo già enumerato tutte le funzioni di una e due variabili binarie
• Non potremmo fare lo stesso con 4 ingressi, e scegliere tra queste i gate a
4 ingressi che realizzano le 7 funzioni del convertitore a 7 segmenti?

𝑥 𝑓0 𝑓1 𝑓2 𝑓3
4 funzioni
0 0 0 1 1 di una
1 0 1 0 1 variabile

𝑥 𝑦 𝑓0 𝑓1 𝑓2 𝑓3 𝑓4 𝑓5 𝑓6 𝑓7 𝑓8 𝑓9 𝑓10 𝑓11 𝑓12 𝑓13 𝑓14 𝑓15

0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 16 funzioni
0 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 di due
1 0 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 variabili
1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1

15
 Funzioni complete di 𝑛 variabili
Il numero di distinte funzioni
di 𝑛 variabili binarie
2n
(𝒏) = 2
aumenta esponenzialmente con 𝑛

𝒏 (𝒏) I costruttori non forniscono la realizzazione

1 4 ad hoc di ogni funzione
2 16 E’ il progettista che deve realizzarle tramite
3 256 opportuna composizione di gate elementari
disponibili in forma di circuiti integrati
4 65536
Small Scale Integration
… …
(SSI)

Medium SI (MSI) Large SI,Very LSI (LSI,VLSI)

16
Sintesi: da comportamento a struttura
Comportamento sintesi Struttura
(cosa fa la rete) (come è realizzata la rete)
analisi
Descrizione in linguaggio Espressione
naturale
«la rete ha uscita 𝑧=1
quando 𝑥 è uguale a 𝑦 e
𝑧 = 𝑥 ≡𝑦 𝑥 ⊕𝑤
diverso da 𝑤»
o, in modo equivalente,
Tabella della verità
𝑤 𝑥 𝑦 𝑧 Schema logico
0 0 0 0 𝑤
0 0 1 0
0 1 0 0 𝑧
0 1 1 1 𝑥
… … … … 𝑦
17
 Algebre binarie
Algebra binaria: Sistema matematico formato da un insieme di operatori
definiti assiomaticamente ed atti a descrivere con una espressione ogni
possibile funzione di variabili binarie

Calcolo delle proposizioni Crisippo (250 a.c.)

vero, falso e, o, non
G. Boole (1854)
tre operatori

AND, OR e NOT sono Algebra di commutazione

sufficienti per esprimere ogni 0, 1 +, . , ’ C. Shannon (1938)
possibile funzione binaria tre operatori

Algebra lineare
Algebra del nand Algebra del nor
0, 1   , .
0, 1  0, 1 
due operatori
un operatore un operatore
(EX-OR, AND) 18
A screenshot of a computer

Description automatically generated

19
 Algebra di commutazione
Algebra binaria definita da
1. un insieme di simboli 𝐵 = {0, 1}
2. un insieme di operazioni 𝑂 = {+, . , ’}, ovvero
somma logica (+) prodotto logico (.) complementazione (’)
3. un insieme di postulati P:
0 + 0 = 0 0 .0 = 0 0’ = 1
1 + 0 = 1 1 .0 = 0 1’ = 0
0 + 1 = 1 0 .1 = 0
1 + 1 = 1 1 .1 = 1 I postulati corrispondono
N.B. somma logica, al comportamento dei
non aritmetica gate OR, AND e NOT
20
 Cos’è un’espressione?
Costanti: 0 o 1
Variabili: letterali che possono assumere il valore 0 o 1
Espressioni: stringhe finite di costanti, variabili, operatori
e parentesi, formate in accordo alle seguenti regole:
1) 0 e 1 sono espressioni
2) una variabile è una espressione
3) se A è un’espressione, lo è anche (A’)
4) se A, B sono espressioni, lo sono anche (A+B) e (A.B)

Esempi: a+(b.c) a + bc 0

a’.b (a+b)’ a’b + 0 + ab’

N.B. - L’operazione di negazione è prioritaria rispetto alle altre e quella

del prodotto è prioritaria rispetto alla somma. Non è quindi obbligatorio
racchiuderla tra parentesi. La notazione AB indica A·B
21
Tabelle della verità, espressioni e schemi
Espressioni
• Qual è la relazione tra tabelle
della verità, che descrivono il Tabelle
comportamento, e espressioni della
e schemi logici che descrivono Verità
la struttura di una rete logica?
• Quante espressioni sono

?
possibili data una tabella della
verità? E quanti schemi logici?
• A quante tabelle corrisponde
un’espressione? A quante
tabelle corrisponde uno
schema logico? Schemi
Logici

Comportamento Struttura
22
 Da Schemi logici a Espressioni
Schema logico - Descrizione grafica di una struttura formata da simboli di
gate e da collegamenti tra le loro linee di ingresso e di uscita.

E SL
Relazione I: Ogni struttura formata da gate
connessi in serie e/o in parallelo è descritta
da una sola espressione.

a’
a a’ + b’

a’ + b z = (a’+b’).(a’+b).(a+b’)

b
b’ a + b’
23
 Da Espressioni a Schemi logici
E SL
Relazione II: Ogni espressione
descrive una sola struttura
formata da gate connessi in serie
e/o in parallelo.

Per individuare lo schema descritto da una espressione:

1) si parte dalle parentesi più interne e si traccia il simbolo del gate corrispondente
all’operazione, collegandone gli ingressi ai segnali esterni;
2) si procede in modo analogo con le altre coppie di parentesi, considerando via via
come ingressi dei nuovi gate anche le uscite di quelli già tracciati.

Esempio:
b
a+(b.c) c
a
24
 Esempi
c
(((a)’ + b) · c)’ b
a

Selettore a 2 vie (Multiplexer) I1

A’ · I0 + A · I1
I0

N.B. - Lo schema logico di una espressione corrispondente ad una rete

combinatoria non può avere segnali in retroazione (l’uscita di ogni gate
dipende da segnali d’ingresso e/o da uscite di gate disposti “a monte”).
25
 Espressioni = Schemi Logici
• Esiste quindi una relazione biunivoca tra schemi e espressioni
• Per esprimere la struttura con cui si realizza una funzione si può
quindi utilizzare indifferentemente l’una o l’altra.
• Quando possibile è preferibile privilegiare l’espressione in quanto
più compatta. L’espressione contiene già tutta l’informazione, non
è necessario disegnare anche lo schema
• Che relazione c’è tra espressioni (e quindi schemi logici) e funzioni?

TdV E SL

? 1:1

Comportamento Struttura 26
 Valutazione di una espressione
Valutazione di una espressione di n variabili per una n-pla di valori
1) Si sostituisce ad ogni variabile il valore che ha nella n-upla
2) Partendo dalle parentesi più interne, si sostituisce ogni operazione con il
suo risultato fino ad ottenere o la costante 0 o la costante 1.

Esempio: E(a,b,c) = a+(b.c) per a=0, b=1, c=0

= 0+(1.0)
= 0+0
=0

N° di valutazioni - Una espressione di 𝑛 variabili può essere valutata in 2𝑛

modi diversi, che corrispondono alle 𝑛 configurazioni binarie dei suoi
ingressi.

Quindi, valutando una espressione di 𝑛 variabili per tutte le possibili 2𝑛

configurazioni, ottengo la tabella della verità, ovvero il comportamento
della rete combinatoria che ha quella struttura
27
 Da Espressioni a TdV
Esempio: E(a,b,c) = a+(b.c)
abc E Relazione III: Ogni espressione
E(0,0,0) = 0+(0.0) = 0 000 0 descrive una e una sola tabella della
E(0,0,1) = 0+(0.1) = 0 001 0 verità completamente specificata.
E(0,1,0) = 0+(1.0) = 0 010 0
E(0,1,1) = 0+(1.1) = 1 011 1
TdV E SL
E(1,0,0) = 1+(0.0) = 1 100 1
E(1,0,1) = 1+(0.1) = 1 101 1
E(1,1,0) = 1+(1.0) = 1 110 1
E(1,1,1) = 1+(1.1) = 1 111 1

Il procedimento di ANALISI ha quindi un risultato univoco: partendo da un dato

schema logico o da un’espressione, si può determinare in modo univoco il
comportamento (la tabella della verità) che realizzano

28
Analisi: da struttura a comportamento
Comportamento sintesi Struttura
(cosa fa la rete) (come è realizzata la rete)
analisi
Descrizione in linguaggio Espressione
naturale
«la rete ha uscita 𝑧=1
quando 𝑥 è uguale a 𝑦 e
𝑧 = 𝑥 ≡𝑦 𝑥 ⊕𝑤
diverso da 𝑤»
o, in modo equivalente,
Tabella della verità
𝑤 𝑥 𝑦 𝑧 Schema logico
0 0 0 0 𝑤
0 0 1 0
0 1 0 0 𝑧
0 1 1 1 𝑥
… … … … 𝑦
29
 Da TdV a Espressioni
Relazione IV: Una funzione può essere descritta da una molteplicità di
espressioni

TdV E SL

• Problema della SINTESI: partendo da un comportamento dato come

tabella della verità, quale scegliere tra i vari schemi logici (o espressioni)
che lo realizzano?
• Uno dei metodi più semplici per passare da una tabella della verità a una
espressione (tra le possibili) riguarda l’utilizzo delle cosiddette
«espressioni canoniche»

30
 TdV e Espressioni (canoniche)
Espressione canonica SP (Somma di Prodotti) o Ia forma canonica
Ogni funzione di 𝑛 variabili binarie è descritta da una somma di tanti
prodotti logici quante sono le configurazioni delle variabili per cui la
funzione vale 1. In ciascun prodotto, o mintermine, appare ogni
variabile, in forma vera se nella configurazione corrispondente vale 1, in
forma negata se vale 0.

Espressione canonica PS (Prodotto di Somme) o IIa forma canonica

Ogni funzione di 𝑛 variabili binarie è descritta da un prodotto di tante
somme logiche quante sono le configurazioni delle variabili per cui la
funzione vale 0. In ciascuna somma, o maxtermine, appare ogni
variabile, in forma vera se nella configurazione corrispondente vale 0, in
forma negata se vale 1.

N.B.: questo significa che ogni rete combinatoria può in principio essere
realizzata con due soli livelli di gate (non si considerano i NOT). Ovviamente
sono possibili altre realizzazioni, preferibili per altre caratteristiche.
31
 Sintesi canonica del EX-OR
Ia forma canonica (SP): 1 se
F(x0, x1)= x0’ x1 + x0 x1’ x0=0 e x1=1
1 se e solo se oppure se
x0=0 e x1=1 x0=1 e x1=0
x0 0 negli altri
x1 due casi

x0 x1 x0x1 1 se e solo se
x0=1 e x1=0
0 0 0
0 1 1
1 0 1 IIa forma canonica (PS):
1 1 0 F(x0, x1)= (x0+x1)(x0 ’+ x1’)
x0
x1 Realizzare e
simulare con
Digital
32
 Sintesi canonica dell’Equivalence
Ia forma canonica (SP): 1 se
F(x0, x1)= x0’ x1‘ + x0 x1 x0=0 e x1=0
1 se e solo se oppure se
x0=1 e x1=1
x0 x0=0 e x1=0
0 negli altri
x1 due casi

x0 x1 x0  x1 1 se e solo se
x0=1 e x1=1
0 0 1
0 1 0
1 0 0 IIa forma canonica (PS):
1 1 1 F(x0, x1)= (x0+x1’)(x0 ’+ x1)

x0
x1

33
 Esempio: full adder
• Definire la struttura di una rete logica con 3 ingressi 𝑎,
𝑏 , 𝑟 e 2 uscite 𝑆 e 𝑅 che presenta
– uscita 𝑆 = 1 quando il numero di «1» sui suoi ingressi è
dispari
– uscita 𝑅 = 1 quando in ingresso ci sono due o più «1».
• Questa rete è combinatoria perché l’uscita dipende
solo dagli ingressi attuali
• Questa rete è un «Full Adder»: vedremo più avanti che
è un componente fondamentale per realizzare
operazioni aritmetiche tra numeri binari

34
Espressione canonica SP (1a forma canonica)
𝑎 S=1 se
𝑆 la configurazione d’ingresso è
𝑏 Full Adder C1 o C2 o C4 o C7
𝑅 ovvero se
𝑟
(a=0) e (b=0) e (r=1) o
(a=0) e (b=1) e (r=0) o
a b r S R (a=1) e (b=0) e (r=0) o
C0 0 0 0 0 0 (a=1) e (b=1) e (r=1)
C1 0 0 1 1 0 ovvero se
C2 0 1 0 1 0 (a’=1) e (b’=1) e (r=1) o
C3 0 1 1 0 1 (a’=1) e (b=1) e (r’=1) o
(a=1) e (b’=1) e (r’=1) o
C4 1 0 0 1 0 (a=1) e (b=1) e (r=1)
C5 1 0 1 0 1
S = a’b’r + a’br’ + ab’r’ + abr
C6 1 1 0 0 1
C7 1 1 1 1 1 R = a’br + ab’r + abr’ + abr
35
Sintesi canonica (1a forma) del Full Adder
S = a’ b’ r + a’ b r’ + a b’ r’ + a b r Se compare lo stesso gate
in più espressioni, posso
R = a’ b r + a b’ r + a b r’ + a b r
riportarlo una volta sola
nello schema, collegando
la sua uscita a più ingressi
a valle

r’ r a’ a b’ b 36
Espressione canonica PS (2a forma canonica)
𝑎 S=1 se
𝑆 la configurazione d’ingresso è
𝑏 Full Adder non C0 e non C3 e non C5 e non C6
𝑅 ovvero se
𝑟
((a=1) o (b=1) o (r=1)) e
((a=1) o (b=0) o (r=0)) e
a b r S R ((a=0) o (b=1) o (r=0)) e
C0 0 0 0 0 0 ((a=0) o (b=0) o (r=1))
C1 0 0 1 1 0 ovvero se
C2 0 1 0 1 0 ((a=1) o (b=1) o (r=1)) e
C3 0 1 1 0 1 ((a=1) o (b’=1) o (r’=1)) e
((a’=1) o (b=1) o (r’=1)) e
C4 1 0 0 1 0
((a’=1) o (b’=1) o (r=1))
C5 1 0 1 0 1
S = (a+b+r) (a+b’+r’) (a’+b+r’) (a’+b’+r)
C6 1 1 0 0 1
C7 1 1 1 1 1
R = (a+b+r) (a+b+r’) (a+b’+r) (a’+b+r)
37
Sintesi canonica (2a forma) del Full Adder
S = (a+b+r) (a+b’+r’) (a’+b+r’) (a’+b’+r)
R = (a+b+r) (a+b+r’) (a+b’+r) (a’+b+r)

r’ r a’ a b’ b 38
Espressioni canoniche: notazione simbolica
𝑎
𝑏 Full Adder
𝑆 S (a,b,r) = 3 m (1,2,4,7)
𝑅 = 3 M (0,3,5,6)
𝑟

R (a,b,r) = 3 m (3,5,6,7)
i a b r S R = 3 M (0,1,2,4)
0 0 0 0 0 0
• m(i) : mintermine di n bit che assume il valore 1
1 0 0 1 1 0 solo per la n-pla di valori delle variabili
2 0 1 0 1 0 corrispondente all’indice i
• M(i) : maxtermine di n bit che assume il valore 0
3 0 1 1 0 1
solo per la n-pla di valori delle variabili
4 1 0 0 1 0 corrispondente all’indice i
5 1 0 1 0 1 •Mintermini e maxtermini sono complementari: una
configurazione è un mintermine o un maxtermine
6 1 1 0 0 1
7 1 1 1 1 1 •Pedice dell’operatore  /  : numero di variabili
coinvolte nei mintermini/maxtermini 39
 Equivalenza tra espressioni
Espressioni equivalenti - Due espressioni E1, E2
sono equivalenti, e si scrive E1 = E2,
se e solo se descrivono la stessa funzione (o TdV).

Funzioni (TdV) Espressioni

di di
𝑛 variabili 𝑛 variabili

Espressioni
di F
F

• Un esempio di espressioni equivalenti sono le due espressioni

canoniche (forma PS e SP) appena viste
40
 Equivalenza tra espressioni
Espressioni equivalenti possono corrispondere a schemi logici di complessità
differente
Esempio: funzione 𝑈 di 3 variabili 𝑎, 𝑏, 𝑐 con 6 mintermini e 2 maxtermini:
𝑈 (𝑎, 𝑏, 𝑐) = 3 𝑚 (0,1,2,3,4,5) = 3 𝑀 (6,7)
Le sue espressioni canoniche richiedono
• 6 AND e 1 OR nella forma SP
• 2 OR e 1 AND nella forma PS

=
41
 Espressioni di funzioni incomplete
• Anche espressioni che forniscono eguale valutazione limitatamente
al dominio di una funzione incompleta sono dette equivalenti.
• Esempio: l’encoder è una rete che realizza la trascodifica da codice
1 su N a codice binario.
• A seconda del valore assegnato alle configurazioni non utilizzate
dalla funzione che realizza un encoder a 3 ingressi, ottengo una
famiglia di espressioni diverse tra loro equivalenti
ENCODER a 3 ingressi
Codice binario
Codice 1 su N

x3 x2 x1 z1 z0
𝑥𝑁 𝑧𝑚−1
0 0 0 0 0
⋮ Encoder ⋮
𝑥1 0 0 1 0 1
𝑧0
0 1 0 1 0
1 0 0 1 1
N.B.: le altre configurazioni sono
per ipotesi impossibili, quindi non
è definito come risponde la rete 42
 Espressioni di funzioni incomplete
• Riempiendo le configurazioni non utilizzate con degli «uni» anziché degli
«zeri» posso ottenere un’espressione equivalente, ma più semplice, delle
due uscite. Come individuare la scelta ottima?

x3 x2 x1 z1 z0 x3 x2 x1 z1 z0
0 0 0 0 0 0 0 0 0 0
0 0 1 0 1 0 0 1 0 1
0 1 0 1 0 0 1 0 1 0
1 0 0 1 1 1 0 0 1 1
0 1 1 0 0 0 1 1 1 1
1 0 1 0 0 1 0 1 1 1
1 1 0 0 0 1 1 0 1 1
1 1 1 0 0 1 1 1 1 1

z1 = x3x2’x1’ + x3’x2 x1’ z 1 = x3 + x 2

z0 = x3x2’x1’ + x3’x2’x1 z 0 = x3 + x 1
43
 Sintesi di reti combinatorie

• Un possibile approccio per realizzare la sintesi

di una funzione data è il seguente:
– Scegliere una espressione tra le molteplici
corrispondenti a una data funzione (es. le
espressioni canoniche)
– Operare nel dominio delle espressioni per ridurne
la complessità algebrica mediante manipolazione
algebrica sfruttando le equivalenze notevoli
dell’algebra di commutazione

44
 Equivalenze notevoli
Proprietà della somma e del prodotto logico:
(tutte verificabili confrontando le tabelle della verità dei due lati delle uguaglianze)

E1) commutativa x+y = y+x

x·y = y·x
y x
x
= y

E2) associativa (x + y) + z = x+y+z

(x · y) · z = x·y·z
y
x
x = y
z z

(utile per ridurre il fan-in)

45
 Equivalenze notevoli
E3) distributiva (x · y) + (x · z) = x · (y + z)
(x + y) · (x + z) = x + (y · z)
x x
y
=
N.B.: Questa equivalenza, y
z z
non valida in algebra
«tradizionale», è vera in
(riduzione del numero di gate utilizzati)
algebra binaria. In
generale, in algebra x y z a=x+y b=x+z a·b c=y·z x+c
binaria ogni proprietà è
0 0 0 0 0 0 0 0
duale.
0 0 1 0 1 0 0 0
Verifica con TdV 0 1 0 1 0 0 0 0
0 1 1 1 1 1 1 1
1 0 0 1 1 1 0 1
1 0 1 1 1 1 0 1
1 1 0 1 1 1 0 1
1 1 1 1 1 1 1 1
46
 Equivalenze notevoli
x x x·x
E4) idempotenza x+x = x x
0 0
x·x = x 1 1

x x x·1
E5) identità x+0 = x x
1 0 0
x·1 = x
1 1

x x·0
E6) limite x+1 = 1 x 0
x·0 = 0 0 0 0
1 0

47
 Equivalenze notevoli
Proprietà della complementazione:
x x
E7) involuzione (x’)’ = x
(amplificazione di segnale)

E8) limitazione x + x’ = 1 x
0
x · x’ = 0 x’
x x’ x·x’
0 1 0
1 0 0

x
E9) combinazione xy + xy’ = x y x
(x+y)·(x+y’) = x x
Dim.: y’
xy + xy’ = x (y+y’) (E3 – distributiva)
= x·1 (E8 – limitazione)
=x (E5 – identità)

(prorietà fondamentale ai fini della semplificazione algebrica delle espressioni – lo si analizzerà in seguito) 48
 Equivalenze notevoli
E10) Ia legge di De Morgan (x + y)’ = x’ · y’
IIa legge di De Morgan (x · y)’ = x’ + y’

x x x y (x·y)’ x’ y’ x’+y’
= y 0 0 1 1 1 1
y
0 1 1 1 0 1
1 0 1 0 1 1
x x
= 1 1 0 0 0 0
y y

• utili per determinare espressioni equivalenti utilizzando gate logici diversi, es.
NOR/NAND al posto di AND/OR
• Equivalentemente, le leggi di De Morgan asseriscono che:
x+y = ((x+y)’)’ E7-involuzione
= (x’ · y’)’ E10-De Morgan
• Dunque è possibile sostituire un gate OR con un gate AND (e viceversa)
1. Negando l’uscita
2. Negando tutti gli ingressi

49
 Equivalenze notevoli
E11) consenso xy + x’z + yz = xy + x’z

(x+y)·(x’+z)·(y+z) = (x+y)·(x’+z)

Dimostrazione:

xy + x’z + yz = xy + x’z + yz (x + x’) Limitazione e Identità

= xy + x’z + yzx + yzx’ Distributiva

= xy (1+z) + x’z (1+y) Distributiva

= xy (1) + x’z (1) Limite

= xy + x’z Identità

(prorietà fondamentale ai fini della semplificazione algebrica delle espressioni – lo si analizzerà in seguito) 50
Manipolazione algebrica di espressioni ...
• Lo schema logico relativo all’espressione canonica SP del «riporto» (R) di un Full
Adder richiede 4 «AND» a 3 ingressi ciascuno e, in cascata, 1 «OR» a 4 ingressi e
3 NOT per avere gli ingressi in forma vera e negata.

R = a’ b r + a b’ r + a b r’ + a b r

r’ r a’ a b’ b

51
 Manipolazione algebrica di espressioni ...
• È possibile ottenere una espressione più semplice? Una possibile manipolazione.

R = a’ b r + a b’ r + a b r’ + a b r

= a’ b r + a b’ r + a b (r’ + r) Distrib. (E3)

= a’ b r + a b’ r + a b 1 Limitazione (E8)

= a’ b r + a b’ r + a b Identità (E5)
• È possibile ottenere una semplificazione ulteriore? Ripartiamo da capo applicando una
manipolazione algebrica meno intuitiva.
Formulazione SP originale..

R = a’ b r + a b’ r + a b r’ +abr +abr +abr Idempot. (E4)

= b r (a’ + a) + a r (b’ + b) + a b (r’ + r) Distrib. (E3)

=br1+ar1+ab1 Limitaz. (E8)

=br+ar+ab Identità (E5)

52
... Manipolazione algebrica di espressioni
R=br+ar+ab

a R

1 OR a 4 ingressi 1 OR a 3 ingressi
4 AND a 3 ingressi 3 AND a 2 ingressi
3 NOT
• Come abbiamo visto il procedimento di manipolazione algebrica verso la rete
«di costo minimo» può non essere affatto ovvio
• Il processo di sintesi volto all’ottenimento della rete di costo minimo viene
realizzato mediante opportune metodologie (es. le mappe di Karnaugh, si
vedranno più avanti) 53
 Il problema della sintesi
Funzione Espressioni equivalenti Schemi logici
assegnata

SINTESI: individuazione dell’espressione che fornisce lo schema “migliore” per la

realizzazione della funzione assegnata. «Migliore» può essere definito con criteri
anche opposti tra loro, quali

Rapidità di progetto Massima velocità

Massima flessibilità Minima complessità

54
 Progetto logico di
Rete
programmabile circuiti combinatori

Composizione
ad hoc di
Rapidità di progetto circuiti notevoli

Massima flessibilità

Massima velocità
Rete
di costo
Minima complessità minimo
55