CURS PDN

Algebra Booleana

1. Elemente de algebra booleana

� Algebra Boole a fost concepută de către matematicianul englez George Boole (1815 ÷ 1864) ca o metodă simbolică de tratare a funcŃiilor logicii formale. Abia în 1938, Claude Shannon avea să o utilizeze pentru prima oară la analiza circuitelor de comutaŃie.

� Algebra Boole, cunoscută şi sub denumirea de Algebra logică sau Calculul propoziŃional, operează cu propoziŃii despre care se poate afirma că sunt adevărate sau false. Fiecărei propoziŃii i se poate asocia o variabilă (numită variabilă logică sau binară) care ia valoarea 1 când propoziŃia este adevărată şi 0 când propoziŃia este falsă.

� PropoziŃiile pot fi simple sau compuse.� PropoziŃiile compuse sunt cele a căror valoare de adevăr depinde de

valoarea de adevăr a propoziŃiilor simple din care se compun şi de tipul legăturilor logice dintre acestea.

� Legăturile logice (operaŃiile) de bază sunt prezentate în tab. 1.1.� Se observă că denumirile şi simbolurile operaŃiilor logice diferă de la un

domeniu la altul. În cele ce urmează, vom utiliza aproape exclusiv notaŃiile din matematică

� PropoziŃia compusă poartă numele de funcŃie logică sau funcŃie binară şi ia valoarea logică 1 când este adevărată şi 0 când este falsă.

� FuncŃia logică este complet definită cu ajutorul unui tabel finit (tabel de adevăr) având în primele coloane valorile logice ale propoziŃiilor simple (considerate independente) şi în ultima coloană - valorile logice ale funcŃiei, obŃinute prin aplicarea operaŃiilor logice asupra valorilor logice corespunzătoare ale propoziŃiilor simple.

1.1. FuncŃii logice elementare

� Pornind de la expresia generală a unei funcŃii de n variabile binare,

� observăm că numărul total de termeni care se pot construi cu ajutorul celor n variabile binare este m = 2n, iar numărul total de funcŃii care rezultă combinând între ei cei m termeni este:

� Particularizând relaŃiile (1.2) pentru n = 0, 1 şi 2 variabile, obŃinem:- pentru n = 0, Nf0 = 2 funcŃii şi anume y1 = 0 şi y2 = 1;- pentru n = 1, deci y = f (x), Nf1 = 4 funcŃii şi anume y1 = 0, y2 = 1, y3 = x,

y4 = ;- pentru n = 2, deci y = f (x1, x2), se obŃin Nf2 = 16 funcŃii pe care le

prezentăm în tabelul 1.2.

� Deşi tabelul 1.2 este sugestiv prin el însuşi, prezentăm în continuare unele observaŃii şi comentarii utile:- ordinea x2x1 a variabilelor din tabelele de adevăr decurge din modul de scriere binară a unui număr zecimal:

unde xn este - după cum se observă - bitul cel mai semnificativ, iar x1 -bitul cel mai puŃin semnificativ.

Observatii:- cele 16 funcŃii apar în perechi (funcŃia şi inversa ei);- y1 şi y2, nu depind de x1 şi x2, deci nu sunt funcŃii ci constante;- y3 (y5) şi y4 (y6), nu depind de x2 (x1), deci nu sunt funcŃii de două variabile, ci doar de una

singură;- din tabelele de adevăr ale funcŃiilor y7 şi y8, care corespund circuitelor ŞI (AND), respectiv ŞI-

NU (NAND), observăm că y7=1 (y8=0), numai dacă ŞI x1 ŞI x2 sunt 1 logic, deci ŞI întrerupătorul X1 ŞI întrerupătorul X2 sunt acŃionate;

- din tabelele de adevăr ale funcŃiilor y9 şi y10, care corespund circuitelor SAU (OR), respectiv SAU-NU (NOR), observăm că y9=1 (y10=0), numai dacă SAU x1, SAU x2, SAU ambele sunt 1 logic, deci SAU întrerupătorul X1, SAU X2, SAU ambele sunt acŃionate;

- y11=1, numai atunci cînd valorile logice ale variabilelor de intrare COINCID, deci întrerupătoarele X1 şi X2 sunt fie ambele neacŃionate, fie ambele acŃionate;

