Probleme Rezolvate Electronica
11
Lect ¸ia 6 Algebr˘ a Boolean˘ a Nr. Axioma/Teorema Forma cu operatorul AND OR 1 Axioma 1. Mult ¸imea B={0, 1} este ˆ ınchis˘ aˆ ın raport cu operatorii AND ¸ si OR ∀x, y ∈ B ⇒ x · y ∈ B ∀x, y ∈ B ⇒ (x + y) ∈ B 2 Axioma 2. Asociativitatea x · (y · z)=(x · y) · z x +(y + z)=(x + y)+ z 3 Axioma 3. Comutativitatea x · y = y · x x + y = y + x 4 Axioma 4. Distributivitatea x · (y + z)= x · y + x · z x +(y · z)=(x + y) · (x + z) 5 Axioma 5. Existent ¸a elementului neutru x · 1=1 · x = x x +0=0+ x = x 6 Axioma 6. Existent ¸a complementului x · x = x · x =0 x + x = x + x =1 7 Teorema 1. Idempotent ¸a (tautologia) x · x = x x + x = x 8 Teorema 2. Legea lui 0 ¸ si a lui 1 x · 0=0 · x =0 x +1=1+ x =1 9 Teorema 3. Dubla negat ¸ie (involut ¸ia) x = x x = x 10 Teorema 4. Absorbt ¸iadirect˘a Absorbt ¸ia invers˘ a x · (x + y)= x x · ( x + y)= x · y x + x · y = x x + x · y = x + y 11 Teorema 5. Teorema lui DeMorgan x · y = x + y (x + y)= x · y 1. Determinat ¸i ¸ si justificat ¸i valoarea de adev˘ar a fiec˘arei afirmat ¸ii: a) W · X + Y + Z =(W + Y + Z ) · (X + Y + W · Z + W · Z ) b) X · Y + X · Y = X c) X + X · Y = X + Y d) X · ( X + Y )= X · Y e) (A ⊕ B) · C =(A · B) ⊕ (B · C) f) Z · X + Y + W · X · Y · Z =(X + Y + Z ) · ( X + Y + Z ) · (Z + W + Y ) g) X · Y + Y · Z + X · Z = X · Y + Y · Z + X · Z h) X · Z + Y =(X + Y + Z ) · ( X + Y + Z ) Solut ¸ie a)Expresia din partea dreapt˘a devine, dup˘a aplicarea A4: (W + Y + Z ) · (X + Y + W · Z + W · Z )=(W + Y + Z ) · (X + Y + Z · (W + W )= Utilizˆand A6 ¸ si dup˘a aplicarea A4: =(W + Y + Z ) · (X + Y + Z )= W · X + W · Y + W · Z + Y · X + Y · Y + Y · Z + Z · X + Z · Y + Z · Z = W · X + Y + Z · Y + Z + W · Z + X · Z = utilizˆand T4 expresia devine egal˘a cu expresia din partea stˆang˘ a: = W · X + Y + Z b) Prin aplicarea A4 ¸ siutilizˆand A6, expresia din partea stˆang˘ a devine: X · Y + X · Y = X · (Y + Y )= X c) Prin aplicarea T4 este justificat˘a valoarea de adev˘ar a urm˘atoarei afirmat ¸ii: X + X · Y = X + Y d) Prin aplicarea A4 ¸ si ulterior A6 expresiei din partea stˆang˘ a, aceasta devine egal˘a cu expresia din partea dreapt˘a: X · ( X + Y )= X · X + X · Y = X · Y 1
description
resolved problems in digital electronic
Transcript of Probleme Rezolvate Electronica
Lectia 6
Algebra Booleana
Nr. Axioma/Teorema Forma cu operatorulAND OR
1 Axioma 1. Multimea B={0, 1} este ınchisa ınraport cu operatorii AND si OR
∀x, y ∈ B ⇒ x · y ∈ B ∀x, y ∈ B ⇒ (x+ y) ∈ B
2 Axioma 2. Asociativitatea x · (y · z) = (x · y) · z x+ (y + z) = (x+ y) + z3 Axioma 3. Comutativitatea x · y = y · x x+ y = y + x4 Axioma 4. Distributivitatea x · (y + z) = x · y + x · z x+(y · z) = (x+ y) · (x+ z)5 Axioma 5. Existenta elementului neutru x · 1 = 1 · x = x x+ 0 = 0 + x = x6 Axioma 6. Existenta complementului x · x = x · x = 0 x+ x = x+ x = 17 Teorema 1. Idempotenta (tautologia) x · x = x x+ x = x8 Teorema 2. Legea lui 0 si a lui 1 x · 0 = 0 · x = 0 x+ 1 = 1 + x = 19 Teorema 3. Dubla negatie (involutia) x = x x = x10 Teorema 4. Absorbtia directa
Absorbtia inversax · (x+ y) = xx · (x+ y) = x · y
x+ x · y = xx+ x · y = x+ y
11 Teorema 5. Teorema lui DeMorgan x · y = x+ y (x+ y) = x · y
1. Determinati si justificati valoarea de adevar a fiecarei afirmatii:a) W ·X + Y + Z = (W + Y + Z) · (X + Y +W · Z +W · Z)b) X · Y +X · Y = Xc) X +X · Y = X + Yd) X · (X + Y ) = X · Ye) (A⊕B) · C = (A ·B)⊕ (B · C)f) Z ·X + Y +W ·X · Y · Z = (X + Y + Z) · (X + Y + Z) · (Z +W + Y )g) X · Y + Y · Z +X · Z = X · Y + Y · Z +X · Zh) X · Z + Y = (X + Y + Z) · (X + Y + Z)
Solutie
a)Expresia din partea dreapta devine, dupa aplicarea A4:(W + Y + Z) · (X + Y +W · Z +W · Z) = (W + Y + Z) · (X + Y + Z · (W +W ) =Utilizand A6 si dupa aplicarea A4:= (W + Y + Z) · (X + Y + Z) = W ·X +W · Y +W · Z + Y ·X + Y · Y + Y · Z + Z · X + Z · Y + Z · Z =W ·X + Y + Z · Y + Z +W · Z +X · Z =utilizand T4 expresia devine egala cu expresia din partea stanga:= W ·X + Y + Z
b) Prin aplicarea A4 si utilizand A6, expresia din partea stanga devine:X · Y +X · Y = X · (Y + Y ) = X
c) Prin aplicarea T4 este justificata valoarea de adevar a urmatoarei afirmatii: X +X · Y = X + Y
d) Prin aplicarea A4 si ulterior A6 expresiei din partea stanga, aceasta devine egala cu expresia din parteadreapta: X · (X + Y ) = X ·X +X · Y = X · Y
1
2. Utilizand axiomele si teoremele algebrei Booleene, sa se demonstreze urmatoarele identitati:a) B +A · C = (A+B + C) · (A+B + C) · (A+B + C)b) A ·D + C ·D +A ·B = A · C ·D +A · C ·D +A ·B · C +A ·B · C +A · C ·Dc) D · (A+B + C +D) · (A+B + C +D) = (D +A · C +A · C) · (A · C +B ·D +A · C)
Solutie
a) Expresia din partea dreapta devine, dupa aplicarea A4:(A+B + C) · (A+B + C) · (A+B + C) == (A ·A+A ·B +A · C +A ·B +B ·B +B · C +A · C +B · C + C · C) · (A+B + C) =utilizand A6, T1 si ulterior A4 (invers, pentru B si C):= (A ·B +A · C +A ·B +B +B · C +A · C + C) · (A+B + C) == [C · (A+B +A+ 1) +B · (A+A+ 1)] · (A+B + C) =utilizand T2, A5 si aplicarea A4 (invers, pentru B):= (C +B) · (A+B + C) = A · C +B · C + C · C +A ·B +B ·B +B · C =observand ca paranteza este egala cu 1 si aplicand A5, rezulta:= A · C +B · (C +A+B + C) = A · C +B = B +A · C, expresie egala cu expresia din partea stanga.
b) Prin gruparea termenilor din partea dreapta, si aplicarea A4:(A · C ·D +A · C ·D) + (A ·B · C +A ·B · C) +A · C ·D = C ·D · (A+A) +A ·B · (C + C) +A · C ·D =aplicarea A6 si gruparea primului termen cu ultimul:= C ·D +A ·B +A · C ·D = (C ·D +A · C ·D) +A ·B = D · (C +A · C) +A ·B =la paranteza se aplica T4 si apoi A4: = D · (C+A)+A ·B = dupa aplicarea A4 si A3: = D ·C+D ·A+A ·B =A ·D + C ·D +A ·B, care este expresia din partea stanga.
c) Prin aplicarea A4 expresiilor din parantezele din partea stanga:D · (A+B + C +D) · (A+B + C +D) == D·(A·A+A·B+A·C+A·D+A·B+B ·B+B ·C+B ·D+A·C+B ·C+C ·C+C ·D+A·D+B ·D+C ·D+D·D) =si restrangerea termenilor utilizand A6 si T1:= D · (0+A ·B+A ·C+A ·D+A ·B+B+B ·C+B ·D+A ·C+B ·C+0+C ·D+A ·D+B ·D+C ·D+D) =pe baza A3, se grupeaza B si D:= D · [B · (A+A+ 1 + C +D + C) +A · C +A · C +D · (A+A+ C + 1)] =si se observa ca parantezele rotunde sunt egale cu 1, conform T2:= D · (B +A · C +A · C +D) = B ·D +A · C ·D +A · C ·D
Expresia din partea dreapta se proceseaza conform A4, A6 si T1:(D +A · C +A · C) · (A · C +B ·D +A · C) =A ·C ·D+B ·D ·D+A ·C ·D+A ·C ·A ·C+A ·C ·B ·D+A ·C ·A ·C+A ·C ·A ·C+A ·C ·B ·D+A ·C ·A ·C == A · C ·D +B ·D +A · C ·D +A ·B · C ·D +A ·B · C ·D =prin aplicarea A3 se grupeaza favorabil termenii pentru a da ın factor B ·D:= (B ·D +A ·B · C ·D +A ·B · C ·D) +A · C ·D +A · C ·D == B ·D · (1 +A · C +A · C) +A · C ·D +A · C ·D =prin aplicarea T2 se ajunge la aceeasi expresie ca dupa procesarea partii stangi:= B ·D +A · C ·D +A · C ·D
3. Utilizand axiomele si teoremele algebrei Booleene, sa se demonstreze urmatoarele identitati:a) A⊕ 1 = A, A⊕ 0 = A, A⊕A = 1, A⊕A = 0b) A ·B + (A+B) · C = A ·B + (A⊕B) · Cc) A⊕B = B ⊕A = A⊕Bd) A⊕B = A ·B +A ·Be) A⊕B = A⊕B = A⊕Bf) A ·B + (A+B) · C = A ·B + (A⊕B) · Cg) A ·B · C +A ·B +A ·B · C ·D = A ·B · C +A ·B +Dh) A ·B · C +A ·B · C +A ·B · C +A ·B · C +A ·B · C = B · C +A ·B +B · Ci) A ·B · C · (B ·D + C ·D · E) +A · C = A · (C +B ·D · E)j) X · Y +X · Y = Xk) X +X · Y = X + Yl) X ·X + Y ) +X · Y
Solutie
a) A⊕ 1 = A · 1 +A · 1 = 0 +A = AA⊕ 0 = A · 0 +A · 0 = A+ 0 = A
2
A⊕A = A ·A+A ·A = A ·A+A ·A = A+A = 1A⊕A = A ·A+A ·A = 0 + 0 = 0
b) Expresia din partea stanga se proceseaza conform A4 si T4:A ·B + (A+B) ·C = A ·B +A ·C +B ·C = A ·B ·C +A ·B ·C +A ·B ·C +A ·B ·C +A ·B ·C +A ·B ·C =A ·B · C +A ·B · C +A ·B · C +A ·B · C =
∑(7, 6, 5, 3)
prin aplicarea A4 si T4 ın partea dreapta se ajunge la o expresie egala cu expresia rezultata din partea stanga:A ·B + (A⊕B) · C = A ·B +A ·B · C +A ·B · C = A ·B · C +A ·B · C +A ·B · C +A ·B · C =
∑(7, 6, 5, 3)
c) A⊕B = A ·B +A ·B =∑
(2, 1)B ⊕A = B ·A+B ·A =
∑(1, 2)
B ⊕A = B ·A+B ·A = B ·A+B ·A =∑
(2, 1)
d) Expresia din partea stanga conform A4 si T4 devine:
A⊕B = A ·B +A ·B = A ·B ·A ·B = (A+B) · (A+B) = A ·A+A ·B+B ·A+B ·B = A ·B+A ·B =∑
(2, 1)Conform A3 expresia din partea dreapta devine:A ·B +A ·B = A ·B +A ·B =
∑(2, 1)
4. Utilizand axiomele si teoremele algebrei Booleene, sa se determine forma minima a functiilor complementareurmatoarelor:
a) F = [(A ·B) ·A] · [(A ·B) ·B] (functia A⊕B exprimata prin operatorul NAND)
b) F = (A+B + C) · (A ·B + C ·D) +B · C ·Dc) F = (A ·B · C +B · C ·D) + (A · C ·D +B · C ·D +B · C ·D)d) F = X · (X +X · Y )
e) F = X · (X + 1)
Solutie
a) F = [(A ·B) ·A] · [(A ·B) ·B] =(A ·B+A) · (A ·B+B) = A ·B ·A ·B+A ·A ·B+A ·B ·B+A ·B = A ·B+0+0+A ·B = A ·B+A ·B = A⊕B.
b) F = (A+B + C) · (A ·B + C ·D) +B · C ·D = (A+B + C) · (A ·B + C ·D) +B · C ·D =
= (A ·B · C) · (A ·B · C ·D) +B · C ·D = (A ·B · C) · (A ·B · C ·D) +B · C ·D = B · C ·D.
c)F = (A ·B · C +B · C ·D) + (A · C ·D +B · C ·D +B · C ·D) == (A ·B · C +B · C ·D) · (A · C ·D +B · C ·D +B · C ·D) == (A ·B · C +B · C ·D) · (A+ C +D +B · C ·D +B · C ·D) == (A ·B · C +B · C ·D) · (A+D · (1 +B · C) + C · (1 +B ·D)) == (A ·B · C +B · C ·D) · (A+D + C) == A ·B · C ·A+A ·B · C ·D +A ·B · C · C +B · C ·D ·A+B · C ·D ·D +B · C ·D · C == 0 +A ·B · C ·D + 0 +B · C ·D ·A+ 0 +B · C ·D == A ·B · C ·D + (A ·B · C ·D +B · C ·D) = A ·B · C ·D +B · C ·D.
5. Sa se aplice teorema lui DeMorgan urmatoarelor expresii:
a) A ·B · (C +D) e) A ·B · (C ·D + E · F )
b) (A+B + C +D) +A ·B · C ·D f) (A+B + C +D) · (A ·B · C ·D)
c) A ·B · (C ·D + E · F ) · (A ·B + C ·D) g) (A ·B · C) · (E · F ·G) + (H · I · J) · (K · L ·M)
d) (A+B · C + C ·D) +B · C h) (A+B) · (C +D) · (E + F ) · (G+H)
Solutie
a) A ·B · (C +D) = A+B + (C +D) = A+B + C ·D = A+B + C ·Db) A ·B · (C ·D + E · F ) = A+B + (C ·D + E · F ) = A+B + C ·D · E · F = A+B + (C +D) · (E + F )
c) (A+B + C +D) +A ·B · C ·D = A ·B · C ·D + (A+B + C +D) = A ·B · C ·D + (A+B + C +D)
d) (A+B + C +D) · (A ·B · C ·D) = (A+B + C +D) + (A ·B · C ·D) = (A+B + C +D) +A ·B · C ·D
6. Sa se determine structura de porti logice care realizeaza urmatoarea functie logica:
Y = (A ·B · C +D) · E · F +G ·H · (I + J +K)
3
Figura 6.1 Structura de porti logice (problema 6).
Solutie
Structura de porti este prezentata ın figura 6.1.
7. Sa se determine structurile de porti logice care realizeaza urmatoarele functii logice. Sa se simplifice expresiileutilizand prelucrari analitice si sa se determine structurile de porti logice simplificate.a) Y1 = (A ·B + C) · [(D + E) · F +G];b) Y2 = (A ·B + C) ·A ·B +B · C;c) Y3 = A ·B · (C ·D + C ·D) +A ·B · (C ·D + C ·D) +A ·B · C ·D;d) Y4 = (A ·B +A ·B) · (C ·D + C ·D);e) Y5 = A ·B · (C +D · E · F ) + C · E · (A+B + F ).
Solutie
Structurile de porti sunt prezentate ın figura 6.2.
8. Sa se determine functia logica a structurii de porti logice prezentate ın figura 6.3.
Solutie
Pornind de la intrarea retelei spre iesire, dupa fiecare poarta se determina expresia logica a iesirii respective careeste apoi propagata la intrarea urmatoarelor porti logice. Pentru reteaua din figura 6.3, la iesirile portilor sededuc:
G1 = AG2 = DG3 = G1 ·B = A ·BG4 = C ·DG5 = B · CG6 = A · C ·G2 = A · C ·DG7 = G4 +G5 = C ·D +B · CG8 = G3 ·G7 = (A ·B) · (C ·D +B · C)G9 = F = G6 +G8 = A · C ·D +A ·B · (C ·D +B · C) = A · C ·D +A ·B · C ·D +A ·B · C.
9. Determinati functiile logice implementate de structurile de porti logice din figura 6.4.
Solutie
Functia logica pentru structurile de porti logice reprezentate ın partea stanga:Y = A ·B · C + (E · F +G) ·BFunctia logica pentru structurile de porti logice reprezentate ın partea dreapta:Y = B · (C ·D · E + F ·G · E) · (A ·B + C)
10. Demonstrati identitatile analitic, folosind axiomele si teoremele algebrei Booleene:a) Y +X · Z +X · Y = X + Y + Zb) X · Y · Z = X + Y + Zc) X + Y · Z = (X + Y ) · (X + Z)d) X · Y + Y · Z +X · Z = X · Y + Y · Z +X · Ze) X · Y +X · Y +X · Y = X + Y
4
Figura 6.2 Structuri de porti logice (problema 7).
f) X · Y + Y · Z +X · Y + Y · Z = 1g) Y +X · Z +X · Y = X + Y + Zh) X · Y + Y · Z +X · Z +X · Y + Y · Z = X · Y +X · Z + Y · Zi) A ·B +A · C ·D +A ·B ·D +A ·B · C ·D = B +A · C ·Dj) X · Z +W · Y · Z +W · Y · Z +W ·X · Z = X · Z +W · Y · Z +W ·X · Y +W ·X · Y +X · Y · Zk) C ·D +A ·B +A · C +A · C +A ·B + C ·D = (A+B + C +D) · (A+B + C +D)l) (A⊕B) · C = (A ·B)⊕ (B · C)
Solutie
a) Expresia din partea stanga se proceseaza conform T4:Y +X · Z +X · Y = Y +X +X · Z = Y +X + Z = X + Y + Z prin aplicarea A3 se ajunge la o expresie egalacu expresia din partea dreapta.
b) Expresia din partea stanga devine, prin aplicarea T5, egala cu expresia din partea dreapta:X · Y · Z = X + Y + Z
c) Utilizand A4 si ulterior T4 expresia din partea dreapta devine egala cu cea din partea stanga:(X + Y ) · (X + Z) = X ·X +X · Z + Y ·X + Y · Z = X + Y · Zd) X · Y + Y · Z +X · Z == X · Y · Z +X · Y · Z +X · Y · Z +X · Y · Z +X · Y · Z +X · Y · Z =
∑(3, 2, 5, 1, 6, 4) =
∑(1, 2, 3, 4, 5, 6)
X ·Y +Y ·Z+X ·Z = X ·Y ·Z+X ·Y ·Z+X ·Y ·Z+X ·Y ·Z+X ·Y ·Z+X ·Y ·Z =∑
(5, 4, 6, 2, 3, 1) =∑
(1, 2, 3, 4, 5, 6)
e) Prin aplicarea A4 si ulterior T1 expresia din partea dreapta devine:X ·Y +X ·Y +X ·Y = X · (Y +Y )+X ·Y = X+X ·Y = X+Y Aplicand T4 expresia devine egala cu expresiadin partea stanga.
11. Folosind algebra Booleana, simplificati expresiile si aduceti-le la o forma echivalenta exprimata cu un numarminim de litere.
5
Figura 6.3 Structura de porti logice (problema 8).
Figura 6.4 Structura de porti logice (problema 9).
a) x · y + x · y b) x · y · z + x · y + x · y · zc) (x+ y) · (x+ y) d) (x+ y) · (x+ y)
e) (x+ y) · (x+ y) f) (y · z + x · w) · (x · y + z · w)g) x · y · z + x · z h) x · y + x · (w · z + w · z)i) x · z + x · y · z + x · z j) (x · y + z) + z + x · y + w · zk) x · y · z + x · y + x · y · z l) x · y · (w + z · w) + y · (x+ x · z · w)m) (x+ z) · (x+ z) · (x+ y + z · w) n) A ·B · C +A ·B · C +A ·Bo) (A+B) · (A+B) p) A ·B · C +A · Cq) B · C +B · (A ·D +A ·D) r) (A+B +A ·B) · (A ·B +A · C +B · C)s) X · Y +X · Y · Z +X · Y t) X + Y · (Z +X + Z)u) W ·X · (Z + Y · Z) +X · (W +W · Y · Z) v) (A ·B +A ·B) · (C ·D + C ·D) +A · Cw) X · (X +X · Y ) x) X · (X + 1)
Solutie
a) Utilizand A4 si ulterior T1 expresia devine:x · y + x · y = x · (y + y) = x
b) Conform A4 expresia devine:x · y · z + x · y + x · y · z = x · y · (z + z) + x · y Prin aplicarea A2 si ulterior A4 si ınca o data A2:x · y + x · y = y · (x+ x) = y
c) Aplicand A4 si T1 expresia devine: (x+ y) · (x+ y) = x ·x+x · y+ y ·x+ y · y = x+x · (y+ y)+0 = x+1 = 1
d) Prin aplicarea T5 si ulterior A6 expresia devine: (x+ y) · (x+ y) = x · y · x · y = 0
e) Utilizand T6 si ulterior T4 expresia devine: (x+ y) · (x+ y) = x · y · (x+ y) = x · yf) Dupa aplicarea A4 expresia devine:(y ·z+x ·w) · (x ·y+z ·w) = y ·z · (x ·y+z ·w)+x ·w · (x ·y+z ·w) = y ·z ·x ·y+y ·z ·z ·w+x ·w ·x ·y+x ·w ·z ·wDupa restrangerea termenilor utilizand A6: 0 + y · z · w + 0 + 0 = y · z · w
12. Aflati complementul expresiei F = x+ y · z. Aratati ca F · F = 0 si F + F = 1.
6
Solutie
F = x+ y · z = x · y · z = x · (y + z) = x · y + x · zF · F = (x+ y · z) · (x · y + x · z) = x · x · y + x · x · z + y · z · x · y + y · z · x · z = 0 + 0 + 0 + 0 = 0
F + F = (x + y · z) + (x · y + x · z) = (x + x · y) + y · z + x · z = x + (y + y · z) + x · z = x + y + (z + x · z) =x+ y + z + x = (x+ x) + y + z = 1 + y + z = 1
13. Aflati expresiile complementare urmatoarelor expresii:
a) x · y + x · y e) (x+ y + z) · (x+ z) · (x+ y)b) (x · y + z · w + q f) A ·B +A ·Bc) V ·W +X) · Y + Z g) W ·X · (Y · Z + Y · Z) +W ·X · (Y + Z) · (Y + Z)d) (A+B + C) · (A ·B + C) · (A+B · C)
Solutie
Formele complementare ale expresiilor se obtin prin negarea acestora:
a) x · y + x · y = x · y · x · y = (x+ y) · (x+ y)
b) (x+ y + z) · (x+ z) · (x+ y) = (x+ y + z) + (x+ z) + (x+ y) = x · y · z + x · z + x · yc) x · y + z · w + q = (x · y) · (z · w) · q = (x+ y) · (z + w) · q
d) A ·B +A ·B = A ·B +A ·B = A ·B ·A ·B = (A+B) · (A+B)
14. Se considera doua functii logice F1 =∑
(0, 1, 3) si F2 =∑
(0, 1, 4, 5). Aratati ca:a) functia E = F1 + F2 contine reuniunea mintermilor apartinand functiilor F1 si F2,b) functia G = F1 · F2 contine intersectia mintermilor functiilor F1 si F2.
Solutie
a) E = F1 + F2 =∑
(0, 1, 3) +∑
(0, 1, 4, 5) =∑
(0, 1, 3, 0, 1, 4, 5) =∑
(0, 1, 3, 4, 5)
b) G = F1 ·F2 =∑
(0, 1, 3)·∑
(0, 1, 3, 4, 5) = (P0+P1+P3)·(P0+P1+P4+P5) = (P0 ·P0+P0 ·P1+P0 ·P4+P0 ·P5)+(P1·P0+P1·P1+P1·P4+P1·P5)+(P3·P0+P3·P1+P3·P4+P3·P5) = (P0+0+0+0)+(0+P1+0+0)+(0+0+0+0) =P0 + P1 =
∑(0, 1)
15. Se considera functiile logice exprimate prin tabelul de adevar urmator:A B C X Y Z W0 0 0 1 0 1 00 0 1 1 0 1 00 1 0 1 0 1 10 1 1 0 1 0 11 0 0 0 1 0 01 0 1 0 1 1 01 1 0 0 1 0 11 1 1 0 1 0 1
a) Sa se reprezinte fiecare functie ın formele standard.b) Sa se deduca formele standard ale functiilor complementate.c) Sa se simplifice functiile prin prelucrari algebrice.
Solutie
a) X =∑
(0, 1, 2), Y =∑
(3, 4, 5, 6, 7), Z =∑
(0, 1, 2, 5), W =∑
(2, 3, 6, 7).
b) X =∑
(3, 4, 5, 6, 7), Y =∑
(0, 1, 2), Z =∑
(3, 4, 6, 7), W =∑
(0, 1, 4, 5).
c) X =∑
(0, 1, 2) = A · B · C + A · B · C + A · B · C = A · B · (C + C) + A · B · C = A · B + A · B · C =A · (B +B · C) = A · (B + C) = A ·B +A · CY =
∑(3, 4, 5, 6, 7) = A ·B · C +A ·B · C +A ·B · C +A ·B · C +A ·B · C = (A ·B · C +A ·B · C) + (A ·B ·
C +A ·B · C) +A ·B · C = B · C + (A ·B +A ·B · C) = B · C +A(B +B · C) = B · C +A ·B +A · CZ =
∑(0, 1, 2, 5) = A ·B ·C +A ·B ·C +A ·B ·C +A ·B ·C = (A ·B ·C +A ·B ·C) +A ·B ·C +A ·B ·C =
(A ·B +A ·B · C) +A ·B · C = A(B + C) +A ·B · C = A ·B +A · C +A ·B · CW =
∑(2, 3, 6, 7) = A ·B · C +A ·B · C +A ·B · C +A ·B · C
7
16. Se considera functia logica F = x · y · z + x · y · z + w · x · y + w · x · y + w · x · ya) Obtineti tabelul de adevar al functiei.b) Determinati structura de porti logice care implementeaza functia, conform expresiei originale.c) Simplificati expresia functiei utilizand alegebra Booleana.d) Obtineti tabelul de adevar al functiei din expresia simplificata si demonstrati ca este identic cu cel obtinutanterior.e) Determinati structura de porti logice care implementeaza functia, conform expresiei minimizate.f) Comparati costurile celor doua implementari ca numar de porti logice si ca numar de intrari ın porti logice.
Solutie
a) Tabelul de adevar al functiei si structura de porti sunt prezentate ın figura 6.5.
Initial w x y z F Simplificat0 0 0 0 00 0 0 1 10 0 1 0 00 0 1 1 00 1 0 0 00 1 0 1 10 1 1 0 10 1 1 1 11 0 0 0 01 0 0 1 11 0 1 0 11 0 1 1 11 1 0 0 01 1 0 1 11 1 1 0 11 1 1 1 1
Figura 6.5 Tabelul de adevar si structura de porti logice initiala si simplificata (problema 16).
c) F = x ·y ·z+x ·y ·z+w ·x ·y+w ·x ·y+w ·x ·y = y ·z · (x+x)+x ·y · (w+w)+w ·x ·y = y ·z+x ·y+w ·x ·y =y · z + y · (x+ x · w) = y · z + y · (x+ w) = y · z + y · x+ y · wf) Costurile implementarii calculate ca numar de porti logice si ca numar de intrari ın porti logice sunt:
Implementare initiala: Implementare dupa simplificare:5 porti NOT × 1 intrare; 1 poarta NOT × 1 intrare;5 porti AND × 3 intrari; 3 porti AND × 2 intrari;1 poarta OR × 5 intrari. 2 porti OR × 2 intrari.Total: 11 porti × 25 intrari. Total: 6 porti × 11 intrari.
17. Aflati expresiile complementare (negate), exprimate ca suma de mintermi:a) F (A,B,C,D) =
∑(0, 2, 6, 11, 13, 14) b) F (A,B,C) =
∏(0, 3, 6, 7)
Solutie
a) Functia complementara prezinta suma mintermilor care nu apar ın expresia initiala de ”suma de produse”:F (A,B,C,D) =
∑(1, 3, 4, 5, 7, 8, 9, 10, 12, 15)
b) Functia complementara prezinta suma mintermilor corespunzatori maxtermilor care apar ın forma ıniıala de”produs de sume”: F (A,B,C) =
∑(0, 3, 6, 7)
18. Convertiti functiile ın forma standard complementara celei prezentate:a) F (A,B,C,D) =
∑(1, 3, 7) b) F (A,B,C,D) =
∏(0, 1, 2, 3, 4, 6, 12)
Solutie
Forma standard complementara se obtine prin iterschimbarea simbolurilor∑
si∏
(din ”suma de produse” ın”produs de sume”) si considerarea indecsilor care nu apar ın expresia initiala.a) F (A,B,C,D) =
∏(0, 1, 2, 4, 5, 6, 8, 9, 10, 11, 12, 13, 14, 15)
b) F (A,B,C,D) =∑
(7, 8, 9, 10, 11, 13, 14, 15)
8
19. Convertiti functiile ın forme standard:a) (A ·B + C) · (B + C ·D)b) A+A · (A+B) · (B + C)c) (A+B · C + C ·D) · (B + E · F )
20. Determinati structura de porti logice care implementeaza functiile, fara a le simplifica. Simplificati functiile prinprelucrari algebrice si propuneti o structura de porti logice simplificata.
a) B · C +A ·B +A · C ·D d) (A ·B +A ·B) · (C ·D + C ·D)b) (A+B) · (C +D) · (A+B +D) e) W ·X · Y +W · Z +X · Yc) A · (B · C +B · C) + C · (B ·D +B ·D) f) W · Y · (X + Z) +X · Y · (W + Z) +W · Z · (X + Y )
21. Stiind ca A ·B = 0 si ca A+B = 1, dovediti prin prelucrari algebrice ca A · C +A ·B +B · C = B + C.Dovediti egalitatea prin forme de unda, analizand toate cazurile posibile ale celor trei intrari.
Solutie
Se considera tabelul din figura 6.6. Se observa ca:
Rand A B C A ·B A+B A · C A ·B B · C A · C +A ·B + B · C B + C0 0 0 0 0 0 0 0 0 0 01 0 0 1 0 0 0 0 0 0 12 0 1 0 0 1 0 1 0 1 13 0 1 1 0 1 0 1 1 1 14 1 0 0 0 1 0 0 0 0 05 1 0 1 0 1 1 0 0 1 16 1 1 0 1 1 0 0 0 0 17 1 1 1 1 1 1 0 1 1 1
Figura 6.6 Tabelul de adevar pentru problema 21.
- ındeplinirea conditiei A ·B = 0 se face pentru randurile 0, 1, 2, 3, 4, si 5;- ındeplinirea conditiei A+B = 1 se face pentru randurile 2, 3, 4, 5, 6, si 7.
Rezulta ca ambele conditii sunt ındeplinite doar ın cazurile liniilor 2, 3, 4 si 5. In aceste cazuri, expresiamentionata este adevarata (coloanele corespunzatoare au aceleasi valori pe randurile 2, 3, 4 si 5. Fomele deunda sunt prezentate ın figura 6.7. De observat ca daca ipotezele asupra semnalelor A si B nu sunt ındeplinite,expresia mentionata nu este adevarata.
Figura 6.7 Forme de una pentru problema 21.
Analitic, se poate observa faptul ca ındeplinirea conditiilor asupra semnalelor a si B are loc doar daca A si Bsunt complementare (A = B). Inlocuind A cu B ın partea stanga se obtine:
A ·C +A ·B +B ·C = B ·C +B ·B +B ·C = B ·C +B ·B +B ·C = B ·C +B +B ·C = B ·C +B = B +C.
22. Determinati tabelul de adevar, forma canonica conjunctiva si forma canonica disjunctiva pentru urmatoareleexpresii logice:
a) Fa = (X · Y + Z) · (Y +X · Z) d) Fd = (A+B) · (B + C)b) Fb = W ·X · Y +W ·X · Z +W ·X · Z + Y · Z e) Fe = X +X · Yc) Fc = X · Y +X · Z f) Ff = X · Y · Z +X · Y + Z
9
Solutie
a) Fa(X,Y, Z) =∑
(0, 1, 2, 4) =∏(3, 5, 6, 7)
X Y Z X · Y X · Y + Z X · Z Y +X · Z Fa
0 0 0 0 0 0 0 00 0 1 0 1 0 0 00 1 0 0 0 0 1 00 1 1 0 1 0 1 11 0 0 0 0 0 0 01 0 1 0 1 1 1 11 1 0 1 1 0 1 11 1 1 1 1 1 1 1
b) Fb(X,Y, Z,W ) =∑
(4, 5, 9, 11, 12, 13, 15) =∏(0, 1, 2, 3, 6, 7, 8, 10, 14)
X Y Z W Y Z W ·X · Y W ·X · Z W ·X · Z Y · Z Fb
0 0 0 0 1 1 0 0 0 0 00 0 0 1 1 1 0 0 0 0 00 0 1 0 1 0 0 0 0 0 00 0 1 1 1 0 0 0 0 0 00 1 0 0 0 1 0 0 0 1 10 1 0 1 0 1 0 0 0 1 10 1 1 0 0 0 0 0 0 0 00 1 1 1 0 0 0 0 0 0 01 0 0 0 1 1 0 0 0 0 01 0 0 1 1 1 1 1 0 0 11 0 1 0 1 0 0 0 0 0 01 0 1 1 1 0 1 0 1 0 11 1 0 0 0 1 0 0 0 1 11 1 0 1 0 1 0 1 0 1 11 1 1 0 0 0 0 0 0 0 01 1 1 1 0 0 0 0 1 0 1
c) Fc(X,Y, Z) =∏(0, 1, 2, 3, 4) =
∑(5, 6, 7)
X Y Z X · Y X · Z Fc
0 0 0 0 0 00 0 1 0 0 00 1 0 0 0 00 1 1 0 0 01 0 0 0 0 01 0 1 0 1 11 1 0 1 0 11 1 1 1 1 1
d) Fd(A,B,C) =∏(2, 4, 5, 6) =
∑(0, 1, 3, 7)
A B C A B A+B B + C Fd
0 0 0 1 1 1 1 10 0 1 1 1 1 1 10 1 0 1 0 1 0 00 1 1 1 0 1 1 11 0 0 0 1 0 1 01 0 1 0 1 0 1 01 1 0 0 0 1 0 01 1 1 0 0 1 1 1
e) Fe =∏(0, 1) =
∑(2, 3)
X Y X · y Fe
0 0 0 00 1 0 01 0 0 11 1 1 1
f) Ff =∏(0, 2, 4) =
∑(1, 3, 5, 6, 7)
10
X Y Z X Z X · Y · Z X · Y Ff
0 0 0 1 1 0 0 00 0 1 1 0 0 0 10 1 0 1 1 0 1 00 1 1 1 0 0 1 11 0 0 0 1 0 0 01 0 1 0 0 0 0 11 1 0 0 1 1 0 11 1 1 0 0 0 0 1
23. Scrieti functiile urmatoare ca suma de mintermi (forma canonica disjunctiva).F (A,B,C) = A ·B · C +A ·B · C +A ·B · CF (A,B,C,D) = A ·B · C ·D +A ·B · C ·D +A ·B · C ·D +A ·B · C ·DF (A,B,C,D,E) = A ·B ·C ·D ·E+A ·B ·C ·D ·E+A ·B ·C ·D ·E+A ·B ·C ·D ·E+A ·B ·C ·D ·E+A ·B ·C ·D ·E
24. Scrieti functiile urmatoare ca produse mintermi (forma canonica conjunctiva).F (A,B,C) = (A+B + C) · (A+B + C) · (A+B + C)F (A,B,C,D) = (A+B + C +D) · (A+B + C +D) · (A+B + C +D) · (A+B + C +D)F (A,B,C,D,E) = (A+B +C +D+E) · (A+B +C +D+E) · (A+B +C +D+E) · (A+B +C +D+E) ·(A+B + C +D + E) · (A+B + C +D + E)
11
