ANALIZA SI SINTEZA DISPOZITIVELOR NUMERICE BIBLIOGRAFIE Mang Gerda Erica, - Analiza i sinteza circuitelor logice circuite combinaionale, Ed. Universitii Oradea, 2002, ISBN 973-8219-96-5 Mang Gerda Erica - Proiectare logica360p Mang Gerda Erica, Popescu Constantin - Proiectare logica cu circuite FPGA partea I Mang Gerda Erica, Tirtea Rodica - Proiectare logica cu circuite FPGA lucrari practice, 2006 Mang Erica, Popescu Constantin - Analiza si sinteza circuitelor logice culegere de probleme, Ed. Universitii Oradea, 2004,ISBN 973-613-267-7 Moris Mano - Digital Design, Prentice Hall, 1984; Xilinx Lab Projects Documentation, Foundation Series Express F1.4, 1998 Xilinx Lab Projects Documentation, Foundation Series Express F1.4, 1998; Xilinx The Programmable Logic Data Book, Xilinx Inc., 1997; Yarbrough John M. Digital Logic Applications and Design, Oregon Institute of Technology, West Publishing Company, 1997; 1 Cuprinsul cursului ASDN semestrul I CAPITOLUL 1 Algebra boolean. Aplicarea ei la studiul circuitelor de comutare CAPITOLUL 2 Minimizarea funciilor de comutare CAPITOLUL 3 Analiza i sinteza circuitelor combinaionale cu pori sau elemente logice CAPITOLUL 4 Exemple de circuite logice combinaionale 2 CAPITOLUL I ALGEBRA BOOLEAN. APLICAREA EI LA STUDIUL CIRCUITELOR DE COMUTARE DEFINIIA ALGEBREI BOOLEENE matematicianul irlandez: George Boole (1815-1864) - "Analiza legilor gndirii" Pentru definirea algebrei booleene se consider: o mulime notat cu B cu cel puin 2 elemente distincte, n care se definesc: 2 operaii: SAU iI, notate: + respectiv , irelaia de echivalen, notat cu = (reflexiv, simetric itranzitiv) 2 constante caracteristice: 0 i 1 4 Numim algebr boolean un sistem format de mulimea B nevid, cu relaia de echivalen, cele dou operaii fundamentale SAU i I i constantele caracteristice 0 i 1, care satisface urmtoarele axiome: A1) Operaia SAU este asociativ: a,b,ceB: (a + b) + c = a + (b + c) A2) Operaia I este asociativ: a,b,ceB: (a b) c = a (b c) A3) Operaia SAU este comutativ: a,beB:a + b = b + a A4) Operaia I este comutativ: a,beB:a b = b a A5) Exist un singur element neutru fa de operaia SAU, elementul neutru 0: aeB: a + 0 = 0 + a = a A6) Exist un singur element neutru fa de operaia I, elementul neutru 1: aeB: a 1 = 1 a = a A7) Operaia SAU este distributiv fa de operaia I: a,b,ceB: a + (b c) = (a + b) (a + c) A8) Operaia I este distributiv fa de operaia SAU: a,b,ceB: a (b + c) = a b + a c A9) Orice element a din B are un complement n B, notat cu , (se citeste NU a), astfel nct: a = 0i a += 1 5 a aaTEOREME T1) a + a = a(Teorema idempotenei)Demonstraie: teorema generalizat: a + a + a + ..... + a = a T2) a a = a Demonstraie: Generalizare:a a ... a = a T3) a + 1 = 1 6 a + a A6= (a + a)1 A9=(a + a)(a + _a) A7=a + a _a A9=a + 0 A5=a a a A5=a a + 0 A9=a a + a _a A8=a (a +_a) A9=a 1 A6=a a + 1 A6=(a + 1) 1 A9=(a + 1)(a + _a) A7=a + _a 1 A6=a + _a A9= 1 T4) a 0 = 0 T5) a + a b = a(Teorema absorbiei) T6) a (a + b) = a demonstraia - prin dualitate T7) Complementul unei variabile (a) este unic demonstraie: Presupunem c variabila a are 2 complemente, pe care le notm curespectiv . n baza axiomei 9 se poate scrie: 7 a 0 A5=a 0 + 0 A9=a 0 + a _a A8=a (0 + _a) A5=a _a A9=0 a + a b A6=a 1 + a b A8=a (1 + b) T3=a 1 = a 1a2aa + 1a= 1a + 2a= 1 a 1a= 0 a 2a= 0 1a = 1a 1 = 1a (a + 2a ) = 1a a + 1a 2a = 0 + 1a 2a = a 2a + 1a 2a= =2a (a + 1a ) = 2a 1a= 2a T8) Complementul complementului este variabila nsi: Demonstraie: Se determin complementul lui . innd cont de axiomele 3, 4 i 9 se poate scrie: Conform axiomei 9 i a teoremei 7, unicul complement al lui este a. Astfel putem spune c: T9)Teorema I a lui De MorganDemonstraie: Vom demonstra n prealabil 2 leme prin care se arat ceste complementul lui a + b. 8 ) a (= a aa + a = 1a a = 0 a) a (= a b a += a b a bL1 : a + b +a b = 1 L2 : (a + b) a b = 0 Conform A9 i a T7 este adevarata. T10)a II-a teorema a lui De Morgan Demonstraia - prin dualitate Lemele 3 i 4 fiind adevrate, conform A9 i a T7 9 L1:a + b +a b = (a + b +a)(a + b +b) = (1 + b)(1 + a)= 1 1 = 1 L2:(a + b) a b = a a b + b a b = 0 b + 0 a = 0 + 0 = 0 b a +=a bb a= a + b L3: a b + ( a+b) = 1 L4: a b ( a+b) = 0 L3: a b + ( a + b) = ((a + b) + a)((a + b) + b) = (1 + b) (b + 1) = 1 L4:a b ( a+b) = (a b) a + (a b) b = 0 b + 0 a = 0 b a=a + b T 11)a + b = a + b Demonstraie:a + b = (a +) ( a + b) = 1 (a + b) = a + b T 12) a ( + b) = a b Demonstraie: a (+ b) = a + a b = 0 + a b T 13)(a + b) ( + c) = a c + b Demonstraie: (a+b)(+ c) = (a + b) + (a + b)c == a+ b + ac + bc = b + ac + bc1 = b + ac + bc (a +) == b + ac + bca + bc = b(1+ c) + ac(1+b) = b + ac 10 aaaaa aa aa aa a a a aa a aaDOMENIIDEAPLICAREALEALGEBREI BOOLEENE n teoria mulimilor: elementele algebrei booleene sunt mulimi constanta 0 este mulimea vid, constanta 1 este mulimea tuturor elementelor operaiei i corespunde operaia de intersecie a mulimilor operaiei + i corespunde operaia de reuniune a mulimilor operaiei i corespunde operaia de complementare a unei mulimi. diagrame Venn:n care mulimea tuturor elementelor este mulimea punctelor incluse ntr-un ptrat, n interiorul cruia se consider mulimi de puncte incluse n diverse contururi nchise 11 Exemplul 1.1. Se va demonstra valabilitatea axiomei 7: A + B C = (A + B) (A + C) 12 n logic: algebra boolean s-a aplicat n felul urmtor: elementele algebrei booleene sunt propoziii logice care pot fi adevrate sau false. constanta 0 nseamn fals constanta 1 nseamn adevrat operaiile , + , reprezint conjunciile i, sau, respectiv negarea unei propoziii.nelesul acestor operaii este urmtorul: propoziia a i b este adevrat dac att propoziia a ct i propoziia b sunt adevrate, propoziia a sau b este adevrat dac fie propoziia a fie propoziia b este adevrat fie ambele sunt adevrate, negata propoziiei a este adevrat dac propoziia a este fals. Se poate atta c i n aceast interpretare sunt satisfcute toate axiomele algebrei booleene. 13 n studiul circuitelor de comutare: Se atribuie valorile unei mrimi fizice electrice (tensiune, curent) celor dou valori ale variabilelor booleene, 0 i 1. d > 0 Tensiunile din intervalul S se numesc niveluri H (High) I se numesc niveluri L (Low) Nivelurile de tensiune din cele dou domenii de valori S (H) i I(L), respect relaia: u1 e S iu2 e I u1 > u2 14 logic pozitiv : valorile maxime de tensiune 1 logic (1) i valorile minime de tensiune 0 logic (0) logic negativ : valorile maxime de tensiune 0 logic (0) i valorile minime de tensiune 1 logic (1) Schimbarea conveniei o negaie a variabilei booleene. n domeniul calculatoarelor electronice: Se folosesc elemente fizice care comport dou stri distincte, stri care pot fi puse n coresponden direct cu propoziii logice crora li se asociaz valoarea de adevrat sau fals. Aceste dou valori sunt asociate celor dou niveluri de potenial care pot schimba starea circuitelor respective. Unei propoziii adevrate i se atribuie valoarea 1, iar unei propoziii false - valoarea 0.15 Funciile logice se pot reprezenta sub forma unor expresii analitice sau sub forma unor tabele de adevr care conin valorile variabilelor n toate combinaiile posibile i valorile corespunztoare ale funciei dependente Operaia SAU (disjuncie) se mai numete sum boolean sau sum logic simboluri: + sau v. Operaia I (conjuncie) se mai numete produs boolean sau produs logic simboluri: , . sau &. Operaiile SAU, I respectiv NU (negaie) pot fi definite cu ajutorul tabelelor de adevr: 16 Tabelul 1.1. x 1 x 2 x 1 +x 2 x 1 x 2 x 1 x 2 x