- y12=1, numai atunci cînd SAU x1, SAU x2, EXCLUSIV ambele sunt 1 logic;- y13=0 (y14=1), numai dacă x1=1 şi x2=0, deci numai dacă X1 este acŃionat şi X2 este neacŃionat;- y15=0 (y16=1), numai dacă x1=0 şi x2=1, deci numai dacă X1 este neacŃionat şi X2 este acŃionat.

� Exprimarea matematică a unei funcŃii logice necesită introducerea axiomelor şi a regulilor de calcul ale algebrei Boole.

1.2. Axiomele algebrei Boole

Fie o mulŃime M compusă din n elemente (x1, x2, ..., xn) şi operaŃiile "⋅“(produs logic) şi "+" (sumă logică) deja prezentate.Spunem că mulŃimea M formează o algebră Boole dacă:

1. MulŃimea M conŃine cel puŃin două elemente distincte:

2. Pentru orice xi, xj ∈ M, avem:

3. OperaŃiile "⋅" şi "+" prezintă următoarele proprietăŃi:a) comutativitatea:

b) asociativitatea:

c) distributivitatea (uneia faŃă de cealaltă):

4. Ambele operaŃii admit câte un "element neutru" cu proprietatea:

5. Pentru orice x ∈ M, va exista un element (non x) cu proprietăŃile:

RelaŃiile 1.14 şi 1.15 poartă numele de principiul contradicŃiei, respectiv -principiul terŃului exclus şi se enunŃă astfel:Principiul contradicŃiei: o propoziŃie nu poate fi şi adevărată şi falsă în acelaşi timp.Principiul terŃului exclus: o propoziŃie este sau adevărată, sau falsă, o a treia posibilitate fiind exclusă.

1.3 Regulile de calcul ale algebrei Boole

Pornind de la axiome, se deduc următoarele teoreme care devin reguli de calcul în cadrul algebrei Boole:

1. Principiul dublei negaŃii:

2. IdempotenŃa:

3. AbsorbŃia:

4. Legile elementelor neutre:

5. Formulele lui De Morgan:

1.4. Exprimarea algebrică a funcŃiilor booleene

O funcŃie logică de n variabile independente, y = f (x1, x2, ..., xn), poate fi exprimată algebric sub formă canonică (disjunctivă sau conjunctivă), sub formă elementară (disjunctivă sau conjunctivă) sau sub formă neelementară.

1.4.1. Forma canonică

Forma canonică presupune operarea cu termeni canonici. Prin termen canonic înŃelegem un termen în care sunt prezente toate variabilele independente, luate sub formă directă sau negată.

1.4.1.1. Forma canonică disjunctivă

În cadrul formei canonice disjunctive (FCD) termenii sunt legaŃi între ei prin disjuncŃii, iar variabilele - în cadrul fiecărui termen, numit "constituent al unităŃii" - prin conjuncŃii.

Se observă că există funcŃii de două variabile, sau, în general, , unde s-a notat cu n numărul variabilelor de intrare.Forma canonică disjunctivă generală a unei funcŃii de două variabile este deci:

sau comprimat:

Pentru o funcŃie de n variabile, FCD este:

1.4.1.2. Forma canonică conjunctivă

În cadrul formei canonice conjunctive (FCC), termenii sunt legaŃi între ei prin conjuncŃii, iar variabilele - în cadrul fiecărui termen, numit "constituent al lui zero" - prin disjuncŃii.

Pentru o funcŃie de n variabile, FCC este:

1.4.2. Forma elementară

Forma elementară (FE) are în alcătuire cel puŃin un termen elementar. Prin termen elementar înŃelegem un termen care nu conŃine toate cele nvariabile ale funcŃiei, deci care nu este canonic.La forma elementară se ajunge prin minimizare.

1.4.3. Forma neelementară

FuncŃiile logice scrise sub formă canonică sau elementară (ambele, disjunctive sau conjunctive) pot fi aduse la forma neelementară (FNE) dacă există variabile sau grupuri de variabile comune mai multortermeni.Comparativ cu formele din care provin, formele neelementare se pot implementa cu circuite logice având un număr mai mic de intrări, dar structurate pe mai multe niveluri logice.

1.5. Reprezentarea fct. booleene cu diagramele Veitch - Karnaugh

