Notiuni de algebra booleana

NOTIUNI DE ALGEBRA BOOLEANA

1.DEFINITII,PROPRIETATI,LEGI SI PRINCIPII

Algebra booleana este o multime nevida in care sunt definite doua legi de compozitie,SI (AND) notata si SAU (OR) notata + si o aplicatie a acestei multimi in ea insasi numita NU (NOT) notata - si care respecta urmatoarele proprietati,principii si legi:

1.Idempotenta x∙x=x x+x=x

2.Comutativitatea x∙y=y∙x x+y=y+x

3.Asociativitatea (x∙y)∙z=x∙(y∙z) (x+y)+z=x+(y+z)

4.Distributivitatea x∙(y+z)=x∙y+x∙z x+(y∙z)=(x+y)∙(x+z)

5.Absortia x∙(x+y)=z x+(x∙y)=x

6.Existenta unui prim element,0,a.i. x∙0=0 x+0=x

7.Existenta unui ultim element,1,a.i. x∙1=1 x+1=1

8.Legea dublei negatii =x

9.Principiul tertului exclus x+=1

10.Principiul contradictiei x∙=0

11.Legile lui De Morgan = x∙y=x+y

Daca multimea in care definim legile de compozitie si aplicatia identica este multimea binara B=,spunem ca am definit algebra binara:<,+,∙,¯,>.Astfel,putem defii complet functiile SI,SAU si NU.Tabele de adevar contin domeniile de definitie,codomeniile si relatiile dintre elemente.

SI

NU

SAU

2.EXPRESII BOOLEENE

2.1 DEFINITIA EXPRESIEI BOOLEENE

O expresie booleana este o expresie care se obtine prin aplicarea de un nr finit de ori a operatorilor SAU,SI,NU,asupra uor variabile booleene determinate,regulate sau neregulate.

Exemple:

Expresii booleene corecte: a¯∙c + a∙b∙ (a + b)¯∙ c+ 0.

Expresii booleene incorecte: a + b; x∙z+1

Observatii!

-Exista prioritati ale operatiilor in cadrul unei expresii,astfel:negarea are prioritatea cea mai mare,apoi SI si apoi SAU.In cazul in care apar paranteze,se acorda prioritate operatiilor din paranteze.

-Operatorul SI (∙) poate fi omis.

2.2 VALOAREA UNEI EXPRESII BOOLEENE

Pentru o expresie de variabile x,x, . ,x se numeste valoarea expresiei booleene pentru sirul de valori v,v, . ,v.

Exemple:

E(x,y)=x∙y + x∙y pentru x=0; y=1 are valoarea E(0,1)=0∙1 + 0∙1=0∙1 + 1∙1=1

2.3 EGALITATEA EXPRESIILOR BOOLEENE

Doua expresii booleene,de aceleasi variabile,se numesc egale sau echivalente daca au aceleasi siruri de valori ale variabilelor,expresiile iau aceleasi valori.

Observatie!Demonstrarea egalitatii expresiilor booleene poate fi facuta si prin calcul boolean,prin aducerea expesiilor la aceiasi forma.

Exemplu:E(a,b)=a + a∙b=(a + a¯) ∙ (a + b)=a + b=E(a,b)

2.4 FORMELE EXPRESIILOR BOOLEENE

Pentru a defini formulele expresiilor booleene trebuie mai intai sa definim urmatoarele notiuni:

a) Produsul elementar,este produsul (operatia SI) a doua sau mai multe variabile simple sau negate luate o singura data.

b) Suma elementara,este o suma (operatie SAU) a doua sau mai multe variabile simple sau negate luate o singura data.

c) Mintermenul,este un produs elementar care contine toate variabilele unei expresii.

Observatie:Mintermenilor li se poate asocia un numar binar astfel:

pentru variabila simpla,cifra binara 1.

pentru variabila negata,cifra binara 0.

De exemplu mintermenului ii corespunde numarul binar 101, mintermenului AB , numarul binar 1100. Deoarece fiecare numar binar are o valoare, se obisnuieste ca mintermenii sa se noteze cu m(mintermen) sau P(produs standard) unde indicele reprezinta valoarea numarului binar asociat. De exemplu m=P=, m=P=C, pentru expresii de trei variabile, sau m=P=, m=P=C, pentru expresii de patru variabile.

d) Maxtermenul,este o suma elementara care contine toate variabilele unei expresii.

Exemplu:Daca x,y,z sunt variabilele expresiei atunci + y + z; x + + sunt maxtermeni.

Observatie: Utilizand asocierea 0 -variabila simpla si 1 -variabila negate, maxtermenii se pot nota cu M(maxtermen) sau S(suma standard) unde indicele i este valoarea numarului binar asociat.De exemplu M=S=A + B + C, M= S= A + B + , pentru expresii de trei variabile, sau M=S=A + B + C + D, M= S= A + B + C + , pentru expresii de patru variabile.

e) Forma normala disjunctiva a unei expresii booleene, este o suma (operatii SAU) de produse elementare. Valoarea expresiei normale disjunctive este 1 logic daca cel putin unul din termeni este 1 logic.

Exemplu: expresiile x∙y + ∙z + x∙y∙z si a∙b∙ + c∙d au forme normale disjunctive.

f) Forma normala conjunctiva a unei expreii booleene,este o suma (operatii SAU) de mintermeni.Valoarea expresiei canonice disjunctive ste 1 logic daca cel putin unul din mintermeni este 1 logic.

Exemplu: (x + y + z)(x + y + ) si (a + )(c + d) au forme normale conjuctive.

g)Forma canonica disjunctive a unei expresii booleene,este o suma (operatii SAU) de mintermeni.Valoarea expresiei canonice disjunctive este 1 logic daca cel putin unul din mintermeni este 1 logic.

Exemplu: Expresia x∙∙z + x∙y∙z + ∙y∙ sau m + m+ m respective P + P+P de variabile x,y,z este o expresie canonica disjunctive.

Observatii:

-Se prefera ca termenii sa se scrie in ordine crescatoare a indicilor,in cazul expresiei prezentate in exemplul:m+m+m respectiv P+P+P.

-Notiunea de expresie canonica disjunctive poate fi inlocuita cu notiunea de lista a minitermenilor si se poate scrie,pentru exemplul astfel:

h)Forma canonica conjunctiva a unei expresii booleene,este un produs(operatii SI) din maxtermeni.Valoarea expresiei canonice conjunctive este 0 logic daca cel putin unul sin maxtermeni este 0 logic.

Exemplu:Expresia(x++z)∙(x+y+)∙(+y+) sau M∙M∙M respectiv S∙S∙S de variabile x,y,z este o expresie canonica conjunctiva.

Observatii:

-Si in acest caz se prefera ca termenii sa se scrie in ordine crescatoare a indicilor in cazul prezentat in exemplul :M∙M∙M respectiv S∙S∙S.

-Notiunea de expresie canonica conjunctiva poate fi inlocuita cu notiunea de lista maxtermenilor si se poate scrie astfel:∏ M(1,2,5).

-O expresie booleana poate avea mai multe forme normale,dar numai o singura forma canonica.

-De la oricare forma a unei expresii se poate ajunge la forma canonica si invers prin calcul boolean.

-Exista pentru orice expresie o forma normala care este considerate cea mai simpla.

Operatia de aducere a expresiei la aceasta forma se numeste minimizare.