Logica combinatoriaberaldi/calcolatori05-06/logica1.pdf · Reti logiche Introduzione • Sono...
52
Logica combinatoria prima parte
Transcript of Logica combinatoriaberaldi/calcolatori05-06/logica1.pdf · Reti logiche Introduzione • Sono...
Logi
ca c
ombi
nat
oria
prim
a pa
rte
Ret
i log
ich
e In
trod
uzi
one
•So
no s
iste
mi e
lett
roni
ci n
ei q
uali
le g
rand
ezze
ele
ttric
he in
gio
co
rapp
rese
ntan
o il
valo
re lo
gico
0 o
ppur
e 1
•Re
ti co
mbi
nato
rie
–Re
aliz
zano
una
fun
zion
e f:
{0,
1}n
{0,1
}m
•Re
ti Se
quen
zial
i –
L’ in
gres
so e
d l’u
scita
son
o de
finite
da
sequ
enze
•E’
impl
icito
il c
once
tto
di t
empo
x 0
,x1,
..,x k
–Il
valo
re a
ttua
le d
ell’u
scita
Y(k
) di
pend
e da
ll’in
gres
so a
ttua
le, X
(k),
e
da u
n nu
mer
o fin
ito d
i val
ori p
rece
dent
i X(k
-1),
..,X(
j)–
Equi
vale
ntem
ente
, Y(k
) di
pend
e da
ll’in
gres
so e
dal
lo s
tato
, S(k
), a
ttua
li
Calc
olat
ori E
lett
roni
ci,B
eral
di, a
.a. 0
5/06
Alg
ebra
di c
omm
uta
zion
e
•In
siem
e di
ele
men
ti A
={0
,1}
•Ope
razi
oni
NO
T(o
pera
tore
unar
io)
=
> 1
= 0
e
0
= 1
AN
D(b
inar
io)
=>
0
·0
= 0
·1
= 1
·0
= 0
e
1
·1=
1
OR
(bin
ario
) =
> 0
+ 0
=
0
e 0
+ 1
= 1
+ 0
= 1
+ 1
= 1
Alge
bra
bool
eana
per
un in
siem
e di
due
val
ori
Calc
olat
ori E
lett
roni
ci,B
eral
di, a
.a. 0
5/06
Un
a se
mpl
ice
appl
icaz
ion
e
•Va
riabi
le d
i con
trol
lo:
X–
due
valo
ri:
•X=
0 ->
inte
rrut
tore
ape
rto
•X=
1 ->
inte
rrut
tore
chi
uso
•U
scita
Y–
Due
sta
ti:•
Lam
padi
na s
pent
a (Z
=0)
•La
mpa
dina
acc
esa
(Z=
1)
X=0
Z=0
Z =
X
X=1
Z=1
Calc
olat
ori E
lett
roni
ci,B
eral
di, a
.a. 0
5/06
Mod
ello
logi
co
AND
OR
Z =
X1 A
ND
X2
X1X2
X1
X2
Z =
X1 O
R X
2
Z
Z
Calc
olat
ori E
lett
roni
ci,B
eral
di, a
.a. 0
5/06
Alt
ro e
sem
pio
Logi
ca p
osit
iva
e n
egat
iva
Pri
nci
pali
prop
riet
à
Calc
olat
ori E
lett
roni
ci,B
eral
di, a
.a. 0
5/06
Le p
rin
cipa
li po
rte
logi
che
Calc
olat
ori E
lett
roni
ci,B
eral
di, a
.a. 0
5/06
Com
port
amen
to e
ster
no
idea
lizza
toEs
empi
o: p
orta
AN
D, l
ogic
a po
siti
va…
0 0
0
011 1
1
00
01
A B X
A B X
tempo
Calc
olat
ori E
lett
roni
ci,B
eral
di, a
.a. 0
5/06
Fun
zion
e di
com
mu
tazi
one
•Si
a x i
una
varia
bile
di c
omm
utaz
ione
ed
x=(x
1,x 2
,…,x
n) il
vet
tore
co
mpo
sto
da n
var
iabi
li bi
narie
x i∈
{0,1
},
x ∈
{0,1
}n
•Si
def
inis
ce f
un
zion
e di
com
mu
tazi
one
ad n
var
iabi
li la
fun
zion
e y=
f(x)
, dov
e f:
{0,
1}n
→{0
,1}
•Ta
bella
di v
erità
. La
funz
ione
può
ess
ere
defin
ita m
edia
nte
una
legg
e ch
e as
soci
a ad
ogn
una
delle
pos
sibi
le 2
n n-
ple
il va
lore
del
l’usc
ita
Calc
olat
ori E
lett
roni
ci,B
eral
di, a
.a. 0
5/06
Fun
zion
i di c
omm
uta
zion
eR
ealiz
zazi
one
med
ian
te r
ete
com
bin
ator
ia
•Al
cune
fun
zion
i di c
omm
utaz
ione
ele
men
tari
sono
rea
lizza
te m
edia
nte
port
e lo
gich
e•
Altr
e fu
nzio
ni s
ono
real
izza
te c
ompo
nend
o le
por
te d
i bas
e, f
orm
ando
co
si u
na r
ete
com
bina
toria
RETE
COMB
INAT
ORIA
RETE
COMB
INAT
ORIA
x 1 x 2 …
x n
y
Calc
olat
ori E
lett
roni
ci,B
eral
di, a
.a. 0
5/06
Tabe
lla d
i ver
ità
•U
na f
unzi
one
di c
omm
utaz
ione
può
ess
ere
defin
ita m
edia
nte
la t
abel
la
di v
erità
, oss
ia u
n el
enco
dei
val
ori d
i y p
er o
gni a
sseg
nazi
one
di v
erità
2nas
segn
azio
ni d
i ver
ità
nva
riabi
liva
lori
della
fun
zion
e
11
1
10
1
11
0
00
0x 2x 1
y
. . .
Calc
olat
ori E
lett
roni
ci,B
eral
di, a
.a. 0
5/06
Nu
mer
o di
fu
nzi
oni
•n
varia
bili
bina
rie =
> m
=2n
asse
gnaz
ioni
div
erse
di v
alor
i.
•fu
nzio
ne =
ass
egna
re m
val
ori d
i ver
ità (
0,1)
=>
2m
asse
gnaz
ioni
di
vers
e
n
2n
22n
Calc
olat
ori E
lett
roni
ci,B
eral
di, a
.a. 0
5/06
Fun
zion
i un
arie
10y 2
01y 1
00y 0
11
10
y 3x
y 0 :
funz
ione
0y 1
: ne
gazi
one
(NO
T)y 2
: fu
nzio
ne id
entit
ày 3
: fu
nzio
ne 1
xy
Calc
olat
ori E
lett
roni
ci,B
eral
di, a
.a. 0
5/06
Fun
zion
i bin
arie
0000y 0
0001y 1
0010y 2
0011y 3
0100y 4
0101y 5
0110y 6
0111y 7
1000y 8
1001y 9
1010y 10
1011y 11
1100Y 12
1101y 13
1110y 14
1111y 15
01 10 1100x 2x 1
x 1
yx 2
AND
ORNO
Tx 2
NOTx 1
01
ORAN
D
Calc
olat
ori E
lett
roni
ci,B
eral
di, a
.a. 0
5/06
An
alis
i e S
inte
si FUN
ZIO
NE
DI
COM
MU
TAZI
ON
E
RET
E CO
MBI
NAT
ORIASi
ntesi
Anali
si
Calc
olat
ori E
lett
roni
ci,B
eral
di, a
.a. 0
5/06
An
alis
i
•H
a co
me
obie
ttiv
o la
des
criz
ione
dei
val
ori d
ell’u
scita
in f
unzi
one
degl
i in
gres
si (
tabe
lla v
erità
o in
for
ma
chiu
sa)
X0
X1 X2
X3
X2X
3
X0+
X1
(X2X
3)
(X0+
X1)
(X2X
3)
Y=
(X
0+
X1)
(X
2X
3)
Calc
olat
ori E
lett
roni
ci,B
eral
di, a
.a. 0
5/06
Esem
pio
Calc
olat
ori E
lett
roni
ci,B
eral
di, a
.a. 0
5/06
Esem
pio
Calc
olat
ori E
lett
roni
ci,B
eral
di, a
.a. 0
5/06
Form
e ca
non
ich
e
•In
gen
eral
e un
a fu
nzio
ne p
uò e
sser
e es
pres
sa u
sand
o di
vers
ees
pres
ssio
ni
•Es
iste
un’
espr
essi
one
“sta
ndar
d” p
er d
efin
ire u
na
qual
unqu
e fu
nzio
ne?
•Si
, 2 f
orm
e: S
omm
a di
Pro
dott
i (SP
) e
la d
uale
Pro
dott
o di
Som
me
(PS)
Calc
olat
ori E
lett
roni
ci,B
eral
di, a
.a. 0
5/06
Min
term
ine
•U
n m
inte
rmin
em
idi
n v
aria
bili,
è u
na f
unzi
one
che
vale
1 s
olo
in
corr
ispo
nden
za d
ell’a
sseg
nam
ento
di v
erità
i. E
’ il p
rodo
tto
di t
utte
le
varia
bili
dire
tte
o ne
gate
m13
=x 4
x3 x 2
x1
•Q
ualu
nque
fun
zion
e è
espr
imib
ile c
ome
som
ma
deim
inte
rmin
iper
cui
y
= 1
k|f(
k)=1
f(x 1
,.., x
n)=
Σm
k
Calc
olat
ori E
lett
roni
ci,B
eral
di, a
.a. 0
5/06
Esem
pio
•y=
f(x1
,x2,
x3)
è 1
se e
sol
o se
il n
umer
o di
var
iabi
li co
n va
lore
1 è
pari
y =
m0+
m3+
m5+
m6 =Σ(
0,3,
5,6)
m3
m0
m5
m6
0 1 2 3 4 5 6 70
11
1
10
11
11
01
00
01
11
10
00
10
01
00
10
00x 3
x 2x 1
y
f(x 1
,x2,x
3) =
x3
x 2x 1
+ x
3x2x
1+
x 3x 2
x 1 +
x 3x 2
x 1Ca
lcol
ator
i Ele
ttro
nici
,Ber
aldi
, a.a
. 05/
06
Ver
ific
a…
•U
n m
inte
rmin
eva
le 1
sol
o pe
r un
a pa
rtic
olar
e as
segn
azio
ne d
i val
ori
alle
var
iabi
li (m
i=1
f(i)=
1)
m3
m0
m5
m6
y =Σ
(0,3
,5,6
)
00
00
10
00
01
00
00
00
00
10
00
00
00
00
00
01
01
11
10
11
11
01
00
01
11
10
00
10
01
00
10
00
0 1 2 3 4 5 6 7
x 3x 2
x 1
y
Calc
olat
ori E
lett
roni
ci,B
eral
di, a
.a. 0
5/06
Sin
tesi
Fo
rma
can
onic
a SP
•U
na f
unzi
one
Ydi
n v
aria
bili
espr
essa
com
eso
mm
aca
noni
ca p
uò
esse
re r
ealiz
zata
med
iant
e 2
livel
li di
logi
ca (
AND
e O
R)
Y =Σ(
1,5,
6)
X0
X1 X2
X0 X1
X2
X0
X1
X2
Y
Ret
e A
ND
in O
R
1 5 6
001
101
110
Calc
olat
ori E
lett
roni
ci,B
eral
di, a
.a. 0
5/06
Esem
pio
•D
iseg
nare
un
circ
uito
in f
orm
a SP
che
rea
lizzi
la s
egue
nte
tabe
lla d
i ver
ità (
funz
ione
di m
aggi
oran
za)
Calc
olat
ori E
lett
roni
ci,B
eral
di, a
.a. 0
5/06
Esem
pio
–fu
nzi
one
di m
aggi
oran
za
Calc
olat
ori E
lett
roni
ci,B
eral
di, a
.a. 0
5/06
Max
term
ine
•U
n m
axte
rmin
e M
i di n
var
iabi
li è
una
funz
ione
che
val
e 0
solo
in
corr
ispo
nden
za d
ell’a
sseg
nam
ento
di v
erità
i. E
’ la
som
ma
di t
utte
le
varia
bili
dire
tte
o ne
gate
M2=
x 4 +
x 3 +
x 2 +
x 1
•U
na f
unzi
one
è es
prim
ibile
com
e pr
odot
to d
ei m
axte
rmin
iper
cui
y=
0
k|f(
k)=0
f(x 1
,.., x
n)=
ΠM
k
Calc
olat
ori E
lett
roni
ci,B
eral
di, a
.a. 0
5/06
Esem
pio
•y=
f(x 1
,x2,
x 3)
è 1
se e
sol
o se
il n
umer
o di
var
iabi
li co
n va
lore
1 è
par
i
M2
M1 M4
M7
y =
M1M
2M4M
7=
Π(1
,2,4
,7)
f(x 1
,x2,x
3) =
(x3+
x 2+
x 1) (
x 3 +
x 2 +
x 1) (
x3 +x
2 +x
1 ))
( x3 +
x 2 +
x 1)
01
11
10
11
11
01
00
01
11
10
00
10
01
00
10
00
0 1 2 3 4 5 6 7
x 3x 2
x 1
y
001 0
10 10
0 111
Calc
olat
ori E
lett
roni
ci,B
eral
di, a
.a. 0
5/06
Ver
ific
a…
•U
n m
axte
rmin
eva
le 0
sol
o pe
r un
a pa
rtic
olar
e as
segn
azio
ne d
i val
ori
alle
var
iabi
li
M2
M1
M4
M7
y =Π
(1,2
,4,7
)
01
11
11
11
11
11
10
11
11
11
11
01
11
10
11
11
M2
M1 M4
M7
01
11
10
11
11
01
00
01
11
10
00
10
01
00
10
00
0 1 2 3 4 5 6 7
x 3x 2
x 1
y
Calc
olat
ori E
lett
roni
ci,B
eral
di, a
.a. 0
5/06
Map
pe d
i Kar
nau
gh (
MK
)
•U
sate
al p
iù p
er 5
var
iabi
li di
com
mut
azio
ne
•So
no s
imili
alle
tab
elle
di v
erità
per
ché
pres
enta
no t
utti
i pos
sibi
li va
lori
degl
i ing
ress
i e la
cor
rispo
nden
te u
scita
•Fa
cilit
ano
lam
inim
izza
zion
e: le
cas
elle
son
o nu
mer
ate
in m
odo
che
due
case
lle a
diac
enti
(ver
tical
men
te o
oriz
zont
alm
ente
) di
ffer
isca
no p
er
un s
olo
bit
•E’
pos
sibi
le o
pera
re la
sem
plifi
cazi
one
“ad
occh
io”:
gru
ppi d
i cas
elle
ad
iace
nti c
on v
alor
e 1
corr
ispo
ndon
o a
term
ini s
empl
ifica
bili
φ x
+ φ
x =
φ
Map
pe d
i Kar
nau
ghpe
r 3
e 4
var
iabi
li di
com
mu
tazi
one
01
45
Y 000
01X1
X0
1X
2
32
76
1110
01
45
Y
0000
01
01X
3 X
2
32
76
1110
1213
89
11 1015
1411
10
X1
X0
Eser
cizi
oIm
pieg
o di
MK
10
11
01
10
10
01
11
01
1010
01
1
01
0
00
0
00
00 1 2 3 4 5 6 7
A
B
C
Y
Tabe
lla di
verità
A B C A B C A B C
m 4 m 5 m 7
Y
Eser
cizi
o
10
11
01
10
10
01
11
01
1010
01
1
01
0
00
0
00
00 1 2 3 4 5 6 7
A
B
C
Y
Tabe
lla di
verità
A B C A B C A B C
m 4 m 5 m 6
Y
Calc
olat
ori E
lett
roni
ci,B
eral
di, a
.a. 0
5/06
Solu
zion
e
10
11
01
10
10
01
11
01
1010
01
1
01
0
00
0
00
00 1 2 3 4 5 6 7
A
B
C
Y
11
1
A B
C00
0
1
11
10
0 1
A B
C+ A
B C
A
B
A B
C+A
B C
A
C
Y=A
C+A
B
A B C
Calc
olat
ori E
lett
roni
ci,B
eral
di, a
.a. 0
5/06
Con
dizi
oni d
i in
diff
enza
•In
alc
uni c
asi l
’usc
ita d
i una
r.c
. è d
efin
ita s
olo
per
un s
otto
insi
eme
dei
poss
ibili
ingr
essi
, son
o ci
oè f
unzi
oni p
arzi
alm
ente
spe
cific
ate
•I
valo
ri d’
ingr
esso
per
cui
non
è d
efin
ita l’
usci
ta (
quin
di è
irril
evan
te c
he
essa
sia
0 o
ppur
e 1)
son
o “c
ondi
zion
i di i
ndiff
eren
za”
(don
’t ca
re
cond
ition
)
Por
te u
niv
ersa
li
•Co
n le
tre
por
te (
NO
T, A
ND
, OR)
può
esse
re r
ealiz
zata
qua
lunq
ue
funz
ione
(in
siem
e co
mpl
eto)
•N
on è
min
imo:
l’op
erat
ore
AND
(O
R)
è rid
onda
nte
•Le
por
te N
AND
ed
NO
R s
olo
le (
unic
he)
port
e un
iver
sali
poic
hé
med
iant
e es
se p
uò e
sser
e re
aliz
zata
qua
lunq
ue f
unzi
one
bina
ria
Calc
olat
ori E
lett
roni
ci,B
eral
di, a
.a. 0
5/06
Rea
lizza
zion
e N
OT,
AN
D,O
R
Calc
olat
ori E
lett
roni
ci,B
eral
di, a
.a. 0
5/06
Sin
tesi
con
por
te u
niv
ersa
li
•SP
: Le
por
te A
ND
e la
OR
sono
sos
titui
te c
on N
AND
•PS
: Le
por
te O
R e
la A
ND
son
o so
stitu
ite c
on N
OR
Calc
olat
ori E
lett
roni
ci,B
eral
di, a
.a. 0
5/06
=
=
=
=
Calc
olat
ori E
lett
roni
ci,B
eral
di, a
.a. 0
5/06
==
=
=
Calc
olat
ori E
lett
roni
ci,B
eral
di, a
.a. 0
5/06
Esem
pio
y=Σ(
1,5
,6)
X0
X1
X2 X0
X1
X2
X0
X1
X2
Y
Ret
e A
ND
in O
R
1 5 6
X0
X1 X2 X0 X1
X2
X0
X1
X2
Y
Ret
e N
AN
Din
NA
ND
1 5 6
Calc
olat
ori E
lett
roni
ci,B
eral
di, a
.a. 0
5/06
Sin
tesi
a 2
live
lli (
form
e ca
non
ich
e)
•U
na q
ualu
nque
fun
zion
e di
com
mut
azio
ne p
uò e
sser
e re
aliz
zata
con
2 liv
elli
di p
orte
sec
ondo
le s
egue
nti s
trut
ture
•So
mm
a di
Pro
dott
i(SP
)–
AND
in O
R–
NAN
D in
NAN
D
•P
rodo
tti d
i Som
me
(PS)
–O
R in
AN
D–
NO
R in
NO
R
Calc
olat
ori E
lett
roni
ci,B
eral
di, a
.a. 0
5/06
La p
orta
XO
R
Port
a lo
gica
XO
R
01
10
X0
X1
Y
00
1X
0
1X
10 0 0 1 01 1 1
0110
Calc
olat
ori E
lett
roni
ci,B
eral
di, a
.a. 0
5/06
La p
orta
XN
OR
Port
a lo
gica
XN
OR
10
01
X0
X1
Y
00
1X
0
1X
10 0 0 1 01 1 1
0 11 0
Calc
olat
ori E
lett
roni
ci,B
eral
di, a
.a. 0
5/06
Ope
rato
reSi
mbo
loPr
oprie
tà
NO
Ty=
1 se
e s
olo
se x
=0
AND
y=x 1
x 2y=
1 se
e s
olo
se x
1=x 2
=1
OR
y=x 1
+x 2
y=0
se e
sol
o se
x1=
x 2=
0
NAN
Dy=
x 1/x
2y=
0 se
e s
olo
se x
1=x 2
=1
NO
Ry=
x↓x
2y=
1 se
e s
olo
se x
1=x 2
=0
XOR
y =
x1⊕
x 2y=
1 se
e s
olo
se x
1≠x 2
XNO
Ry=
x1≡
x 2y=
1 se
e s
olo
se x
1=x 2
y=x
Rie
pilo
go
Calc
olat
ori E
lett
roni
ci,B
eral
di, a
.a. 0
5/06
![proporzionalità diretta e inversa [modalità compatibilità] · Grandezze costanti Grandezze che mantengono sempre lo stesso valore Sono grandezze costanti: ... Consideriamo due](https://static.fdocumenti.com/doc/165x107/5c6835d409d3f2ff5a8d29ba/proporzionalita-diretta-e-inversa-modalita-compatibilita-grandezze-costanti.jpg)