� Un alt mod de reprezentare a funcŃiilor booleene în afara tabelului de adevăr (TA) îl constituie diagrama Veitch - Karnaugh (VK).

� Reluând exemplul funcŃiei de două variabile ŞI (AND) al cărei tabel de adevăr este tab. 1.5, observăm corespondenŃa celor patru combinaŃii logice ale variabilelor x1 şi x2 cu vârfurile unui pătrat de latură l = 1, desenat în planul (x1, x2), fig. 1.4.

� Este uşor de sesizat faptul că orice sens de deplasare am alege pe conturul pătratului din fig. 1.4, coordonatele unui vârf diferă de coordonatele unui vârf vecin prin valoarea logică a unui singur bit.

Fig. 1.4. Un model de ordonare ciclică a combinaŃiilor logice ale celor două variabile de intrare.

� Rearanjând liniile tabelului de adevăr (tab. 1.5) după modelul sugerat în fig. 1.4, obŃinem tab. 1.6 în care oricare două linii vecine, inclusiv prima cu ultima, diferă între ele prin valoarea logică a unei singure variabile.Tab. 1.5. Tabelul de adevăr al funcŃiei

ŞI (AND) de două variabile

Tab. 1.6. Explicativ pentru construireacodului binar reflectat al uneifuncŃii de două variabile

� Examinând primele două coloane ale tab. 1.6, constatăm că ele se pot obŃine prin introducerea unei "oglinzi" după 21 = 2 linii pentru coloana x1şi după 22 = 4 linii pentru coloana x2.

� Desigur, reflectarea în oglindă a valorilor logice ale variabilei x2 nu mai are loc deoarece numărul de linii ale TA al unei funcŃii de două variabile este 22 = 4.

� Codul binar reflectat obŃinut în tab. 1.6 mai este cunoscut şi sub denumirea de cod ciclic sau cod Gray.

� Prezentând tab. 1.6 într-o formă în care valorile logice alocate variabilelor x1 şi x2 constituie adresele celor 22 = 4 locaŃii în care funcŃia ia valori, obŃinem diagrama VK a funcŃiei AND de două variabile, fig. 1.5.

� Faptul că diagrama VK are caracter ciclic este evidenŃiat de prima şi ultima coloană care pot fi considerate vecine deoarece diferă între ele prin valoarea logică a unui singur bit de adresă (00 - 10).Fig. 1.5. Diagrama VK a funcŃiei

ŞI (AND) de două variabile

� Diagrama VK din fig. 1.5 poate fi deci privită ca un cilindru obŃinut prin curbarea figurii şi suprapunerea laturilor din stânga şi din dreapta (îngroşate în desen), devenite generatoare.

� În cazul unei funcŃii (AND) de trei variabile, liniile tabelului de adevăr (tab. 1.7) pot fi puse în corespondenŃă cu coordonatele vârfurilor unui cub, fig. 1.6.

Fig. 1.6. Un model de ordonare ciclică a combinaŃiilor logice ale celor 3 variabile de intrare

Tab. 1.7. Tabelul de adevăr al funcŃiei

ŞI (AND) de 3 variabile

� Observăm şi în acest caz, că diferenŃa coordonatelor a două vârfuri vecine ale cubului este - orice drum am alege - de un singur bit, fapt care ne sugerează o rearanjare a tab. 1.7 pe principiul codului binar reflectat, tab. 1.8.

Tab. 1.8. Explicativ pentru construirea codului binar reflectat al unei funcŃii de 3 variabile

� Dispunerea "oglinzilor" în tab. 1.8 se face la fiecare 21 = 2 locaŃii în coloana lui x1, la fiecare 22 = 4 locaŃii în coloana lui x2 şi la fiecare 23 = 8 locaŃii în coloana lui x3.

� Diagrama VK corespunzătoare tabelului 1.8 poate fi prezentată de maniera din fig. 1.7 a sau b.

� Ambele prezentări permit evidenŃierea ciclicităŃii prin curbarea figurilor, suprapunerea laturilor îngroşate şi transformarea dreptunghiului în cilindru.

� În fig. 1.7 b au fost marcate numai zonele în care variabilele iau valoarea logică 1.