00000001 01101010 101100 111111 x CIRCUITE DE COMUTARE CU PORI PARAMETRII CIRCUITELOR LOGICE 1. Caracteristici electrice statice - descriu comportarea circuitelor logice n current continuu sau la variaii lente n timp ale tensiunilor i curenilor prin circuit sunt: nivelele logice de intrare/ieire: - intervalele de tensiune pentru care se atribuie nivel logic 0 i nivel logic 1; curenii de intrare/ieire - curenii care se pot nchide prin intrarea/ieirea circuitului logic pentru nivelele de intrare/ieire; capacitatea de intrare - caracterizeaz intrrile n circuite logice MOS i reprezint capacitatea msurat ntre intrarea circuitului i mas. 17 Caracteristici electrice dinamice - descriu comportarea circuitelor logice la tranziii rapide ale semnalelor: timpul de propagare - intervalul de timp scurs ntre momentul de aplicare al semnalului la intrare i momentul n care se obine rspunsul la ieirea circuitului logic; timpul de tranziie - timpul necesar pentru tranziia de la nivel logic L la H (tTLH) i invers (tTHL); timpul de meninere (hold time) - intervalul de timp ct trebuie meninut neschimbat semnalul pe o intrare a unui circuit logic n comparaie cu o alt intrare considerat ca referin de timp, timpul de pregtire (setup time) - intervalul de timp cu care trebuie s precead semnalul de pe o intrare a unui circuit logic, semnalul prezent pe o alt intrare, considerat ca referin de timp 18 CIRCUITUL INVERSOR Tensiunile se aleg n aa fel nct: UP > US > UI > UN, rezistenele se aleg astfel ca: dac UA = UI tranzistorul este blocat prin rezistena R i dioda D se stabilete curentul: IL ~ (UP - US) / R, tensiunea la ieirea F va fi: UF = UP IL R = US 19 P R R1 R2 N (Potenial de limitare) A RS D L F IL 0 UI US dac UA = US tranzistorul intr n saturaie (conduce la limit) rezistena ntre colector i emitor estefoarte mic i poate fi neglijat fa de rezistena R prin rezistena R i tranzistor: IH ~ (UP UI) / R, tensiunea la ieirea F va fi: UF = UP IH R = UI Rolul diodei: Dac UP ar fi egal cu US dioda de limitare ar putea lipsi. Dar tensiunea de limitare i dioda au rolul de a asigura o tranziie mai rapid de la starea L la starea H 20 U UP (H) US (L) UI t FUNCII BOOLEENE funcia de transfer a unui circuit de comutare este o funcie booleean o funcie booleean f de n variabile, f(x1,x2,...,xn) - unde x1,x2,...,xn iau valorile 0 i 1 -, se definete ca o aplicaie a mulimii {0,1}n n mulimea {0,1} n mulimea {0,1}n exist 2n elemente, deci acestora li se pot atribui valorile {0,1} nmoduri diferite tabelul de coresponden pentru n = 3, n {0,1}3 exist 23 = 8 elemente cu cele 2 valori de 0 i 1 luate cte 3, se pot face 8 aranjamente cu repetiie 28 = 256 funcii. 21 n22 pentru 2 variabile 22 = 4 valori 24 = 16 funcii 22 Tabelul 1.3. x1x2x3f0f1f2...f255 000000...1 001000...1 010000...1 011000...1 :::::::: 110001...1 111010...1 Tabelul 1.4. x1 x2 f0f1f2f3f4f5f6f7f8f9f10 f11 f12 f13 f14 f15 000000000011111111 010000111100001111 100011001100110011 110101010101010101 Indicele funciei = echivalentul zecimal al numrului binar interpretat de la stnga la dreapta funcii degenerate - depind de una sau de nici una dintre variabile alte functii: 23 f0 = 0f5 = x2f12 = 1xf3 = x1f10 = 2xf15 = 1 f1 = x1 x2I f7 = x1 + x2SAU f6 = x1 x2SAU EXCLUSIV f9 = x1 x2I EXCLUSIV OPERAII CU FUNCII se definesc pe domeniul valorilor funciilor Definiie: Fie f, g i h 3 funcii booleene de n variabile. Se definete: f + g = hdac i numai dac f (x1,x2,...,xn) + g (x1,x2,...,xn) = h (x1,x2,...,xn) unde toi xi, i = 1,...,n, iau valorile 0 i 1, iar valorile funciilor se combin conform tabelului de coresponden al operaiei SAU. f g = h dac i numai dac f (x1,x2,...,xn) g (x1,x2,...,xn) = h (x1,x2,...,xn) unde toi xi, i = 1,...,n, iau valorile 0 i 1, iar valorile funciilor se combin conform tabelului de coresponden al operaiei I. = g dac i numai dac (x1,x2,...,xn) = g (x1,x2,...,xn) unde toi xi, pentru i = 1, ... , n, iau valorile 0 i 1. Funciile f, respectiv g, aplic fiecare din cele 2n n-uple n mulimea {0,1} 2n perechi de valori ale funciilor 24 ff Exemplul 1.2. Fie cteva funcii de 3 variabile definite prin tabelul de coresponden: Exemplu: se observ: f1 = x1 x2 x3 O caracteristic a unei funcii booleene este numrul de combinaii de valori ale variabilelor pentru care funcia ia valoarea 1 = ponderea funciei (w(f) sau w). 25 Tabelul 1.5 x1 x2 x3f0f1f3f4f5f8f13 5f0 0000000001 0 0100000001 0 1000000001 0 1100000001 1 0000000111 1 0100011010 1 1000100001 1 1101101010 Observatii: 26 1.) f ( w 2 ) f ( wn =2.) g f ( w ) g ( w ) f ( w ) g f ( w + = +3.) g f ( w ) g ( w ) f ( w ) g f ( w + + = FORME CANONICE ALE FUNCIILOR BOOLEENE Expresia algebric a funciilor elementare de pondere 1 este aa numitul termen minim. Exemplul 1.3.Din tabelul 1.5: f1 = x1 x2 x3 expresie echivalent a funciei sau funcie elementar. Expresia funciei cu pondere 1 se obine lund n termenul minim variabila (valoarea) direct atunci cnd ea are valoarea 1 n n-uplul corespondent, respectiv variabila (valoarea) negat atunci cnd ea are valoarea 0. Exemplul 1.4.Din tabelul 1.5 se poate scrie: 27 f8 = x1 2x 3xf4 = x1 2x x3 Orice funcie de pondere > 1 poate fi scris n mod unic sub forma unei sume booleene de funcii elementare Aceast form de scriere este unic i se numete form canonic disjunctiv (FCD). Exemplul 1.5. FCD poate fi folosit pentru recunoaterea funciilor echivalente (pentru c FCD este unic) Termenii minimi se mai numesc i termeni p sau termeni produs boolean 28 f13 = f1 + f4 + f8 f13 = x1 x2 x3 + x1 2x x3 + x1 2x 3xf5 = f1 + f4 = x1 x2 x3 + x1 2x x3 Exemplul 1.6. Negata unei funcii se obine inversnd valorile funciei din tabelul de coresponden Ponderea negatei este: Orice funcie boolean poate fi scris i sub forma unui produs de sume booleene - form canonic conjunctiv (FCC) Exemplul 1.7. 29 f5 = 35p+ 37psau f5 (x1,x2,x3) = p5+ p7 = (5,7) w 2 wn =) FCD ( x x x x x x x x xx x x x x x x x x f3 2 1 3 2 1 3 2 13 2 1 3 2 1 3 2 1 5 + + ++ + + = Pentru a obine forma canonic conjunctiv a funciei se calculeaz negata negatei funciei: Aplicnd teorema lui De Morgan (T10) se obine: 30 3 2 1 3 2 1 3 2 13 2 1 3 2 1 3 2 1 5x x x x x x x x xx x x x x x x x x f =) FCC () x x x ( ) x x x ( ) x x x () x x x ( ) x x x ( ) x x x ( f3 2 1 3 2 1 3 2 13 2 1 3 2 1 3 2 1 5+ + + + + + + + + + + + =REPREZENTAREA GEOMETRICA FUNCIILOR Se consider un cub n dimensional i se noteaz cele 2n vrfuri ale sale cu n-uple de zerouri i uniti astfel nct dou vrfuri legate printr-o muchie s fie notate cu n-uple de 0 i 1 adiacente (s difere printr-o singur poziie) 31 0 1 01 11 00 10 001 101 000 100 111 011 010 110 Teorem: Orice funcie boolean de n variabile poate fi reprezentat n mod unic ca o submulime de vrfuri ale n-cubului. Demonstraie: ntre funciile m(x1,x2,...,xn) i vrfurile n-cubului exist o coresponden biunivoc. Dar orice funcie boolean se poate scrie n mod unic sub forma unei sume booleene de funcii elementare submulimea de vrfuri ale n-cubului se poate reprezenta n mod unic o funcie boolean. 32 Exemplul 1.8. Se d funcia : 33 0001 0101 0000 0100 01110011 0010 0110 1001 1101 1000 1100 1111 1011 10101110 f (x1,x2,x3,x4) =) x , x , x , x ( m4 3 2I i1 ie unde I = {0,3,5,7,15} EXPRESII BOOLEENE DEFINIIE Expresiile sau formulele booleene generate de n variabile, notate x1,x2,...,xn, se definesc inductiv n felul urmtor: 0 i 1 sunt expresii booleene; dac xi este o variabil booleean, atuncixi (i=1, ... , n) este o expresie booleean; dacA este o expresie boleean, atunci ieste o expresie booleean; dac A i B sunt expresii booleene, atunci A + B este o expresie booleean; dac A i B sunt expresii booleene, atunci A B este o expresie booleean; expresii booleene sunt numai cele date de punctele 15. 34 AObservatii: exist o infinitate de expresii booleene generate de n variabile, ns o parte dintre acestea sunt echivalente ntre ele o serie de clase de echivalen care sunt finite atta timp ct n este finit pentru a arta c dou expresii sunt echivalente, (fac parte din aceai clas de echivalen): se pot folosi axiomele i teoremele algebrei booleene tabelele de coresponden pentru operaiile+,i- 35 EXPRESIA NORMAL DISJUNCTIV DEFINIIE Numim expresie normal disjunctiv o expresie sub forma unei sume booleene de termeni produs, care nu sunt n mod obligatoriu termeni canonici, respectiv termeni minimi Exemplul 1.9. expresie normal disjunctiv se poate transforma ntr-o expresie de form canonic disjunctiv introducnd n fiecare termen variabila care lipsete, fr a modifica ns expresia: Dou expresii care pot fi aduse la aceai form canonic sunt echivalente ntre ele 36 E = x1 2x+ x2 x3 E = x12x ( x3 + 3x ) + (x1 + 1x )x2x3 = = x12x x3 + x12x 3x + x1 x2 x3 + 1x x2 x3 EXPRESIA NORMAL CONJUNCTIV expresie dat sub form de produs boolean de factori scrii sub form de sum boolean, care nu conin ns toate variabilele ce genereaz expresia dat forma normal conjunctiv (FNC) poate fi adus la FCC folosind o procedur asemntoare cu cea artat la forma normal disjunctiv Pentru o funcie boolean dat exist: 2n termeni (factori) canonici (3n 1) factori normali (termeni normali) dintre care 2n sunt termeni canonici 37 EXPRESII BOOLEENE DUALE din axiomele i teoremele algebrei booleene dualitatea ntre operaia SAU i operaia I axiomele referitoare la operaia I se pot obine din cele referitoare la operaia SAU prin schimbarea operatorilor+ i , respectiv a constantei 1 cu 0 Duala unei expresii A, notat Ad, se definete inductiv astfel: 1. 0d = 1; 2. 1d = 0; 3. Dac xi, pt. i=1,...,n, este o variabil boolean atunci = xi; 4. Dac A, B i C sunt expresii booleene iA = B + C, atunci Ad = Bd Cd; 5. Dac A, B i C sunt expresii booleene iA = B C, atunci Ad = Bd + Cd; 6. Dac A i B sunt dou expresii booleene iA =, atunci i Ad = 38 dixBdB Exemplul 1.10. Observatii: n expresia dual variabilele apar n aceai form ca i n expresia iniial n expresia negat toate variabilele apar negate 39 Duala expresiei A =z ) y x (+ este Ad =z y x + Duala expresiei B =xy z y x + + + esteBd =) y x ( z y x + Negnd expresiile A si B rezult:A= z y x z y x z y x + = + + = +B=) y x ( z y x + TEOREM Dac A este o expresie booleean de variabile x1,x2, ... ,xn, avnd functia corespondent fA(x1,x2, ... ,xn), atunci funcia corespondent dualei Ad, este dat de relaia: de asemenea se poate afirma ca dac dou expresii booleene sunt echivalente, A = B atunci i dualele lor sunt echivalente:Ad = Bd

Exemplu: duala unei expresii este expresia funciei negate de variabile negate 40 ) x ,..., x , x ( f ) x , ... , x , x ( fn 2 1 A n 2 1dA=x1 x2f13 2 1x xd13f f4 13f00111000 01110110 10001001 11100000 2 1 2 1 2 1 2 1x x x x x x x x + + = +f13= Ed = d13f =4 2 1f x x = 13f= 2 1 2 1x x x x = SISTEME COMPLETE DE OPERAII orice funcie boolean de n variabile poate fi reprezentat printr-o expresie boolean, format prin aplicarea de un numr finit de ori asupra variabilelor, a funciilor fundamentale sau operaiilor SAU, I, NU folosind alte operaii logice n locul operaiilor SAU, I i NU se pot forma de asemenea expresii logice care s defineasc toate funciile logice de n variabile DEFINIIEO mulime de operaii {o1, o2, ... , ok} se numete sistem complet de operaii n algebra funciilor de n variabile, Bn, dac i numai dac pentru orice funcie f de n variabile exist o expresie A format din cele n variabile i operaiile o1, o2, ... , ok astfel nct A s-l reprezinte pe f. 41 Exemplul 1.12. Mulimea operaiilor {+,,-} formeaz un sistem complet de operaii, deoarece cu ajutorul acestora se poate scrie FCD, respectiv FCC a oricrei funcii de n variabile. Un sistem complet de operaii este minim dac nlturnd oricare dintre operaiile sistemului, acesta devine incomplet Sistemul de operaii {+,,-} nu este minim deoarece nlturnd operaia + sau sistemul rmne complet: TEOREM:Sistemul de operaii {, -} este complet. Demonstraie: 42 2 1 2 12 1 2 1x x x xx x x x = ++ = 2 1 2 1x x x x = + Analog:sistemul de operaii {+,-} este complet Sistemele de operaii {,-} i {+,-} sunt minime deoarece nlturnd oricare dintre cele 2 operaii sistemul devine incomplet TEOREM:Operaia SAU-NU formeaz un sistem complet notat {}.Demonstraie:se pot realiza operaiile + i -, astfel: 43 1 1x x = 1 1 1 1x x x x = + =x1 + x2 = (x1 x2) (x1 x2) = 2 1 2 1 2 1x x x x x x + = + + +x1 x2 = (x1 x1) (x2 x2) == + = + + +2 1 2 2 1 1x x x x x x x1x2 x1 x2 = x2 x1

- comutativ x1 (x2 x3) = (x1 x2) x3 - nu este asociativ - sunt valabile relaiile: 0 x2 = 1x1x x1 = 0 1 x1 = 0 x1 x1 = 1x TEOREM:Operaia I-NU formeaz un sistem complet notat {/}.Demonstraie: 44 1 1x x =/ 1 1 1 1x x x x = =x1 + x2 = (x1 / x1) / (x2 / x2) = 2 1 2 2 1 1x x x x x x = x1 x2 = (x1 / x2) / (x1 / x2) = 2 1 2 1 2 1x x x x x x = Pr opr iet i: x1 / x2 = x2/ x1- comut at iv x1 / (x2 / x3) = (x1 / x2) / x3 - nu est e asociat iv 0 / x2 = 11x / x1 = 1 1 / x1 = 1x x1 / x1 = 1x TEOREM:Sistemul de operaii {,} este complet, unde prin s-a notat operaia numit implicare. Demonstraie: Duala operaiei implicare este operaia numit inhibare. Operaia inhibare, mpreun cu constanta 1, formeaz un sistem de operaii complet 45 x1 + x2 = 1x x2 = x1 + x2 x1 x2 =2 1 2 1 2 1x x x x x x = + = Pr opr iet i: x1 x2 = x2 x1- nu est e comut at ivx1 x1 = 10 x1 = 1 x1 1x = 1x1 x1 = x1 x1 1 = 1x1 x2 = 2x 1xx1 0 = 1x (x1 x2) 1x= x1 TEOREM:Operaiile SAU EXCLUSIV ()i I formeaz mpreun cu constanta 1 un sistem de operaii complet, {,,1}. Demonstraie: 46 x 0 x 1 x 1 x x = + = =x1 + x2 = (x1x2) x1x2 = == + + +2 1 2 1 2 1 2 1 2 1 2 1x x ) x x x x ( x x ) x x x x (2 1 2 1 2 1 2 12 1 2 1 2 1 2 1 2 1 2 1x x x x x x x x) x x )( x x x x ( x x ) x x )( x x (+ = + + == + + + + + = Proprieti: x1 x2 = x2 x1 - comutativ x1 (x2 x3) = (x1 x2) x3- asociativ x1 (x2 x3) = x1 x2 x1x3 - distributiv fa de operaia I x x = 0x 0 = x x 1 =xx x = 1 MODURI DE REPREZENTARE Pentru familia TTL se folosesc simbolurile: 47 AB A B I A B AB I-NU A+B + SAU A B A+B + SAU-NU A B AB A B A B AB A B A+B A B A+B Folosind pori TTL I-NU se pot obine operaiile de baz din algebra booleean: 48 xx xx x1 x2 x1 x2 x1 x2 x1 x2x1 x2 x1 x2 = x1 x2 Realizarea operaiilor NU i I folosind pori TTL I-NU x1 x2x1 x2 x1 x2 x1

x1

x2x2

x1 + x2 Alte modaliti de obinere ale operaiilor I respectiv SAUCLASE DE FUNCII BOOLEENE. FUNCII AUTODUALE DEFINIIE O funcie boolean de n variabile se numete funcie autodual dac: sau: dac o funcie autodual este reprezentat printr-o expresie A, ea poate fi reprezentat i prin duala acelei expresii, Ad, expresia corespunztoare unei funcii autoduale i duala expresiei fiind n acest caz echivalente Exemplul 1.14 funcia minoritar de trei variabile - aplic 1 acelor n-upluri n care majoritatea variabilelor au valoarea zero negata funciei minoritare - funcia majoritar 49 ) x ,..., x , x ( f ) x , ... , x , x ( fn 2 1 n 2 1=dn 2 1A A ) x , ... , x , x ( f = =50 Tabelul 1.7. x1 x2 x3fMIN fMAJx1 x2 x3fMIN (x1,x2,x3) fMIN (x1,x2,x3) 0 0 0101 1 101 0 0 1101 1 001 0 1 0101 0 101 0 1 1011 0 010 1 0 0100 1 101 1 0 1010 1 010 1 1 0010 0 110 1 1 1010 0 010 ) FND ( x x x x x x) FCD ( x x x x x x x x x x x x ) x , x , x ( f3 2 3 1 2 13 2 1 3 2 1 3 2 1 3 2 1 3 2 1 MIN+ + == + + + =) FCD ( x x x x x x x x x x x x f f3 2 1 3 2 1 3 2 1 3 2 1 MAJ MIN+ + + = =) FND ( x x x x x x f3 1 2 1 3 2 MIN+ + =) FND ( ) x x ( ) x x ( ) x x ( f f3 1 2 1 3 2 MIN MIN+ + + = = S-a demonstrat deci, att pe cale analitic ct i cu ajutorul tabelului de coresponden, c fMIN este o funcie autodual deoarece: adic: Acelai lucru se poate spune i despre negata ei - funcia majoritar TEOREM: Numrul funciilor autoduale este: 51 ) x , x , x ( f ) x , x , x ( f3 2 1 MIN 3 2 1 MIN=) 0 , 0 , 1 ( f ) 1 , 1 , 0 ( fMIN MIN=NFAD = 1 n22 FUNCII SIMETRICE DEFINIIE O funcie boolean de n variabile f(x1,x2, ... ,xn) se spune c este simetric dac i numai dac rmne neschimbat la orice permutare a variabilelor ei. Exemple de functii simetrice: - funcia majoritar - funcia SAU EXCLUSIV TEOREM O funcie boolean de n variabile este simetric dac exist m numere naturale a1, a2, ...,aj, ...,am unde me{0,1,...,n}, iar 0 s aj s n astfel nct funcia s ia valoarea 1, dac i numai dac aj dintre variabile au valoarea 1 52 1 2 1 2 2 1 2 1 2 1 2 1x x x x x x x x x x ) x , x ( f + = + = = simetrie o posibilitate de scriere: indicnd ponderile n-uplelor ce se aplic n 1: unde n reprezint numrul de variabile iar indicele inferior reprezint ponderile n-uplelor aplicate n 1 Exemple: funcia SAU EXCLUSIV (XOR): funcia majoritar: funcia SUM : Numrul funciilor simetrice de n variabile, notat NS(n) este: NS(n) = 2n+1 53 { }nl , k , jS{ }21S{ }33 , 2S{ }33 , 1S TEOREM:Suma logic a dou funcii simetrice de aceleai variabile, SA(x1,x2, ...,xn) i SB(x1,x2, ...,xn), este o funcie simetric de aceleai variabile: SC(x1,x2, ...,xn) = SA(x1,x2, ...,xn) + SB(x1,x2, ...,xn) a crei mulime de numere aj este C, undeC = AB. TEOREM:Produsul logic a dou funcii simetrice de aceleai variabile, SA(x1,x2, ...,xn) i SB(x1,x2, ...,xn), este o funcie simetric de aceleai variabile: SC(x1,x2, ...,xn) = SA(x1,x2, ...,xn) SB(x1,x2, ...,xn) a crei mulime de numere aj este C, undeC = A B TEOREM:Negata unei funcii simetrice de n variabile, SA(x1,x2,...,xn) este o funcie simetric: SC(x1,x2, ...,xn) =a crei mulime de numere aj este C = N A definit simbolic astfel: N A = {xxeN i xeA} 54 ) x ..., , x , (x Sn 2 1 AFUNCII CU PRAG o mulime de numere reale care reprezint ponderile variabilelor: w1,w2, ...,wn un numr real, numit prag: T DEFINIIE O funcie boolean cu n variabile este funcie cu prag dac ndeplinete condiiile: wi se nmulete aritmetic cu 0 i 1, iar E este o sum aritmetic 55 < => ===T x w daca , 0 ) x ,..., x x ( fT x w daca , 1 ) x ,..., x x ( fin1 ii n 2 1in1 ii n 2 1 vom reprezenta geometric funciile luate ca exemplu, i vom considera n-uplele ca vrfuri ale unui hipercub cu latura egal cu unitatea se noteaz combinaiile de valori ale variabilelor pentru care funcia f(x1,x2,...,xn) ia valoarea 0 cu f-1(0), iar cele pentru care funcia ia valoarea 1 cu f-1(1) n reprezentarea geometric a funciilor booleene de n variabile ecuaia: w1x1 + w2x2 + ... + wnxn = T definete un hiperplan (n-1) dimensional care separ vrfurile f-1(1) ale n-cubului de vrfurile f-1(0) dac i numai dac f(x1,x2, ...,xn) este o funcie cu prag: f(x1,x2,...,xn) = 1,dac w1x1+w2x2+...+wnxn > Tsi f(x1,x2, ...,xn) = 0, dac w1x1+w2x2+...+wnxn > T toate vrfurile f-1(1) vor fi de o parte a planului sau coninute n plan, iar vrfurile f-1(0) de cealalt parte 56 Exemplul 1.15. fp(x1,x2,x3) = x1x3 + x2x3 Planul: 1/2 x1 + 1/2 x2 + x3 = 5/4 57 x1 x2x3fpw1x1 + w2x2 + w3x3 0000 0+0+0=0 += =-1,5 x w x w daca 0-1,5 x w x w daca 1x x ) x , x ( f2 2 1 12 2 1 12 1 2 1 01 1000 11 x2 x1 FUNCII DE COMUTARE Funcia de transfer a unui circuit de comutare se numete funcie de comutare. Dac valoarea unei funcii de comutare este precizat pentru toate combinaiile posibile de valori ale variabilelor de intrare, aceasta se numete funcie de comutare complet definit Dac nu se precizeaz valoarea funciei pentru toate combinaiile posibile de valori ale variabilelor de intrare, funcia se numete funcie de comutare parial sau incomplet definit, iar combinaiile de intrri pentru care valoarea funciei este nedefinit se numesc condiii nu ine cont. Unei funcii de comutare pariale de n variabile i corespunde o clas de funcii booleene Cf Numrul funciilor booleene din Cf depinde de numrul (r) combinaiilor nu ine cont: 2r 60 Exemplul 1.19. r = 2, clasa Cf corespondentfunciei fc, conine22 = 4 funcii booleene pentru reprezentarea algebric a funciilor de comutare pariale se alege acea funcie boolean din clasa Cf care are cea mai simpl form 61 x1 x2x3fpCf 00000 00 0 00111 11 1 01011 11 1 01100 00 0 10011 11 1 10111 11 1 110d0 01 1 111d0 10 1