Elemente de algebra booleana

Generalitati

Transferul, prelucrarea si pastrarea datelor numerice sau nenumerice in interiorul unui calculator se realizeaza prin intermediul circuitelor de comutare. Aceste circuite se caracterizeaza prin faptul ca prezinta doua stari stabile care se deosebesc calitativ intre ele. Starile sunt puse in corespondenta cu valorile binare "0" si "1" sau cu valorile logice "adevarat" si "fals" (din acest motiv se mai numesc si circuite logice). Pornind de la aceste considerente, un domeniul al logicii matematice, (stiinta care utilizeaza metode matematice in solutionarea problemelor de logica) numit "algebra logicii" si-a gasit o larga aplicare in analiza si sinteza circuitelor logice. Algebra logicii opereaza cu propozitii care pot fi adevarate sau false. Unei propozitii adevarate i se atribuie valoarea "1", iar unei propozitii false i se atribuie valoarea "0". O propozitie nu poate fi simultan adevarata sau falsa, iar doua propozitii sunt echivalente din punct de vedere al algebrei logice, daca simultan ele sunt adevarate sau false. Propozitiile pot fi simple sau compuse, cele compuse obtinandu-se din cele simple prin legaturi logice de tipul conjunctiei , disjunctiei sau negatiei

Bazele algebrei logice au fost puse de matematicianul englez George Boole (1815-1864) si ca urmare ea se mai numeste si algebra booleana. Ea a fost conceputa ca o metoda simbolica pentru tratarea functiilor logicii formale, dar a fost apoi dezvoltata si aplicata si in alte domenii ale matematicii. In 1938 Claude Shannon a folosit-o pentru prima data in analiza circuitelor de comutatie.

Definirea axiomatica a algebrei booleene

Algebra booleana este o algebra formata din:

elementele

2 operatii binare numite SAU si SI, notate simbolic + sau si sau

1 operatie unara numita NU negatie, notata simbolic  sau

Operatiile se definesc astfel:

SI SAU NU

0 0 = 0       0 + 0 = 0 0 = 1

0 1 = 0       0 + 1 = 1 1 = 0

1 0 = 0       1 + 0 = 1

1 1 = 1       1 + 1 = 1

Axiomele algebrei booleene sunt urmatoarele:

Fie o multime M compusa din elementele x₁, x₂,.x_n, impreuna cu operatiile si +. Aceasta multime formeaza o algebra daca:

1)     Multimea M contine cel putin 2 elemente distincte x₁ x₂ (x₁,x₂I M);

2)     Pentru x₁ I M, x₂ I M avem:

x₁ + x₂ I M si x₁ x₂ I M

3)     Operatiile si + au urmatoarele proprietati:

a.     sunt comutative

x₁ x₂ = x₂ x₁

x₁ + x₂ = x₂ + x₁

b.     sunt asociative

x₁ (x₂ x₃) = (x₁ x₂) x₃

x₁ + (x₂ + x₃) = (x₁ + x₂) + x₃

c.      sunt distributive una fata de cealalta

x₁ (x₂ + x₃) = x₁ x₂ + x₁ x₃

x₁ + (x₂ x₃) = (x₁ + x₂) (x₁ + x₃)

4)     Ambele operatii admit cate un element neutru cu proprietatea:

x₁ + 0 = 0 + x₁ = x₁

x₁ 1 = 1 x₁ = x₁

unde 0 este elementul nul al multimii, iar 1 este elementul unitate al multimii.

5)     Daca multimea M nu contine decat doua elemente, acestea trebuie sa fie obligatoriu elementul nul 0 si elementul unitate 1; atunci pentru x I M exista un element unic notat cu x cu proprietatile:

principiul contradictiei

      principiul tertului exclus

x este inversul elementului x.

In definirea axiomatica a algebrei s-au folosit diferite notatii. In tabelul urmator se dau denumirile si notatiile specifice folosite pentru diverse domenii:

Proprietatile algebrei booleene

Plecand de la axiome se deduc o serie de proprietati care vor forma reguli de calcul in cadrul algebrei booleene. Aceste proprietati sunt:

1)     Principiul dublei negatii

    dubla negatie duce la o afirmatie

2)     Idempotenta

x x = x

x + x = x

3)     Absorbtia

x₁ (x₁ + x₂) = x₁

x₁ + (x₁ x₂) = x₁

4)     Proprietatile elementelor neutre

x 0 = 0               x 1 = x

x + 0 = x              x + 1 = 1

5)     Formulele lui De Morgan

Aceste formule sunt foarte utile datorita posibilitatii de a transforma produsul logic in suma logica si invers.

Formulele pot fi generalizate la un numar arbitrar de termeni:  

6)     Principiul dualitatii - daca in axiomele si proprietatile algebrei booleene se interschimba 0 cu 1 si + cu , sistemul de axiome ramane acelasi, in afara unor permutari.

Verificarea proprietatilor se poate face cu ajutorul tabelelor de adevar si cu observatia ca doua functii sunt egale daca iau aceleasi valori in toate punctele domeniului de definitie. Prin tabelul de adevar se stabileste o corespondenta intre valorile de adevar ale variabilelor si valoarea de adevar a functiei.

Obs. Comutativitatea si asociativitatea pot fi extinse la un numar arbitrar, dar finit, de termeni, indiferent de ordinea lor.