Fig. 1.7. Două modalităŃi de reprezentare a diagramei VK a unei funcŃii de 3 variabile

Pentru funcŃii de patru variabile diagrama VK poate fi reprezentată ca în fig. 1.8 a sau b.

În ambele cazuri este respectat principiul ciclităŃii, pătratul care reprezintă diagrama VK putînd fi transformat în cilindru atît în cazul în care se suprapun laturile verticale, cât şi în cazul în care se suprapun laturile orizontale.Într-adevăr, locaŃia 0000 este vecină atît cu locaŃia 0010 cât şi cu 1000.Pentru funcŃii de cinci variabile se utilizează două tabele alăturate de tipul celui din fig. 1.8.a (sau b), unul pentru x5 şi altul pentru 5.Pentru funcŃii de mai mult de cinci variabile, utilizarea diagramelor VK devine anevoioasă şi este preferabil să se recurgă la alte metode, algebrice sau tabelare.

Fig. 1.8. Două modalităŃi dereprezentare a diagramei

VK a unei funcŃii de 4 variabile

1.6. Minimizarea funcŃiilor logice

� Cu cât o funcŃie logică are o expresie mai simplă (conŃine mai puŃini termeni, iar termenii - mai puŃine variabile), cu atât circuitul logic rezultat prin implementarea funcŃiei este mai simplu (conŃine mai puŃine porŃi logice, porŃile având un număr mai mic de intrări), fiabilitatea sa creşte, iar preŃul de cost scade. Suntem, prin urmare, deosebit de interesaŃi în simplificarea (minimizarea) formei analitice a unei funcŃii booleene, având astfel garanŃia obŃinerii unui circuit logic mai simplu şi mai performant.

� OperaŃiunea de minimizare poate fi aplicată funcŃiilor logice exprimate sub formă canonică (disjunctivă sau conjunctivă), precum şi funcŃiilor logice incomplet definite.

� Minimizarea unei funcŃii logice poate fi făcută fie cu ajutorul diagramelor VK, fie prin metode analitice.

1.6.1. Minimizarea cu ajutorul diagramelor VK� Minimizarea funcŃiilor logice cu ajutorul diagramelor VK constă în

parcurgerea următoarelor etape:

A. Alcătuirea diagramei VK şi completarea locaŃiilor acesteia cu valorile logice corespunzătoare termenilor funcŃiei.

� Astfel, în cazul unei exprimări sub forma canonică disjunctivă (FCD) a funcŃiei, fiecărui termen îi corespunde o locaŃie care conŃine "1" logic, iar în cazul exprimării sub formă canonică conjunctivă (FCC) - o locaŃie care conŃine "0" logic.

� Evident, atât în cazul FCD cât şi în cazul FCC, locaŃiile cărora nu le corespunde nici un termen canonic vor primi valori logice complementare celor menŃionate mai sus, iar cele ce corespund unor stări nedeterminate (cazul funcŃiilor incomplet definite) se vor marca cu "*" şi vor fi interpretate, după caz, ca "0" sau "1" logic, în procesul de minimizare.

B. Minimizarea propriu-zisă� Minimizarea poate fi de tip disjunctiv sau conjunctiv în funcŃie de

conŃinutul "1" sau "0" logic al locaŃiilor cu care se operează.� Ea constă din două etape şi anume:

B.1. Gruparea locaŃiilor vecine ce conŃin "1" ("0") logic în grupe de câte 20, 21, ..., 2k locaŃii.

� łinând seama de faptul că oricare două locaŃii vecine din diagrama VK diferă între ele prin valoarea logică a unei singure variabile, gruparea a 2 (21) locaŃii vecine care au acelaşi conŃinut conduce la eliminarea acelei variabile care, înregistrînd o variaŃie logică de la o locaŃie la alta, nu poate caracteriza grupul. Prin urmare, în cazul unei funcŃii de n variabile, doi termeni canonici conŃinând câte n variabile fiecare şi care corespund celor două locaŃii vecine grupate, vor fi înlocuiŃi cu un singur termen format din n-1 variabile;

� Generalizînd, gruparea a 2k locaŃii vecine care au acelaşi conŃinut şi care corespund celor 2k termeni canonici formaŃi din câte n variabile fiecare, conduce la eliminarea a k variabile şi, prin urmare, la obŃinerea unui singur termen format din n-k variabile.

