Analiza și Sinteza Dispozitivelor Numerice

Curs 1

CAPITOLUL I

ELEMENTE DE ALGEBRA BOOLEANA

1.1. Generalitati

Transferul, prelucrarea si pastrarea datelor numerice sau nenumerice în 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 între ele. Starile sunt puse în 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 în solutionarea problemelor de logica) numit “algebra logicii” si-a gasit o larga aplicare în 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 d.p.d.v. al algebrei logice, daca simultan ele sunt adevarate sau false. Propozitiile pot fi simple sau compuse, cele compuse obtinându-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 în alte domenii ale matematicii. În 1938 Claude Shannon a folosit-o pentru prima data în analiza circuitelor de comutatie.

1.2. Definirea axiomatica a algebrei booleene

Algebra booleana este o algebra formata din:

- elementele {0,1};

- 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 x1, x2,…xn, împreuna cu operatiile × si +. Aceasta multime formeaza o algebra daca:

1) Multimea M contine cel putin 2 elemente distincte x1 ¹ x2 (x1,x2Î M);

2) Pentru " x1 Î M, x2 Î M avem:

x1 + x2 Î M si x1 × x2 Î M

3) Operatiile × si + au urmatoarele proprietati:

a. sunt comutative

x1 × x2 = x2 × x1

x1 + x2 = x2 + x1

b. sunt asociative

x1 × (x2 × x3) = (x1 × x2) × x3

x1 + (x2 + x3) = (x1 + x2) + x3

c. sunt distributive una fata de cealalta

x1 × (x2 + x3) = x1 × x2 + x1 × x3

x1 + (x2 × x3) = (x1 + x2) × (x1 + x3)

4) Ambele operatii admit câte un element neutru cu proprietatea:

x1 + 0 = 0 + x1 = x1

x1 × 1 = 1 × x1 = x1

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

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

x × x = 0 principiul contradictiei

x + x = 1 principiul tertului exclus

x este inversul elementului x.

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