Fondamenti esercitazioni parte3_2012-11-25

FONDAMENTI DI INFORMATICA


ESERCITAZIONI ANNO ACCADEMICO 2012-2013

DOTT. FABRIZIO SOLINAS

Mail: [email protected]


Parte 3.

• Forme Canoniche

• Mappe di Karnaugh

• Ulteriori operatori logici

• Reti combinatorie.

UNIVERSITA' DI CAGLIARI-CORSO DI LAUREA IN INFORMATICA 2


FORME CANONICHE

•  MINTERMINE: PRODOTTO FONDAMENTALE

•  MAXTERMINE: SOMMA FONDAMENTALE


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


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



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


Σ (0,2,3,6,7)

minjx y z

x y z

x y z

x y z

x y z


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


maxj

x + y + z

x + y + z

x + y + z

Π (1,4,5)


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


Π (3,5,6,7)

Σ (0,1,2,4)

f = xý´z´ + xý´z + xýz´ + xy´z´= min0 + min1 + min2 + min4 =

f = (x+y’+z’) · (x’+y+z’) · (x’+y’+z) · (x’+y’+z’) = max3 * max5 * max6 * max7 =


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


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


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

=+=++

=+++

)())((


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.


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 +=),,(


zyzyxxzxyzyx =+=+ )(

xyz+ xyz = (x + x)yz = yz

Espressione minima:


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


ywywzzwzyyzwxx

wzyxwzxyyzwxxyzw

=+=++

=+++

)())((

ywywwzyxf +=),,,(Espressione minima:

ywywzzyzwwzyxx

xyzwyzwxwzxywzyx

=+=++

=+++

)())((


Ulteriori operatori logici PORTA NAND

x y x | y

0 0 1

0 1 1

1 0 1

1 1 0

yxyx ⋅=|


xy

x | y

La porta NAND è funzionalmente completa:

xxx |=

yxyxyyxxyx |)|(|)|( =+⇒=+

)|(|)|( yxyxyx =⋅


Ulteriori operatori Logici PORTA NOR

x y x ↓ y

0 0 1

0 1 0

1 0 0

1 1 0

yxyx +=↓


La porta NOR è funzionalmente completa:

xxx ↓=

yxyxyyxxyx ↓=⋅⇒↓↓↓=⋅ )()(

)()( yxyxyx ↓↓↓=+

xy

x ↓ y


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 +=),,(


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


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 è:


x y z

zx ⋅

zy ⋅

yzzxxy ++


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 ++=



Ulteriori operatori logici La rete corrispondente (è consentito l’uso delle porte NOT).

Rete OR-AND:


x y z

zy +

zx +))()(( zyzxyx +++


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 è:


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)


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.



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 ++=),,,(


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


Ulteriori operatori logici •  Esercizio:disegnare la rete corrispondente (è consentito l’uso delle porte NOT)

Rete AND-OR:


x y z w

zywyx ⋅++⋅

yx ⋅

zy ⋅


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


Half-Adder

bit augendo

bit addendo

xi

yi

si

ci+1

bit somma

bit riporto

iii yxs ⊕=

iii yxc =+1

ix

iy

OR-esclusivo


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


Full-Adder

xi

yi

ci

si

ci+1


Reti combinatorie Full-Adder

•  Il blocco logico del full-adder può essere rappresentato con due half-adder con i riporti posti in OR:


Full-Adder

H-Axi

yi

ci

si

ci+1

ii cy ⊕

H-Aii cy

)( iii cyx ⊕

)( iii cyx ⊕⊕

)( iiiii cyxcy ⊕+


Reti combinatorie •  Esercizio 1: Disegnare il circuito completo del full-adder come somma di due

half-adder.


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


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


xi yi ci

si

iii cyx ⋅⋅

iii cyx ⋅⋅

iii cyx ⋅⋅

iii cyx ⋅⋅



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


xi yi ci

ci+1

ii cy ⋅

ii cx ⋅

ii yx ⋅



disegnare la sua rete combinatoria (fare la sintesi della rete). Circuito completo


xi yi ci

iii cyx ⋅⋅

iii cyx ⋅⋅

iii cyx ⋅⋅

iii cyx ⋅⋅

ii cy ⋅

ii cx ⋅

ii yx ⋅

iiiiiiiiiiiii cyxcyxcyxcyxs +++=

iiiii cycxxyc ++=+1

Fondamenti esercitazioni parte3_2012-11-25

Education

Transcript of Fondamenti esercitazioni parte3_2012-11-25