� La realizarea grupărilor de locaŃii vecine ce conŃin "1" ("0") logic, este necesară respectarea următoarelor reguli:

r1) fiecare locaŃie din diagrama VK care prezintă interes din punct de vedere al tipului de minimizare utilizat, poate face parte din oricât de multe grupări, dar cel puŃin din una;

r2) cel mai avansat grad de simplificare se obŃine dacă locaŃiile ce conŃin "1" ("0") logic din diagrama VK formează un număr minim de grupuri, fiecare grup conŃinând la rândul său un număr cât mai mare de locaŃii.

B.2. Scrierea formei minimale a funcŃiei� Forma minimală disjunctivă (FMD) sau conjunctivă (FMC) conŃine atâŃia

termeni câte grupări de locaŃii au fost realizate. LocaŃiilor izolate, care nu au putut fi cuprinse în nici o grupare, le vor corespunde termenii canonici iniŃiali din care au provenit. Grupurilor de 2k locaŃii le vor corespunde termeni elementari formaŃi din câte n-k variabile care caracterizează grupul.

� În cadrul FMD (FMC), termenii canonici şi/sau elementari, vor fi legaŃi între ei prin disjuncŃii (conjuncŃii) iar variabilele în cadrul fiecărui termen se vor afla în conjuncŃie (disjuncŃie) şi vor fi luate direct sau negat astfel încât termenul respectiv să devină un constituent al unităŃii (al lui zero).

Exemplu:

Considerăm o funcŃie logicăde 3 variabile dată fie printabelul de adevăr (tab. 1.9), fie prin FCD (rel 1.40) sau FCC (rel. 1.41):

Indiferent de la care din cele 3 forme pornim, se obŃine aceeaşi diagramă VK din fig. 1.9, în care am notat cu P1, P2, ..., P5 locaŃiile ce conŃin "1" logic şi corespund termenilor din FCD, iar cu S1, S2, S3 locaŃiile ce conŃin "0" logic şi corespund termenilor din FCC.

Fig. 1.9. Diagrama VK a funcŃiei din exemplul considerat

e1) ObŃinerea FMDGrupând, spre exemplu, P1P2, observăm că gruparea a 21 = 2 locaŃii va trebui să conducă la eliminarea unei singure variabile de intrare din cele 3: x3 = 0 - caracterizează ambele locaŃii şi se reŃine sub forma ; x2 = 1 - caracterizează ambele locaŃii şi se reŃine sub forma x2; în sfîrşit, x1 este 1 pentru locaŃia P1 şi 0 pentru locaŃia P2, deci x1 variază în cadrul grupului de locaŃii P1P2 şi dispare. Termenul elementar care caracterizează complet grupul P1P2 este şi se trece în fig. 1.9.Procedând analog cu grupul P4P5 se obŃine termenul elementar x3x2, iar pentru grupul P3P4, termenul x3x1.RelaŃia 1.40 devine, prin urmare:

dar aceasta nu reprezintă o formă minimală!

Într-adevăr, conform regulii r2, se poate obŃine un grad şi mai ridicat de simplificare a funcŃiei, grupând împreună locaŃiile P1P2P4P5. După cum rezultă din consideraŃiile expuse la punctul B.1, gruparea a 22 = 4 locaŃii va conduce la eliminarea a două din cele 3 variabile. Termenul elementar ce va corespunde grupului P1P2P4P5 se obŃine astfel: x3 este 0 pentru P1P2 şi 1 pentru P4P5, deci variază în cadrul grupului de 4 locaŃii şi dispare; x2 este 1 pentru P1P4 şi tot 1 pentru P2P5, deci nu variază şi se reŃine sub forma x2; în sfîrşit, x1 este 1 pentru grupul P1P4 şi 0 pentru P2P5, deci variază în cadrul grupului de 4 locaŃii şi dispare. Termenul elementar rezultat este x2, iar forma minimală disjunctivă a funcŃiei (1.40) este:

e2) ObŃinerea FMCPentru scrierea FMC, se grupează S1S2 şi S1S3.Grupul de locaŃii S1S2 este caracterizat de x3 = 0 şi x2 = 0. Variabila x1 variază în cadrul grupului şi, necaracterizându-l, dispare. Termenul elementar rămas este (x3 + x2).

