Reprezentarea funcţiilor booleeneiota.ee.tuiasi.ro/~cghaba/SPME/spmeNotecurs/Reprezentarea...

Reprezentarea funcţiilor booleene

(în lucru)

Reprezentările FB pot fi:

GraficeAnalitice

Reprezentări grafice

Tabele de adevărScheme de operatori (porţi logice)Arbori de decizie binarăDiagrame Veitch-KarnaughScheme cu contacteHipercubDiagrame de semnale

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ă

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

Tabele de adevăr

Funcţie de 2 variabilefba

011

101

110

000

Tabele de adevăr

Funcţie de 3 variabile

1111

1011

1101

1001

0110

1010

0100

0000

fcba

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

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

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

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

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’

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’)

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

Tabele de adevăr şi mintermi


m3

m2

m1

m0

Notaţie

0

1

1

0

f Mintermiba

a.b11

a.b’01

a’.b10

a’.b’00

Tabele de adevăr


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

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

Tabele de adevăr şi mintermi


M3

M2

M1

M0

Notaţie

0

1

1

0

f Maxtermiba

a’+b’11

a’+b01

a+b’10

a+b00

Tabele de adevăr


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

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


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


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


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

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


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


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


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

Reprezentarea FB folosind simboluri

Există două varianteANSI/IEEE 91-1973IEC


≥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)

Reprezentarea funcţiilor booleeneiota.ee.tuiasi.ro/~cghaba/SPME/spmeNotecurs/Reprezentarea...

Documents

Transcript of Reprezentarea funcţiilor booleeneiota.ee.tuiasi.ro/~cghaba/SPME/spmeNotecurs/Reprezentarea...