Post on 28-Jul-2015
FONDAMENTI DI INFORMATICA
FONDAMENTI DI INFORMATICA
ESERCITAZIONI ANNO ACCADEMICO 2012-2013
DOTT. FABRIZIO SOLINAS
Mail: fabrizio.solinas@unica.it
FONDAMENTI DI INFORMATICA
Parte 3.
• Forme Canoniche
• Mappe di Karnaugh
• Ulteriori operatori logici
• Reti combinatorie.
UNIVERSITA' DI CAGLIARI-CORSO DI LAUREA IN INFORMATICA 2
FONDAMENTI DI INFORMATICA
FORME CANONICHE
• MINTERMINE: PRODOTTO FONDAMENTALE
• MAXTERMINE: SOMMA FONDAMENTALE
UNIVERSITA' DI CAGLIARI-CORSO DI LAUREA IN INFORMATICA 3
configurazioni mintermini maxtermini x y z termini designazione termini designazione 0 0 0 x y z min0 x + y + z max0
0 0 1 x y z min1 x + y + z max1
0 1 0 x y z min2 x + y + z max2
0 1 1 x y z min3 x + y + z max3
1 0 0 x y z min4 x + y + z max4
1 0 1 x y z min5 x + y + z max5
1 1 0 x y z min6 x + y + z max6
1 1 1 x y z min7 x + y + z max7
FONDAMENTI DI INFORMATICA
FORME CANONICHE.
• PRIMA FORMA CANONICA: SOMMA DI MINTERMINI [Σ]
• SECONDA FORMA CANONICA: PRODOTTO DI MAXTERMINI [Π]
§ OGNI FUNZIONE BOOLEANA PUO’ ESSERE ESPRESSA COME SOMMA DI MINTERMINI O PRODOTTO DI MAXTERMINI
UNIVERSITA' DI CAGLIARI-CORSO DI LAUREA IN INFORMATICA 4
FONDAMENTI DI INFORMATICA
CIRCUITI LOGICI CIRCUITI LOGICI.
FORME CANONICHE.
ESEMPIO: § DATA LA SEGUENTE TAVOLA DI VERITA’, RICAVARE LA PRIMA FORMA CANONICA.
x y z f(x, y, z)
0 0 0 1
0 0 1 0
0 1 0 1
0 1 1 1
1 0 0 0
1 0 1 0
1 1 0 1
1 1 1 1
UNIVERSITA' DI CAGLIARI-CORSO DI LAUREA IN INFORMATICA 5
Σ (0,2,3,6,7)
minjx y z
x y z
x y z
x y z
x y z
FONDAMENTI DI INFORMATICA
FORME CANONICHE.
ESERCIZIO: § DATA LA SEGUENTE TAVOLA DI VERITA’, RICAVARE LA SECONDA FORMA CANONICA.
x y z f(x, y, z)
0 0 0 1
0 0 1 0
0 1 0 1
0 1 1 1
1 0 0 0
1 0 1 0
1 1 0 1
1 1 1 1
UNIVERSITA' DI CAGLIARI-CORSO DI LAUREA IN INFORMATICA 6
maxj
x + y + z
x + y + z
x + y + z
Π (1,4,5)
FONDAMENTI DI INFORMATICA
FORME CANONICHE. ESERCIZIO:
§ DATA LA SEGUENTE TAVOLA DI VERITA’, RICAVARE PRIMA E SECONDA FORMA CANONICA.
x y z f(x, y, z)
0 0 0 1
0 0 1 1
0 1 0 1
0 1 1 0
1 0 0 1
1 0 1 0
1 1 0 0
1 1 1 0
UNIVERSITA' DI CAGLIARI-CORSO DI LAUREA IN INFORMATICA 7
Π (3,5,6,7)
Σ (0,1,2,4)
f = x´y´z´ + x´y´z + x´yz´ + xy´z´= min0 + min1 + min2 + min4 =
f = (x+y’+z’) · (x’+y+z’) · (x’+y’+z) · (x’+y’+z’) = max3 * max5 * max6 * max7 =
FONDAMENTI DI INFORMATICA
Mappe di Karnaugh • Esempio 1: Data la seguente funzione in prima forma canonica
f (x, y, z, w) = ∑(0, 4, 5, 8, 12, 13, 14, 15), ricavare l’espressione minima attraverso la mappa di Karnaugh.
xy zw 00 01 11 10
00 1 1 1 1
01 0 1 1 0
11 0 0 1 0
10 0 0 1 0
xy zw 00 01 11 10
00 0 4 12 8
01 1 5 13 9
11 3 7 15 11
10 2 6 14 10
UNIVERSITA' DI CAGLIARI-CORSO DI LAUREA IN INFORMATICA 8
x y z w f 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 1 1 0 0 1 0 0 1 0 1 0 1 1 0 1 1 0 0 0 1 1 1 0 1 0 0 0 1 1 0 0 1 0 1 0 1 0 0 1 0 1 1 0 1 1 0 0 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 1
FONDAMENTI DI INFORMATICA
Mappe di Karnaugh. Esempio 2/2. • Esempio: Data la seguente funzione in prima forma canonica:
f (x, y, z, w) = ∑(0, 4, 5, 8, 12, 13, 14, 15) ricavare l’espressione minima attraverso la mappa di Karnaugh.
xy zw 00 01 11 10
00 1 1 1 1
01 1 1
11 1
10 1
xyxyzzzxyxyzww
wxyzxyzwwzxyzwxy
=+=++
=+++
)())((
UNIVERSITA' DI CAGLIARI-CORSO DI LAUREA IN INFORMATICA 9
zyzywwzwywzyxx
wzxywzyxzwxyzwyx
=+=++
=+++
)())((
xyzyzwwzyxf ++=),,,(Espressione minima:
xyzw+ xyzw+ xyzw+ xyzw =
(x + x)(yzw+ yzw) = (y+ y)zw = zw
Illusione Ottica, il soprasegnato si attacca con il soprasegnato successivo. Quindi in questo caso è x’y’z’w’. Così tutti gli altri termini, anche nelle slide successive.
FONDAMENTI DI INFORMATICA
Mappe di Karnaugh. • Esercizio: Data la seguente funzione in prima forma canonica
f (x, y, z) = ∑(1, 2, 5, 6), ricavare l’espressione minima attraverso la mappa di Karnaugh.
xy z 00 01 11 10
0 0 1 1 0
1 1 0 0 1
zyzyzyxf +=),,(
UNIVERSITA' DI CAGLIARI-CORSO DI LAUREA IN INFORMATICA 10
zyzyxxzxyzyx =+=+ )(
xyz+ xyz = (x + x)yz = yz
Espressione minima:
FONDAMENTI DI INFORMATICA
Mappe di Karnaugh • Esercizio: Data la seguente funzione in prima forma canonica
f (x, y, z, w) = ∑(0, 2, 5, 7, 8, 10, 13, 15), ricavare l’espressione minima attraverso la mappa di Karnaugh.
xy zw 00 01 11 10
00 1 0 0 1
01 0 1 1 0
11 0 1 1 0
10 1 0 0 1
UNIVERSITA' DI CAGLIARI-CORSO DI LAUREA IN INFORMATICA 11
ywywzzwzyyzwxx
wzyxwzxyyzwxxyzw
=+=++
=+++
)())((
ywywwzyxf +=),,,(Espressione minima:
ywywzzyzwwzyxx
xyzwyzwxwzxywzyx
=+=++
=+++
)())((
FONDAMENTI DI INFORMATICA
Ulteriori operatori logici PORTA NAND
x y x | y
0 0 1
0 1 1
1 0 1
1 1 0
yxyx ⋅=|
UNIVERSITA' DI CAGLIARI-CORSO DI LAUREA IN INFORMATICA 12
xy
x | y
La porta NAND è funzionalmente completa:
xxx |=
yxyxyyxxyx |)|(|)|( =+⇒=+
)|(|)|( yxyxyx =⋅
FONDAMENTI DI INFORMATICA
Ulteriori operatori Logici PORTA NOR
x y x ↓ y
0 0 1
0 1 0
1 0 0
1 1 0
yxyx +=↓
UNIVERSITA' DI CAGLIARI-CORSO DI LAUREA IN INFORMATICA 13
La porta NOR è funzionalmente completa:
xxx ↓=
yxyxyyxxyx ↓=⋅⇒↓↓↓=⋅ )()(
)()( yxyxyx ↓↓↓=+
xy
x ↓ y
FONDAMENTI DI INFORMATICA
Ulteriori operatori logici • Esercizio: Data la seguente tabella di verità ricavare la funzione tramite le
mappe di Karnaugh e disegnare la rete corrispondente (è consentito l’uso delle porte NOT).
xy z 00 01 11 10
0 0 0 1 1
1 0 1 1 0
yzzxzyxf +=),,(
UNIVERSITA' DI CAGLIARI-CORSO DI LAUREA IN INFORMATICA 14
x y z f
0 0 0 0
0 0 1 0
0 1 0 0
0 1 1 1
1 0 0 1
1 0 1 0
1 1 0 1
1 1 1 1
FONDAMENTI DI INFORMATICA
Ulteriori operatori logici • Esercizio: Data la seguente funzione in prima forma canonica
f (x, y, z) = ∑(3, 4, 6, 7) disegnare la rete corrispondente (è consentito l’uso delle porte NOT)
Rete AND-OR è:
UNIVERSITA' DI CAGLIARI-CORSO DI LAUREA IN INFORMATICA 15
x y z
zx ⋅
zy ⋅
yzzxxy ++
FONDAMENTI DI INFORMATICA
Ulteriori operatori logici
• Esercizio: ricavare la seconda forma canonica.
xy z 00 01 11 10
0 0 0 1 1
1 0 1 1 0 ))((),,( zyzxzyxf ++=
UNIVERSITA' DI CAGLIARI-CORSO DI LAUREA IN INFORMATICA 16
FONDAMENTI DI INFORMATICA
Ulteriori operatori logici La rete corrispondente (è consentito l’uso delle porte NOT).
Rete OR-AND:
UNIVERSITA' DI CAGLIARI-CORSO DI LAUREA IN INFORMATICA 17
x y z
zy +
zx +))()(( zyzxyx +++
FONDAMENTI DI INFORMATICA
Ulteriori operatori logici • Esercizio 4: disegnare la rete NOR-NOR corrispondente (è consentito l’uso delle
porte NOT) alla funzione dell’esercizio precedente.
La rete NOR-NOR è:
UNIVERSITA' DI CAGLIARI-CORSO DI LAUREA IN INFORMATICA 18
x y z
zy ↓
zx ↓)()()( zyzxyx ↓↓↓↓↓
f (x, y, z) = (x + y)(y+ z)
f (x, y, z) = (x + y)↓(y+ z)
f (x, y, z) = (x↓ y)↓(y↓ z)
f (x, y, z) = (x↓ y)↓(y↓ z)
FONDAMENTI DI INFORMATICA
Ulteriori operatori logici
• Remainder: § Se vi viene chiesto un circuito con sole NAND utilizzare la
prima forma canonica.
§ Se vi viene chiesto un circuito con sole NOR utilizzare la seconda forma canonica.
UNIVERSITA' DI CAGLIARI-CORSO DI LAUREA IN INFORMATICA 19
FONDAMENTI DI INFORMATICA
Ulteriori operatori logici • Esercizio: Data la seguente tabella di verità ricavare la
funzione tramite le mappe di Karnaugh e disegnare la rete corrispondente (è consentito l’uso delle porte NOT).
xy zw 00 01 11 10
00 1 0 0 1
01 1 1 1 1
11 1 1 1 1
10 1 0 0 0
yzxywwzyxf ++=),,,(
UNIVERSITA' DI CAGLIARI-CORSO DI LAUREA IN INFORMATICA 20
x y z w f 0 0 0 0 1 0 0 0 1 1 0 0 1 0 1 0 0 1 1 1 0 1 0 0 0 0 1 0 1 1 0 1 1 0 0 0 1 1 1 1 1 0 0 0 1 1 0 0 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
FONDAMENTI DI INFORMATICA
Ulteriori operatori logici • Esercizio:disegnare la rete corrispondente (è consentito l’uso delle porte NOT)
Rete AND-OR:
UNIVERSITA' DI CAGLIARI-CORSO DI LAUREA IN INFORMATICA 21
x y z w
zywyx ⋅++⋅
yx ⋅
zy ⋅
FONDAMENTI DI INFORMATICA
Reti combinatorie Half-Adder
xi yi si ci+1
0 0 0 0
0 1 1 0
1 0 1 0
1 1 0 1
UNIVERSITA' DI CAGLIARI-CORSO DI LAUREA IN INFORMATICA 22
Half-Adder
bit augendo
bit addendo
xi
yi
si
ci+1
bit somma
bit riporto
iii yxs ⊕=
iii yxc =+1
ix
iy
OR-esclusivo
FONDAMENTI DI INFORMATICA
Reti combinatorie Full-Adder
xi yi ci si ci+1
0 0 0 0 0
0 0 1 1 0
0 1 0 1 0
0 1 1 0 1
1 0 0 1 0
1 0 1 0 1
1 1 0 0 1
1 1 1 1 1
UNIVERSITA' DI CAGLIARI-CORSO DI LAUREA IN INFORMATICA 23
Full-Adder
xi
yi
ci
si
ci+1
FONDAMENTI DI INFORMATICA
Reti combinatorie Full-Adder
• Il blocco logico del full-adder può essere rappresentato con due half-adder con i riporti posti in OR:
UNIVERSITA' DI CAGLIARI-CORSO DI LAUREA IN INFORMATICA 24
Full-Adder
H-Axi
yi
ci
si
ci+1
ii cy ⊕
H-Aii cy
)( iii cyx ⊕
)( iii cyx ⊕⊕
)( iiiii cyxcy ⊕+
FONDAMENTI DI INFORMATICA
Reti combinatorie • Esercizio 1: Disegnare il circuito completo del full-adder come somma di due
half-adder.
UNIVERSITA' DI CAGLIARI-CORSO DI LAUREA IN INFORMATICA 25
ix
iy ii cy ⊕
ii cy
)( iiii cyxs ⊕⊕=
)( iii cyx ⊕)(1 iiiiii cyxcyc ⊕+=+
ic
• La realizzazione fisica della porta XOR non è semplice come quella della NAND e della NOR
FONDAMENTI DI INFORMATICA
Reti combinatorie • Esercizio 2: Partendo dal blocco logico e dalla tabella di verità del full-adder,
disegnare la sua rete combinatoria (fare la sintesi della rete). Mappa e circuito per l’output si
iiiiiiiiiiiii cyxcyxcyxcyxs +++=
xiyi ci 00 01 11 10
0 0 1 0 1
1 1 0 1 0
UNIVERSITA' DI CAGLIARI-CORSO DI LAUREA IN INFORMATICA 26
xi yi ci
si
iii cyx ⋅⋅
iii cyx ⋅⋅
iii cyx ⋅⋅
iii cyx ⋅⋅
FONDAMENTI DI INFORMATICA
Reti combinatorie • Esercizio 2: Partendo dal blocco logico e dalla tabella di verità del full-adder,
disegnare la sua rete combinatoria (fare la sintesi della rete). Mappa e circuito per l’output ci+1
iiiii cycxxyc ++=+1
xiyi ci 00 01 11 10
0 0 0 1 0
1 0 1 1 1
UNIVERSITA' DI CAGLIARI-CORSO DI LAUREA IN INFORMATICA 27
xi yi ci
ci+1
ii cy ⋅
ii cx ⋅
ii yx ⋅
FONDAMENTI DI INFORMATICA
Reti combinatorie • Esercizio 2: Partendo dal blocco logico e dalla tabella di verità del full-adder,
disegnare la sua rete combinatoria (fare la sintesi della rete). Circuito completo
UNIVERSITA' DI CAGLIARI-CORSO DI LAUREA IN INFORMATICA 28
xi yi ci
iii cyx ⋅⋅
iii cyx ⋅⋅
iii cyx ⋅⋅
iii cyx ⋅⋅
ii cy ⋅
ii cx ⋅
ii yx ⋅
iiiiiiiiiiiii cyxcyxcyxcyxs +++=
iiiii cycxxyc ++=+1