Noțiuni de Algebră Booleană

CAPITOLUL I

NOŢIUNI DE ALGEBRĂ BOOLEANĂ

1.1. Definiţii, proprietăţi, legi şi principii.

Algebra booleană este o mulţime nevidă în care sunt definite două legi de compoziţie, ŞI (AND) notată • şi SAU (OR) notată + şi o aplicaţie a acestei mulţimi în ea însăşi numită NU (NOT) notată ־ şi care respectă următoarele proprietăţi, principii şi legi:

1. Idempotenţa 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. Absorbţia x ∙ (x + y) = x x + (x ∙ y) = x

6. Existenţa unui prim element 0, astfel încât x ∙ 0 = 0 x + 0 = x

7. Existenţa unui ultim element 1, astfel încât x ∙ 1 = x x + 1 = 1

8. Legea dublei negaţii = x

9. Principiul terţului exclus x + = 1

10. Principiul contradicţiei x ∙ = 0

11. Legile lui DeMorgan

Dacă mulţimea în care definim legile de compoziţie şi aplicaţia identică este mulţimea binară B2 = (0, 1), spunem că am definit algebra binară: <, (0, 1), +, ∙, ¯, >. Astfel putem defini complet funcţiile ŞI, SAU şi NU. Tabelele de adevăr conţin domeniile de definiţie, codomeniile şi relaţiile dintre elemente.

ŞI

x y x ∙ y

0 0 0

0 1 0

1 0 0

1 1 1

SAU

x y x + y

0 0 0

0 1 1

1 0 1

1 1 1

NU

x

0 1

1 0

Tabelele pot fi construite foarte simplu utilizând legile şi principiile algebrei booleene. De exemplu pentru prima şi ultima linie funcţiile Şi şi SAU poate fi utilizat principiul 1 dar şi principiile 6 şi 7, iar pentru liniile 2 şi 3 principiile 6 şi 7.

1.2. Expresii booleene.

1.2.1. Definiţia expresiei booleene. O expresie booleană este o expresie care se obţine prin aplicarea de un număr finit de ori a operatorilor SAU, ŞI, NU, asupra unei variabile booleene determinate sau nedeterminate, negate sau nenegate.

1.2.2. Valoarea unei expresii booleene. Pentru o expresie de variabile x1, x2,…xn, se numeşte valoarea expresiei booleene pentru şirul de valori v1, v2,…vn, valoarea obţinută prin înlocuirea variabilelor x1, x2, …xn cu valorile corespunzătoare v1, v2,…vn.

1.2.3. Egalitatea expresiilor booleene. Două expresii booleene, de aceleaşi variabile, sunt egale sau echivalente dacă pentru aceleaşi şiruri ale variabilelor, expresiile iau aceleaşi valori.

1.2.4. Formele expresiilor booleene. Pentru a defini formele expresiilor booleene trebuie mai întâi să definim următoarele noţiuni:

a).Produsul elementar, este produsul (operaţia ŞI) a două sau mai multe variabile simple sau negate luate o singură dată.

b). Suma elementară, este o sumă (operaţie SAU) a două sau mai multe variabile simple sau negate luate o singură dată.

c). Mintermenul, este un produs elementar care conţine toate variabilele unei expresii.

d). Maxtermenul, este o sumă elementară care conţine toate variabilele unei expresii.

e). Formula normală disjunctivă a unei expresii booleene, este o sumă (operaţii SAU) de produse elementare. Valoarea expresiei normale disjunctive este 1 logic dacă cel puţin unul din termeni este 1 logic.

f). Forma normală conjunctivă a unei expresii booleene, este un produs (operaţii ŞI) de sume elementare. Valoarea expresiei normale conjunctive este 0 logic dacă cel puţin unul din termeni este 0 logic.

g). Forma canonică disjunctivă a unei expresii booleene, este o sumă (operaţii SAU) de mintermeni. Valoarea expresiei booleene disjunctive este 1 logic dacă cel puţin unul din mintermeni este 1 logic.