g1u14um
Algebra booleana este o algebra formata din:
- elementele A0,1S;
- 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, impreuna cu operatiile × si +. Aceasta multime formeaza o algebra daca:
1) Multimea M contine cel putin 2 elemente distincte x1 ¹ x2 (x1,x2I M);
2) Pentru " x1 I M, x2 I M avem: x1 + x2 I M si x1 × x2 I 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 cate 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 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: x × x = 0 principiul contradictiei x + x = 1 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:

Matematica Logica Tehnica
Prima lege de compozitiex1 + x2 Disjunctiex1 Ú x2 SAUx1 + x2
A doua lege de compozitiex1 × x2 Conjunctiex1 Ù x2 SIx1 × x2
Elementul inversx NegareØx NUx

1.3. 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 x = x dubla negatie duce la o afirmatie
2) Idempotenta x × x = x x + x = x
3) Absorbtia x1 × (x1 + x2) = x1 x1 + (x1× x2) = x1
4) Proprietatile elementelor neutre x × 0 = 0 x × 1 = x x + 0 = x x + 1 = 1
5) Formulele lui De Morgan x1 × x2 = x1 + x2 x1 + x2 = x1 × x2
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: x1 × x2 × … × xn = x1 + x2 + … + xn x1 + x2 + … + xn = x1 × x2 × … × xn
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.

1.4. Functii booleene
O functie f: Bn ® B, unde B = A0,1S se numeste functie booleana. Aceasta functie booleana y = f(x1, x2,…,xn) are drept caracteristica faptul ca atat variabilele cat si functia nu pot lua decat doua valori distincte, 0 sau 1. Functia va pune in corespondenta fiecarui element al produsului cartezian n dimensional, valorile 0 sau 1. Astfel de functii sunt utilizate pentru caracterizarea functionarii unor dispozitive (circuite) construite cu elemente de circuit avand doua stari (ex.: un intrerupator inchis sau deschis, un tranzistor blocat sau in conductie; functionarea unui astfel de circuit va fi descrisa de o variabila booleana xi).

1.4.1. Functii booleene elementare
Revenim la forma generala a unei functii booleene de n variabile: y = f(x1, x2,…,xn)
Domeniul de definitie este format din m = 2n puncte. Deoarece in fiecare din aceste puncte functia poate lua doar valorile 0 si 1 rezulta ca numarul total al functiilor booleene de n variabile este N = 2m.
Vom considera in continuare functiile elementare de 1 variabila. Pentru n = 1 avem m = 2 si N = 4. Functia are forma y = f(x) si cele 4 forme ale ei se gasesc in tabelul urmator:

fi x 0 1 Reprezentare Denumire f0 0 0 0 Constanta 0 f1 0 1 x Variabila x f2 1 0 x Negatia lui x f3 1 1 1 Constanta 1

La fel se pot realiza toate functiile cu ajutorul unor functii de baza. Acestora le vor corespunde si niste circuite logice elementare, cu ajutorul carora se poate realiza practic orice tip de circuit. Tinand cont de faptul ca circuitele logice de comutatie au 2 stari stabile LOW (L) si HIGH (H), asignand lui L 0 si lui H 1 se poate intocmi un tabel al functiilor elementare.

Denumire Functie Simbol Tabel de adevar Tabel de definitie
Inversor -; NOT f = x x f = x x f 0 1 1 0 x f L H H L
Poarta SI -; AND f = x1 × x2 x1x2 f=x1×x2 x1 x2 f0 0 00 1 01 0 01 1 1 x1 x2 fL L LL H LH L L H H H
Poarta SAU -; OR f = x1 + x2 x1x2 f=x1+x2 x1 x2 f0 0 00 1 11 0 1 1 1 1 x1 x2 fL L LL H HH L H H H H
Poarta SI-NU -; NAND f = x1 × x2 x1x2 f=x1×x2 x1 x2 f0 0 10 1 11 0 1 1 1 0 x1 x2 fL L HL H HH L H H H L
Poarta SAU-NU -; NOR f = x1 + x2 x1x2 f=x1+x2 x1 x2 f0 0 10 1 01 0 0 1 1 0 x1 x2 fL L HL H LH L L H H L
SAU EXCLUSIV -; XOR f = x1 + x2 x1x2 f=x1 + x2 x1 x2 f0 0 00 1 11 0 1 1 1 0 x1 x2 fL L LL H HH L H H H L
COINCIDENTA f = x1 × x2 x1x2 f=x1 × x2 =x1 + x2 x1 x2 f0 0 10 1 01 0 0 1 1 1 x1 x2 fL L HL H LH L L H H H