Pentru grupul de locaŃii S1S3 se elimină x3 care variază în cadrul grupului şi rămâne termenul elementar (x2 + x1).Forma minimală conjunctivă a funcŃiei (1.41) este, prin urmare:

Comparând relaŃiile 1.40 cu 1.43 sau 1.41 cu 1.44, minimizarea formelor algebrice ale funcŃiei este evidentă. Totuşi, pentru eliminarea oricăror semne de întrebare, implementăm în fig. 1.10 şi fig. 1.11 formele canonice şi cele minimale.Simplificarea structurilor logice prin minimizare este acum absolut vizibilă.

ObservaŃii:

1. Cele două forme minimale (rel. 1.43 şi 1.44) sunt convergente.Într-adevăr, prelucrând relaŃia (1.44) obŃinem:

2. Forma minimală (disjunctivă sau conjunctivă) nu este unică, deşi ea conŃine un anumit număr (minim) de termeni, fiecare dintre aceştia fiind constituit dintr-un anumit număr (minim) de variabile de intrare. Prin urmare, se pot obŃine două sau mai multe forme "la fel de minimale", dar niciodată o formă "mai minimală" decât alta!

Considerând, pentru exemplificare, diagrama VK din fig. 1.12, constatăm că grupările P1P3 şi P2P5 sunt "obligatorii", în timp ce P4 se poate grupa fie cu P3, fie cu P5, în ambele variante rezultând forme "la fel de minimale".

Fig. 1.12. Explicativă pentru obŃinerea unor forme "la fel de minimale"

1.6.2. Minimizarea prin metoda analitică

� Minimizarea prin metoda analitică are acelaşi domeniu de aplicabilitate ca şi cea realizată cu ajutorul diagramei VK.

� Minimizarea de tip disjunctiv porneşte de la FCD în care se grupează termenii care diferă prin valoarea logică a unei singure variabile (proprietatea de distributivitate), după care se elimină variabila care este în disjuncŃie cu negata sa (principiul terŃului exclus).

Exemplu:

Reluând exemplul de la paragr. 1.6.1, rel. 1.40, etapele minimizării prinmetoda analitică sunt:- gruparea perechilor de termeni P1P2, P3P4 şi P4P5, dând factor comun grupurile de variabile comune; observăm că termenul P4 a fost "prins" în două grupări, ceeace echivalează cu scrierea sa de două ori, fapt permis de principiul idempotenŃei;

- eliminarea parantezelor pe baza principiului terŃului exclus;- gruparea termenilor elementari P12 P45, dând factor comun variabila comună x2;- eliminarea parantezelor (principiul terŃului exclus);- scrierea FMD.Schematic, etapele minimizării sunt prezentate mai jos:

� Minimizarea de tip conjunctiv este similară celei de tip disjunctiv cu următoarele deosebiri: se porneşte de la FCC în care se fac grupările respective, după care se elimină variabila care se află în conjuncŃie cu negata sa (principiul contradicŃiei).Prezentăm, pe acelaşi exemplu, etapele minimizării de tip conjunctiv:

1.6.3. Minimizarea funcŃiilor incomplet definite� În cazul funcŃiilor incomplet definite, vom asocia în diagrama VK simbolul

"*" pentru acele puncte din domeniul de definiŃie în care funcŃia nu este definită.

� În timpul minimizării funcŃiei, simbolului "*" i se atribuie valoarea logică "0" sau "1", după cum dictează interesele minimizării.

1.6.4. Concluzii

� Deşi minimizarea prin metoda analitică urmează practic aceiaşi paşi cu minimizarea bazată pe diagrama VK, ea este mult mai dificilă dearece grupările de termeni sunt mai greu de observat.

� Minimizarea bazată pe diagramele VK devine complicată pentru mai mult de 5 variabile de intrare.

� Întrucât FMD şi FMC sunt convergente, este indicat să se utilizeze acea variantă de minimizare care conduce la o formă mai simplă. Adeseori se optează însă pentru varianta implementabilă cu circuitele logice disponibile la utilizator: FMC în cazul în care se dispune în majoritate de porŃi NOR şi FMD în cazul în care se dispune în majoritate de porŃi NAND.