Reprezentarea funcţiilor booleeneiota.ee.tuiasi.ro/~cghaba/SPME/spmeNotecurs/Reprezentarea...
Transcript of Reprezentarea funcţiilor booleeneiota.ee.tuiasi.ro/~cghaba/SPME/spmeNotecurs/Reprezentarea...
![Page 1: Reprezentarea funcţiilor booleeneiota.ee.tuiasi.ro/~cghaba/SPME/spmeNotecurs/Reprezentarea FB.pdf · zGrafice zAnalitice. Reprezent ări grafice zTabele de adevăr zScheme de operatori](https://reader030.fdocumente.com/reader030/viewer/2022040109/5e604632e05f9b41cd3a8a07/html5/thumbnails/1.jpg)
Reprezentarea funcţiilor booleene
(în lucru)
![Page 2: Reprezentarea funcţiilor booleeneiota.ee.tuiasi.ro/~cghaba/SPME/spmeNotecurs/Reprezentarea FB.pdf · zGrafice zAnalitice. Reprezent ări grafice zTabele de adevăr zScheme de operatori](https://reader030.fdocumente.com/reader030/viewer/2022040109/5e604632e05f9b41cd3a8a07/html5/thumbnails/2.jpg)
Reprezentările FB pot fi:
GraficeAnalitice
![Page 3: Reprezentarea funcţiilor booleeneiota.ee.tuiasi.ro/~cghaba/SPME/spmeNotecurs/Reprezentarea FB.pdf · zGrafice zAnalitice. Reprezent ări grafice zTabele de adevăr zScheme de operatori](https://reader030.fdocumente.com/reader030/viewer/2022040109/5e604632e05f9b41cd3a8a07/html5/thumbnails/3.jpg)
Reprezentări grafice
Tabele de adevărScheme de operatori (porţi logice)Arbori de decizie binarăDiagrame Veitch-KarnaughScheme cu contacteHipercubDiagrame de semnale
![Page 4: Reprezentarea funcţiilor booleeneiota.ee.tuiasi.ro/~cghaba/SPME/spmeNotecurs/Reprezentarea FB.pdf · zGrafice zAnalitice. Reprezent ări grafice zTabele de adevăr zScheme de operatori](https://reader030.fdocumente.com/reader030/viewer/2022040109/5e604632e05f9b41cd3a8a07/html5/thumbnails/4.jpg)
Reprezentări analitice
Simbolice– forme normale necanonice disjunctive şi
conjunctive– forme normale canonice disjunctive şi conjunctive– simbol de marcare
Coduri– vectori booleeni– numere convenţionale– notaţia cubică poziţională
![Page 5: Reprezentarea funcţiilor booleeneiota.ee.tuiasi.ro/~cghaba/SPME/spmeNotecurs/Reprezentarea FB.pdf · zGrafice zAnalitice. Reprezent ări grafice zTabele de adevăr zScheme de operatori](https://reader030.fdocumente.com/reader030/viewer/2022040109/5e604632e05f9b41cd3a8a07/html5/thumbnails/5.jpg)
Tabele de adevăr
Unei funcţii de n variabile i se asociază o tabelă cu:2n linii – corespund celor 2n combinaţii posibile ale variabilelorn+1 coloane – n coloane corespunzătoare celor n variabile şi o coloană pentru valorile funcţiei
![Page 6: Reprezentarea funcţiilor booleeneiota.ee.tuiasi.ro/~cghaba/SPME/spmeNotecurs/Reprezentarea FB.pdf · zGrafice zAnalitice. Reprezent ări grafice zTabele de adevăr zScheme de operatori](https://reader030.fdocumente.com/reader030/viewer/2022040109/5e604632e05f9b41cd3a8a07/html5/thumbnails/6.jpg)
Tabele de adevăr
Funcţie de 2 variabilefba
011
101
110
000
![Page 7: Reprezentarea funcţiilor booleeneiota.ee.tuiasi.ro/~cghaba/SPME/spmeNotecurs/Reprezentarea FB.pdf · zGrafice zAnalitice. Reprezent ări grafice zTabele de adevăr zScheme de operatori](https://reader030.fdocumente.com/reader030/viewer/2022040109/5e604632e05f9b41cd3a8a07/html5/thumbnails/7.jpg)
Tabele de adevăr
Funcţie de 3 variabile
1111
1011
1101
1001
0110
1010
0100
0000
fcba
![Page 8: Reprezentarea funcţiilor booleeneiota.ee.tuiasi.ro/~cghaba/SPME/spmeNotecurs/Reprezentarea FB.pdf · zGrafice zAnalitice. Reprezent ări grafice zTabele de adevăr zScheme de operatori](https://reader030.fdocumente.com/reader030/viewer/2022040109/5e604632e05f9b41cd3a8a07/html5/thumbnails/8.jpg)
Definiţii
Un literal este apariţia unei variabile în forma normală sau negată.– Ex. x, x’, a, a’, x1, x1’ etc.
Un termen produs sau termen normal conjunctiv este produsul logic al mai multor literale. Fiecare literal apare o singură dată– Ex. x.z’, a.b’.c, x1’.x2.x3
![Page 9: Reprezentarea funcţiilor booleeneiota.ee.tuiasi.ro/~cghaba/SPME/spmeNotecurs/Reprezentarea FB.pdf · zGrafice zAnalitice. Reprezent ări grafice zTabele de adevăr zScheme de operatori](https://reader030.fdocumente.com/reader030/viewer/2022040109/5e604632e05f9b41cd3a8a07/html5/thumbnails/9.jpg)
Definiţii
Un minterm sau constituent al unităţii este un termen produs care include toate variabilele de care depinde funcţia.
– Ex. Pentru f(x,y,z)x.y.z, x’.y.z sunt mintermi, x.y nu este minterm pentru ca lipseşte variabila z– Ex. Pentru f(a,b,c,d)a.b.c.d’, a’.b.c.d’ sunt mintermia.d nu este minterm pentru că lipsesc variabilele b şi c
![Page 10: Reprezentarea funcţiilor booleeneiota.ee.tuiasi.ro/~cghaba/SPME/spmeNotecurs/Reprezentarea FB.pdf · zGrafice zAnalitice. Reprezent ări grafice zTabele de adevăr zScheme de operatori](https://reader030.fdocumente.com/reader030/viewer/2022040109/5e604632e05f9b41cd3a8a07/html5/thumbnails/10.jpg)
Definiţii
Un maxterm sau constituent al lui 0 este un termen sumă care include toate variabilele de care depinde funcţia.
– Ex. Pentru f(x,y,z)x+y+z, x’+y+z sunt maxtermi, x+y nu este maxterm pentru ca lipseşte variabila z– Ex. Pentru f(a,b,c,d)a+b+c+d’, a’+b+c+d’ sunt mintermia+d nu este maxterm pentru că lipsesc variabilele b şi c
![Page 11: Reprezentarea funcţiilor booleeneiota.ee.tuiasi.ro/~cghaba/SPME/spmeNotecurs/Reprezentarea FB.pdf · zGrafice zAnalitice. Reprezent ări grafice zTabele de adevăr zScheme de operatori](https://reader030.fdocumente.com/reader030/viewer/2022040109/5e604632e05f9b41cd3a8a07/html5/thumbnails/11.jpg)
Definiţii
Un termen sumă sau termen normal disjunctiv este suma logică a mai multor literale. Fiecare literal apare o singură dată– Ex. x+z’, a+b’+c, x1’+x2+x3
![Page 12: Reprezentarea funcţiilor booleeneiota.ee.tuiasi.ro/~cghaba/SPME/spmeNotecurs/Reprezentarea FB.pdf · zGrafice zAnalitice. Reprezent ări grafice zTabele de adevăr zScheme de operatori](https://reader030.fdocumente.com/reader030/viewer/2022040109/5e604632e05f9b41cd3a8a07/html5/thumbnails/12.jpg)
Definiţii
O expresie sumă de produse sau formă normală disjunctivă este formată din suma logică a mai multor termeni produs.Ex.
a.b’.c’+a’.b.c+a’.b.c’ObservaţiePentru simplificare, când nu există dubii, operatorul “.”
se poate omiteEx.
ab’c’+a’bc+a’bc’
![Page 13: Reprezentarea funcţiilor booleeneiota.ee.tuiasi.ro/~cghaba/SPME/spmeNotecurs/Reprezentarea FB.pdf · zGrafice zAnalitice. Reprezent ări grafice zTabele de adevăr zScheme de operatori](https://reader030.fdocumente.com/reader030/viewer/2022040109/5e604632e05f9b41cd3a8a07/html5/thumbnails/13.jpg)
Definiţii
O expresie produs de sume sau formă normală conjunctivă este formată din produsul logic a mai multor termeni sumă.Ex.
(a+b’+c’).(a’+b+c).(a’+b+c’)ObservaţiePentru simplificare, când nu există dubii, operatorul “.”
se poate omiteEx.
(a+b’+c’)(a’+b+c)(a’+b+c’)
![Page 14: Reprezentarea funcţiilor booleeneiota.ee.tuiasi.ro/~cghaba/SPME/spmeNotecurs/Reprezentarea FB.pdf · zGrafice zAnalitice. Reprezent ări grafice zTabele de adevăr zScheme de operatori](https://reader030.fdocumente.com/reader030/viewer/2022040109/5e604632e05f9b41cd3a8a07/html5/thumbnails/14.jpg)
Tabela de adevăr şi mintermi
Regulă:Fiecărei combinaţii de valori îi corespunde un
minterm în care– xi apare normal dacă pentru combinaţia
respectivă xi=1– xi apare negat dacă pentru combinaţia respectivă
xi=0
![Page 15: Reprezentarea funcţiilor booleeneiota.ee.tuiasi.ro/~cghaba/SPME/spmeNotecurs/Reprezentarea FB.pdf · zGrafice zAnalitice. Reprezent ări grafice zTabele de adevăr zScheme de operatori](https://reader030.fdocumente.com/reader030/viewer/2022040109/5e604632e05f9b41cd3a8a07/html5/thumbnails/15.jpg)
Tabele de adevăr şi mintermi
Funcţie de 2 variabile
m3
m2
m1
m0
Notaţie
0
1
1
0
f Mintermiba
a.b11
a.b’01
a’.b10
a’.b’00
![Page 16: Reprezentarea funcţiilor booleeneiota.ee.tuiasi.ro/~cghaba/SPME/spmeNotecurs/Reprezentarea FB.pdf · zGrafice zAnalitice. Reprezent ări grafice zTabele de adevăr zScheme de operatori](https://reader030.fdocumente.com/reader030/viewer/2022040109/5e604632e05f9b41cd3a8a07/html5/thumbnails/16.jpg)
Tabele de adevăr
Funcţie de 3 variabile
m7
m6
m5
m4
m3
m2
m1
m0
Notaţie
a.b.c
a.b.c’
a.b’.c
a.b’.c’
a’.b.c
a’.b.c’
a’.b’.c
a’.b’.c’
Mintermi
0111
0011
0101
1001
1110
1010
0100
0000
fcba
![Page 17: Reprezentarea funcţiilor booleeneiota.ee.tuiasi.ro/~cghaba/SPME/spmeNotecurs/Reprezentarea FB.pdf · zGrafice zAnalitice. Reprezent ări grafice zTabele de adevăr zScheme de operatori](https://reader030.fdocumente.com/reader030/viewer/2022040109/5e604632e05f9b41cd3a8a07/html5/thumbnails/17.jpg)
Tabela de adevăr şi maxtermi
Regulă:Fiecărei combinaţii de valori îi corespunde un
maxterm în care– xi apare negat dacă pentru combinaţia respectivă
xi=1– xi apare normal dacă pentru combinaţia
respectivă xi=0
![Page 18: Reprezentarea funcţiilor booleeneiota.ee.tuiasi.ro/~cghaba/SPME/spmeNotecurs/Reprezentarea FB.pdf · zGrafice zAnalitice. Reprezent ări grafice zTabele de adevăr zScheme de operatori](https://reader030.fdocumente.com/reader030/viewer/2022040109/5e604632e05f9b41cd3a8a07/html5/thumbnails/18.jpg)
Tabele de adevăr şi mintermi
Funcţie de 2 variabile
M3
M2
M1
M0
Notaţie
0
1
1
0
f Maxtermiba
a’+b’11
a’+b01
a+b’10
a+b00
![Page 19: Reprezentarea funcţiilor booleeneiota.ee.tuiasi.ro/~cghaba/SPME/spmeNotecurs/Reprezentarea FB.pdf · zGrafice zAnalitice. Reprezent ări grafice zTabele de adevăr zScheme de operatori](https://reader030.fdocumente.com/reader030/viewer/2022040109/5e604632e05f9b41cd3a8a07/html5/thumbnails/19.jpg)
Tabele de adevăr
Funcţie de 3 variabile
M7
M6
M5
M4
M3
M2
M1
M0
Notaţie
a’+b’+c’
a’+b’+c
a’+b+c’
a’+b+c
a+b’+c’
a+b’+c
a+b+c’
a+b+c
Maxtermi
0111
0011
0101
1001
1110
1010
0100
0000
fcba
![Page 20: Reprezentarea funcţiilor booleeneiota.ee.tuiasi.ro/~cghaba/SPME/spmeNotecurs/Reprezentarea FB.pdf · zGrafice zAnalitice. Reprezent ări grafice zTabele de adevăr zScheme de operatori](https://reader030.fdocumente.com/reader030/viewer/2022040109/5e604632e05f9b41cd3a8a07/html5/thumbnails/20.jpg)
Forma canonică normal disjunctivă
O funcţie f(x1,x2,...,xn) poate fi scrisă sub forma canonică normal disjunctivă:
2n-1
f(x1,x2,...,xn)=Σ αK.mKK=0
unde αK=f(kn-1,kn-2,...,k1,k0) este valoarea funcţiei din tabelul de adevăr corespunzător mintermului mk
![Page 21: Reprezentarea funcţiilor booleeneiota.ee.tuiasi.ro/~cghaba/SPME/spmeNotecurs/Reprezentarea FB.pdf · zGrafice zAnalitice. Reprezent ări grafice zTabele de adevăr zScheme de operatori](https://reader030.fdocumente.com/reader030/viewer/2022040109/5e604632e05f9b41cd3a8a07/html5/thumbnails/21.jpg)
Forma canonică normal disjunctivă
f(a,b)==f(0,0).a’.b’+ f(0,1).a’.b+ f(1,0).a.b’+ f(1,1).a.b==a’.b+a.b
m3
m2
m1
m0
Notaţie
0
1
10
f Mintermiba
a.b11
a.b’01
a’.b10a’.b’00
![Page 22: Reprezentarea funcţiilor booleeneiota.ee.tuiasi.ro/~cghaba/SPME/spmeNotecurs/Reprezentarea FB.pdf · zGrafice zAnalitice. Reprezent ări grafice zTabele de adevăr zScheme de operatori](https://reader030.fdocumente.com/reader030/viewer/2022040109/5e604632e05f9b41cd3a8a07/html5/thumbnails/22.jpg)
Forma canonică normal disjunctivă
Funcţie de 3 variabilef(a,b,c)=m2+m3+m4=
= a’.b.c’+ a’.b.c+ a.b’.c’
m7
m6
m5
m4
m3
m2
m1
m0
Notaţie
a.b.c
a.b.c’
a.b’.c
a.b’.c’
a’.b.c
a’.b.c’
a’.b’.c
a’.b’.c’
Min-termi
0111
0011
0101
1001
1110
1010
0100
0000
fcba
![Page 23: Reprezentarea funcţiilor booleeneiota.ee.tuiasi.ro/~cghaba/SPME/spmeNotecurs/Reprezentarea FB.pdf · zGrafice zAnalitice. Reprezent ări grafice zTabele de adevăr zScheme de operatori](https://reader030.fdocumente.com/reader030/viewer/2022040109/5e604632e05f9b41cd3a8a07/html5/thumbnails/23.jpg)
Forma canonică normal disjunctivă
FCND este formată din suma logică a mintermilor pentru care funcţia ia valoarea 1.Observaţie: FCND are atâţia mintermi câte valori de 1 are funcţia
![Page 24: Reprezentarea funcţiilor booleeneiota.ee.tuiasi.ro/~cghaba/SPME/spmeNotecurs/Reprezentarea FB.pdf · zGrafice zAnalitice. Reprezent ări grafice zTabele de adevăr zScheme de operatori](https://reader030.fdocumente.com/reader030/viewer/2022040109/5e604632e05f9b41cd3a8a07/html5/thumbnails/24.jpg)
Forma canonică normal conjunctivă
O funcţie f(x1,x2,...,xn) poate fi scrisă sub forma canonică normal conjunctivă:
2n
-1
f(x1,x2,...,xn)=Π (βK+MK)K=0
unde βK=f(kn-1,kn-2,...,k1,k0) este valoarea funcţiei din tabelul de adevăr corespunzător maxtermului Mk
![Page 25: Reprezentarea funcţiilor booleeneiota.ee.tuiasi.ro/~cghaba/SPME/spmeNotecurs/Reprezentarea FB.pdf · zGrafice zAnalitice. Reprezent ări grafice zTabele de adevăr zScheme de operatori](https://reader030.fdocumente.com/reader030/viewer/2022040109/5e604632e05f9b41cd3a8a07/html5/thumbnails/25.jpg)
Forma canonică normal conjunctivă
f(a,b)==(f(0,0)+a+b).( f(0,1)+a+b’).( f(1,0)+a’+b).( f(1,1)+a’+b’)==M0.M3==(a+b).(a’+b’)
M3
M2
M1
M0
Notaţie
0
1
1
0
f Maxtermi
ba
a’+b’11
a’+b01
a+b’10
a+b00
![Page 26: Reprezentarea funcţiilor booleeneiota.ee.tuiasi.ro/~cghaba/SPME/spmeNotecurs/Reprezentarea FB.pdf · zGrafice zAnalitice. Reprezent ări grafice zTabele de adevăr zScheme de operatori](https://reader030.fdocumente.com/reader030/viewer/2022040109/5e604632e05f9b41cd3a8a07/html5/thumbnails/26.jpg)
Forma canonică normal conjunctivă
Funcţie de 3 variabilef(a,b,c)=M0.M1.M5.M6.M7
=(a+b+c).(a+b+c’).(a’+b+c’).(a’+b’+c).(a’+b’+c’)
M7
M6
M5
M4
M3
M2
M1
M0
Notaţie
a’+b’+c’
a’+b’+c
a’+b+c’
a’+b+c
a+b’+c’
a+b’+c
a+b+c’
a+b+c
Maxtermi
0111
0011
0101
1001
1110
1010
0100
0000
fcba
![Page 27: Reprezentarea funcţiilor booleeneiota.ee.tuiasi.ro/~cghaba/SPME/spmeNotecurs/Reprezentarea FB.pdf · zGrafice zAnalitice. Reprezent ări grafice zTabele de adevăr zScheme de operatori](https://reader030.fdocumente.com/reader030/viewer/2022040109/5e604632e05f9b41cd3a8a07/html5/thumbnails/27.jpg)
Forma canonică normal conjunctivă
FCNC este formată din produsul logic al maxtermilor pentru care funcţia ia valoarea 0.Observaţie: FCNC are atâţia maxtermi câte valori de 0 are funcţia
![Page 28: Reprezentarea funcţiilor booleeneiota.ee.tuiasi.ro/~cghaba/SPME/spmeNotecurs/Reprezentarea FB.pdf · zGrafice zAnalitice. Reprezent ări grafice zTabele de adevăr zScheme de operatori](https://reader030.fdocumente.com/reader030/viewer/2022040109/5e604632e05f9b41cd3a8a07/html5/thumbnails/28.jpg)
Reprezentarea FB folosind simboluri
Există două varianteANSI/IEEE 91-1973IEC
![Page 29: Reprezentarea funcţiilor booleeneiota.ee.tuiasi.ro/~cghaba/SPME/spmeNotecurs/Reprezentarea FB.pdf · zGrafice zAnalitice. Reprezent ări grafice zTabele de adevăr zScheme de operatori](https://reader030.fdocumente.com/reader030/viewer/2022040109/5e604632e05f9b41cd3a8a07/html5/thumbnails/29.jpg)
Reprezentarea FB folosind simboluri
≥1
≥1
&
&
=1
=1
ANSI/IEEE 9 1-1973 ANSI/IE EE 91/1984 (IEC)
NU (NOT)
SI (A ND)
SAU-NU (NOR)
SI-NU (NAND)
SAU-EXCLUSIV (XOR)
SAU-EXCLUSIV-NU (XNOR )
SAU (OR)
![Page 30: Reprezentarea funcţiilor booleeneiota.ee.tuiasi.ro/~cghaba/SPME/spmeNotecurs/Reprezentarea FB.pdf · zGrafice zAnalitice. Reprezent ări grafice zTabele de adevăr zScheme de operatori](https://reader030.fdocumente.com/reader030/viewer/2022040109/5e604632e05f9b41cd3a8a07/html5/thumbnails/30.jpg)
Reprezentarea FB folosind simboluri