1.4.2. Reprezentarea functiilor booleene
Exista doua moduri de reprezentare a functiilor booleene: grafica si analitica.
1. Modalitati grafice - se caracterizeaza printr-o reprezentare intuitiva, usor de retinut, dar sunt inadecvate pentru functii booleene cu un numar de variabile mai mare decat 4;
2. Modalitati analitice - sunt mai greoaie, dar permit metode automate, deci algoritmi de simplificare a functiei; se folosesc in general pentru functii booleene cu numarul variabilelor mai mare decat 5.
1.4.2.1. Modalitati de reprezentare grafica
Modalitatile de reprezentare grafica sunt: tabel de adevar, diagrama Karnaugh, schema logica, diagrama de timp.
1. Tabel de adevar -; se marcheaza intr-un tabel corespondenta dintre valorile de adevar ale variabilelor de intrare si valoarea de adevar a functiei, in fiecare punct al domeniului de definitie.
Pentru o functie cu n variabile de intrare vom avea 2n combinatii.
Exista situatii in care, pentru anumite combinatii ale variabilelor de intrare, valoarea functiei nu este specificata. Aceste functii se numesc incomplet definite. In tabel, in locul in care functia nu este specificata, se noteaza cu “X”. Daca o functie booleana este incomplet definita pentru “m” combinatii ale variabilelor de intrare se pot defini 2m functii noi prin alegerea arbitrara a valorilor incomplet definite.
2. Diagrama Karnaugh
O diagrama Karnaugh pentru o functie booleana de n variabile se deseneaza sub forma unui patrat sau dreptunghi impartit in 2n compartimente. Fiecare compartiment este rezervat unui termen canonic al functiei, respectiv unuia dintre varfurile cubului n dimensional din reprezentarea geometrica a functiei (2n n-uple ale functiei).
Diagrama Karnaugh este organizata astfel incat doua compartimente vecine pe o linie sau pe o coloana corespund la doi termeni canonici care difera numai printr-o singura variabila, care apare in unul adevarata, iar in celalalt negata (la doua n-pluri adiacente). Se considera vecine si compartimentele aflate la capetele opuse ale unei linii, respectiv coloane.
Diagrama Karnaugh se noteaza fie indicand domeniul fiecarei variabile, fie indicand pe linie si coloana n-uple de zerouri si unitati corespondente unui compartiment din diagrama si ordinea variabilelor. Prima notatie se foloseste in cazul in care se reprezinta functia prin forma ei canonica sau normala. A doua notatie se foloseste in cazul in care functia se reprezinta prin tabel de adevar. Pentru a putea reprezenta usor functii exprimate in mod conventional prin indicii termenilor canonici se poate nota fiecare compartiment cu indicele termenului corespondent, tinand cont de o anumita ordine a variabilelor.
Exemple:
1) Diagrama Karnaugh pentru functia de 2 variabile: f(x1, x2) = x1×x2 + x1×x2

x2 x1 0 1 x2 x1 0 1
0 x1x2 x1x2 0 0 1 x2 1 x1x2 x1x2 1 1 0 x1 sau x1
00 01 11 10 x2
Obs. Numerotarea liniilor si coloanelor se face in cod Gray (cod binar reflectat)

Cod binar direct Cod Gray
0000 0000
0001 0001
0010 0011
0011 0010
0100 0110
0101 0111
0110 0101
0111 0100
1000 1100
1001 1101
1010 1111
1011 1110
1100 1010
1101 1011
1110 1001
1111 1000
2) Diagrama Karnaugh pentru functia de 3 variabile: y = f(x1,x2,x3)
Domeniul de definitie este format din 23 = 8 puncte si reprezinta varfurile unui cub cu latura 1: x1

001 101
011 111

000 100 x3
010 110 x2

Diagramele Karnaugh corespunzatoare pot fi reprezentate astfel: x2

x1 x2x3 00 01 11 10
0 0 1 3 2 x1 1 4 5 7 6 x3 sau

x3 x1x2 x3 0 1
00 0 1
01 2 3 x2 x1 11 6 7
10 4 5
3) Diagrama Karnaugh pentru functia de 4 variabile: y = f(x1,x2,x3,x4) x4 x1x2 x3x4 00 01 11 10
00 0 1 3 2
01 4 5 7 6 x2 x1 11 12 13 15 14
10 8 9 11 10 x3
Prin sageti am marcat vecinatatile punctului de coordonate 0010.
4) Diagramele Karnaugh pentru functii de mai mult de 4 variabile se construiesc din diagrame de 4 variabile considerate ca diagrame elementare.
3. Schema logica -; reprezentare cu ajutorul simbolurilor circuitelor logice.
4. Diagrama de timp -; reprezentare utila pentru studiul unor forme tranzitorii de hazard in circuitele logice. Se reprezinta functii logice in a caror evolutie intervine timpul.
Exemplu: f = x1×x2

x1 x2 f