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

Obs. Acestea se mai pot numi Adevarat (engl. True) respectiv Fals (engl. False), Pornit (engl. On) respectiv Oprit (engl. Off)

doua operatii binare numite SAU (OR engl.) notata simbolic + sau respectiv SI (AND engl.) notate simbolic prin sau Ù

operatie unara numita NU negatie, notata simbolic printr-o bara deasupra a ceea ce se neaga sau cu simbolul Ø

Operatiile se definesc astfel:

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:

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

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

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

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

Ambele operatii admit cate un element neutru cu proprietatea:

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

x₁ x₁ = x₁

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

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:

Principiul dublei negatii

dubla negatie duce la o afirmatie

Idempotenta

x x = x

x + x = x

Absorbtia

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

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

Proprietatile elementelor neutre

x x 1 = x

x + 0 = x    x + 1 = 1

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:

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.

Tabele de adevar

Unei functii booleene cu n variabile ii putem asocia un tabel care are 2ⁿ + 1linii care corespund celor 2ⁿ combinatii posibile ale variabilelor, precum a n+1 coloane care reprezinta cele n variabile plus una care reprezinta valorile corespunzatoare ale functiei.

De exemplu pentru functia F(x,y)=x+y avem 2 vaiabile deci vom vrea un tabel cu 5 linii si 3 coloane

In cazul care functia booleana este exprimata sub forma de expresie, pentru a ajunge la tabelul de adevar trebuie realizate mai multe calcule prin care sa ne dam seama care este tabelul de adevar corespunzator funtiiei date. De exempu functia: pentru a ajunge la tabelul de adevar trebuie sa realizam mai multe calcule intr-un mod asemanator unor calcule algebrice obisnuite numai ca folosind regulile si principiile algebrei booleene. Pentru ca in formularea functiei apare nagatul pentru z si pentru z in primul rand vom calcula acele valori apoi succesiv vom construi tabelul de adevar pentru funtia data. Pentru aceasta