Automate si Microprogramare

36Algebra Boole. Functii logice

Algebra Boole. Functii logice39

ELEMENTE DE ALGEBR BINAR

Algebra Boole. Funcii logice

3.1Logica binar

3.1.1Definirea algebrei booleene ca latice

Se consider o mulime M nevid, mpreun cu dou operaii binare pe M, reuniune (() i intersecie ((). Tripletul: L = (M, (, () este o latice i se bucur de urmtoarele proprieti:

1) Comutativitate : m1 ( m2 = m2 ( m1 , (m1,m2(M.

m1 ( m2 = m2 ( m1

2) Asociativitate : m1 ( (m2 ( m3) = (m1 ( m2) ( m3 , (m1,m2,m3(M.

m1 ( (m2 ( m3) = (m1 ( m2) ( m33) Absorbie : m1 ( (m2 ( m1) = m1 , (m1,m2(M.

m1 ( (m2 ( m1) = m1Aceste proprieti constituie axiomele pentru latice. Se observ c simbolurile ( i ( se pot schimba ntre ele. Acest lucru rmne valabil n orice afirmaie ce decurge din sistemul de axiome, proprietate cunoscut sub denumirea de principiul dualitii pentru latici.

Avnd n vedere axiomele 1) i 2), operaiile de ( i ( se pot extinde la orice numr arbitrar, dar finit, de termeni, indiferent de ordinea termenilor sau factorilor:

(j=1,n mj = m1 ( m2 ( ... ( mn ;(j=1,n mj = m1 ( m2 ( ... ( mnPlecnd de la axiomele definite anterior, se poate demonstra pentru latici i proprietatea de idempoten: m ( m = m, m ( m = m, (m(M.

O latice se poate defini i ca o mulime parial ordonat: L = (M,() care are o cea mai mic margine superioar (c.m.m.m.s), notat cu s, i o cea mai mare margine inferioar (c.m.M.m.i), notat cu p, pentru fiecare pereche de elemente. Legtura ntre cele dou definiii ale laticelor se poate face notnd: s = m1 ( m2 i p = m1 ( m2.

O latice finit (mrginit) are un element care este c.m.M.m.i., numit ultim element al laticei, notat prin 0, astfel nct:

m ( 0 = m, m ( 0 = 0, (m(M,

i un alt element, care este c.m.m.m.s., numit prim element al laticei, notat prin 1, astfel nct:

m ( 1 = 1, m ( 1 = m , (m(M.

Se observ c 0 este elementul neutru n raport cu reuniunea, iar 1 este elementul neutru n raport cu intersecia.

Fie L = (M,(,(,0,1) o latice finit i m(M. Un element complementar (sau pe scurt, un complement) al elementului m este elementul: mc, astfel nct exist:

Principiul terului exclus:m ( mc = 1

Principiul contradiciei:

m ( mc = 0.

Trebuie menionat c nu orice element dintr-o latice finit are un complement i, de asemenea, complementul unui element al unei latice, dac acesta exist, nu este n mod necesar unic.

Dac ntr-o latice finit orice element are un complement unic, mc, aceast latice se numete complementar.

O latice L este distributiv dac i numai dac:

(m1 ( m2) ( m3 = (m1 ( m3) ( (m2 ( m3) , (m1,m2,m3(M.

(m1 ( m3) ( m3 = (m1 ( m3) ( (m2 ( m3)

Cele dou proprieti poart numele de distributivitatea reuniunii n raport cu intersecia i respectiv, distributivitatea interseciei n raport cu reuniunea.

O latice particular, care este distributiv i complementar, se numete algebr Boole. Aceasta se scrie ca un cvadruplu: B = (M,(,(,c), unde, operaia c este operaia unar de complementare.

3.1.2Proprietile algebrei booleene

O algebr boolean poate fi definit i prin proprietile sale. Fie o mulime M nevid, avnd un cel mai mic element, 0, numit i cea mai mare margine inferioar i un cel mai mare element, 1, numit i cea mai mic margine superioar a mulimii.

Considerm pe aceast mulime 3 operaii: reuniune, (, intersecie, (, (operaii binare, care implic minim 2 elemente) i operaia de complementare, c, operaie unar.

Prin definiie, o algebr Boole este un cvadruplu: B = (M, (, (, c). Pe o astfel de structur algebric sunt adevrate urmtoarele proprieti: 1) Comutativitate: m1 ( m2 = m2 ( m1 ,

m1 ( m2 = m2 ( m1 , (m1,m2(M.

2) Asociativitate:(m1 ( m2) ( m3 = m1 ( (m2 ( m3) ,

(m1 ( m2) ( m3 = m1 ( (m2 ( m3) , (m1,m2,m3(M.

3) Absorbie: m1 ( (m2 ( m1) = m1 ,

m1 ( (m2 ( m1) = m1 , (m1,m2(M.

4) Distributivitate:m1 ( (m2 ( m3) = (m1 ( m2) ( (m1 ( m3) ,

m1 ( (m2 ( m3) = (m1 ( m2) ( (m1 ( m3) , (m1,m2,m3(M.

5) Idempoten:m ( m = m, m ( m = m , (m(M.

6) Proprietile lui 1 i 0:m ( 0 = m ; m ( 0 = 0 ,

m ( 1 = 1 ; m ( 1 = m , (m(M.

7) Principiul terului exclus:m ( mc = 1, (m(M, (mc este complementul lui m)

ntr-o algebr Boole orice element are complement i acesta este unic.

8) Principiul nonconcordanei sau a contradiciei:m ( mc = 0, (m(M.

9) Principiul involuiei sau a dublei negri:(mc)c = m, (m(M.

10) Legile lui de Morgan:(m1 ( m2)c = (m1)c ( (m2)c ,

(m1 ( m2)c = (m1)c ( (m2)c , (m1,m2,(M.Cnd mulimea M cuprinde numai 2 elemente {0,1}, putem defini o algebr Boole cu dou valori: B2 = ({0,1}, (, (, c). Aceast algebr este foarte important n practic pentru studiul circuitelor logice.

n aceast algebr, cele 3 operaii se definesc pe elementele mulimii astfel :

(01(01m01

001000mc10

111101

n tehnic, aplicarea algebrei Boole i-a gsit o coresponden n ceea ce privete materializarea operatorilor logici.

Pentru operaii, n afara denumirilor menionate se mai folosesc i:

( = operaia SAU = disjuncia logic = suma logic.

Se mai noteaz cu: ( ( V ( +

(deci: m1 ( m2 ( m1 V m2 ( m1 + m2)

Deoarece suma logic nu se confund cu sumarea algebric, se evit ultimul simbol.

( = operaia I = conjuncia logic = produs logic.

Se mai noteaz cu: ( ( ( ( & ( (

(deci: m1 ( m2 ( m1 ( m2 ( m1 & m2 ( m1 ( m2 ( m1m2)

c = operaia NU = negarea logic = inversiunea logic

3.2Funcii booleene (FB)

3.2.1Definiii

Algebra boolean cu dou elemente, denumit i algebr bivalent, are aplicaie direct n teoria circuitelor de comutaie. n acest caz, ntre valorile mulimii {0,1} i cele dou stri ale elementelor de comutaie se stabilete o coresponden biunivoc. Astfel, o variabil asociat unui element de comutare poate lua numai dou valori, 0 i 1, fiind o variabil boolean bivalent, sau pe scurt, o variabil boolean. Rezult c pentru circuitele realizate cu elemente de comutaie modelul matematic l constituie funciile de variabile binare. Deoarece circuitele realizate cu elemente de comutaie nu pot avea dect dou stri distincte, funciile care descriu aceste circuite vor lua numai dou valori. Aceste funcii bivalente de variabile binare se numesc funcii booleene, sau funcii logice i au o deosebit importan pentru studiul circuitelor logice i comenzilor numerice.

Se consider vectorul X = (x1,x2,...,xn), ale crui coordonate (x1,...,xn) pot lua valorile 0 sau 1. n acest caz rezult c pot exista 2n vectori X distinci. Se noteaz mulimea acestor vectori cu . De asemenea, fiecrui vector din i se pot atribui valorile 0 sau 1.

Prin definiie, o funcie boole: f(X) = f (x1,x2,...,xn), X = (x1,...,xn) este o aplicaie f : ( {0,1}.

Se poate da i o alt definiie a funciei boole, mai concret, considernd c mulimea este format din dou submulimi disjuncte: K i Kc (Kc este complementara lui K n raport cu ), astfel ca: K, Kc ( ; K ( Kc = ; K ( Kc = (.

Atunci, o funcie boole de n argumente: f(x) = f(x1,...,xn), X = (x1,...,xn) se poate defini i prin:

x(K ( f(x) = 1,

x(Kc ( f(x) = 0.

Deci, unei FB i se asociaz un vector Vf = (f(x)) cu 2n componente egale cu 0 sau 1, fiecare component fiind asociat unui vector X dat.

(ntruct exist

vectori bivaleni cu 2n componente, rezult c numrul FB distincte de n argumente este finit i egal cu

.

S notm valorile fixe ale coordonatei unui vector din prin: (x1*,x2*,...,xn*). Aceste valori pot fi privite ca o combinaie de valori ale argumentelor unei FB. Deoarece numrul acestor combinaii este finit i egal cu

, atunci orice FB poate fi complet definit printr-un tabel finit cu 2n rnduri. n acest tabel, n partea stng se trec combinaiile valorilor argumentelor, iar n partea dreapt valorile corespunztoare, 0 sau 1, ale funciei:x1 x2.. . . . . . xn-1 xnf(x1 ,...,xn)

0 0 . . . . . . 0 0

0 0 . . . . . . .0 1

0 0 . . . . . . .1 0

. . . . . . . . . . . . . . . . . . 1 1. . . . . . . 1 1 (1

(2(3. . . . . . . .

Exist situaii cnd pentru unele combinaii ale valorilor argumentelor o FB s nu aib valoarea determinat. Astfel de FB nedeterminate pentru una sau mai multe combinaii ale valorilor argumentelor se numesc incomplet definite. n tabelele de definiie ale funciilor, valorile nedeterminate se noteaz cu asterisc. De cele mai multe ori, situaiilor de nedeterminare li se pot ataa arbitrar valori din mulimea {0,1}. Se spune c facem o definire complet a funciei. n general, dac o FB nu este definit pentru k combinaii ale valorilor argumentelor, atunci, prin definire arbitrar se pot obine 2k funcii distincte complet definite.

Astfel de funcii incomplet definite se ntlnesc frecvent n practica comenzilor secveniale, evidenierea situaiilor de nedefinire i atribuirea voit a valorilor 0 sau 1 fiind foarte important pentru simplificarea lor.

Exemplu: Fie o FB de 3 argumente:

a b c f(a,b,c)

0 0 0

0 0 1

0 1 0

0 1 1

1 0 0

1 0 1

1 1 0

1 1 1 0

1

*

0

0

*

1

* 0

1

0

1

0

1Se constat c prin definirea complet a acestei funcii (nedefinit pentru 3 combinaii ale valorilor argumentelor) se pot obine 23 = 8 funcii booleene distincte.

3.2.2Operaii cu FB

Aa cum se pot defini operaii logice n mulimea M = {0,1}, (i anume: (, (, c), aceleai operaii se pot aplica i funciilor logice. Operaiile se definesc numai pe domeniul valorilor funciilor.

Dou FB, f1(x1,...,xn) i f2(x1,...,xn) se numesc identice dac au valori identice pentru toate combinaiile posibile ale valorilor argumentelor i se scrie:

f1(x1,...,xn) = f2(x1,...,xn).

Dac cel puin pentru o singur combinaie a valorilor argumentelor cele dou funcii nu au aceleai valori atunci: f1(x1,...,xn) ( f2(x1,...,xn).

Fie f1, f2, f3, funcii booleene de n argumente. Operaiile (, (, c cu funcii se definesc astfel:

1) f1 ( f2 = f3 dac i numai dac: f1(x1,...,xn) ( f2(x1,...,xn) = f3(x1,...,xn),

adic, valorile funciilor se combin conform tabelului operaiei (, pentru fiecare

combinaie a valorilor argumentelor;

2) f1 ( f2 = f3 , dac i numai dac: f1(x1,...,xn) ( f2(x1,...,xn) = f3(x1,...,xn),

adic, valorile funciilor se combin conform tabelului operaiei (, pentru fiecare

combinaie a valorilor argumentelor;

3) ,

adic, se respect tabelul de definire a operaiei de complementare.

Exemplu: Fie urmtoarele funcii de dou argumente x1 i x2:

x1 x2 f1 f2 f3 f4 f5

0 0

0 1

1 0

1 1 0

1

1

0 1

0

1

0 1

1

1

0 0

0

1

0 0

1

0

1

Se observ c: f3 = f1 ( f2 , f4 = f1 ( f2 , iar .

3.2.3Funcii booleene elementare

Din punct de vedere abstract este interesant de a putea construi FB orict de complexe, care din punct de vedere practic s se reflecte prin comenzi discrete de complexitate mare. De aceea apare necesitatea definirii unui numr de FB simple cu care s se poat defini orice FB mai complex.

Din punct de vedere practic, definind funcii de baz putem elabora circuite elementare care s poat fi realizate modular, iar prin combinarea acestor module s putem materializa comenzi complexe. Astfel de funcii s-au numit FB elementare.

Plecnd de la necesitile practice, s-a constatat c este suficient a se folosi pentru definirea FB, funcii de dou argumente. Cele

funcii booleene de dou argumente sunt prezentate n tabelul urmtor: (Numrul lor este evident: NFB =

/n=2 =

= 24 = 16).

x1 x2f0f1f2f3f4f5f6f7f8f9f10f11f12f13f14f15

0 0

0 1

1 0

1 10

0

0

01

0

0

00

1

0

01

1

0

00

0

1

01

0

1

00

1

1

01

1

1

00

0

0

11

0

0

10

1

0

11

1

0

10

0

1

11

0

1

10

1

1

11

1

1

1

0((x1(x2((((x2(x1((1

1) FB degenerate:

funcii elementare constante

f0(x1,x2) = 0

f15(x1,x2) = 1

funcii elementare DA sau tampon

f12(x1,x2) = x1

f10(x1,x2) = x2Astfel de funcii se materializeaz cu circuite tampon folosite pentru adaptare de nivel logic sau de sarcin logic.

funcii negaie (inversoare logice)

2) FB nedegenerate:

Disjuncia logic sau funcia logic SAU:

f14(x1,x2) = f10(x1,x2) ( f12(x1,x2) = x1 ( x2 Conjuncia logic sau funcia logic I:

f8(x1,x2) = f10(x1,x2) ( f12(x1,x2) = x1 ( x2 Funcia lui Webb (Pierce):

f1(x1,x2) = x1 ( x2Examinnd valorile acestei funcii rezult c ea este negarea funciei disjuncie; de aici, denumirea de SAU-NU (NOR = NOT OR);

Deci se mai poate scrie:

Din relaia precedent se observ c simbolul ( are rolul de operator, definind situaia "nici x1 nici x2". Din acest motiv f1 se mai numete funcie NICI.

Funcia lui Sheffer:

f7(x1,x2) = x1 ( x2Examinnd valorile acestei funcii rezult c ea este negarea funciei conjuncie; de aici, denumirea de I-NU (NAND = NOT AND);

Conform acestei relaii de echivalen se mai poate spune c funcia lui Sheffer definete situaia: "numai x1 sau numai x2"; rezult denumirea de funcie NUMAI.

Ultimele funcii (NICI i NUMAI) au o deosebit importan att pentru teoria FB ct i pentru aplicarea practic a acestora n realizarea circuitelor logice modulare (cu ajutorul acestor dou funcii se pot realiza toate celelalte).

Funcia SUMA MODULO 2:

f6(x1,x2) = x1 ( x2

Se mai numete funcie SAU EXCLUSIV deoarece corespunde sumrii aritmetice a valorilor argumentelor n baza 2 (spre deosebire de operaia SAU care corespunde cu SAU INCLUSIV i este operaia logic SAU: 1 ( 1 = 0, dar 1 ( 1 = 1).

Se poate demonstra tabelar c:

x1 x2 (

0 0

0 1

1 0

1 1 0

1

1

0

x1 x2

0 0

0 1

1 0

1 11

1

0

01

0

1

00

1

0

00

0

1

00

1

1

0

Deoarece pentru fiecare din cele patru combinaii ale valorilor argumentelor cele dou pri ale expresiei au aceleai valori, identitatea este demonstrat.

Funcia echivalen:

f9(x1,x2) = x1 ( x2

Se poate verifica tabelar, sau utiliznd relaiile lui de Morgan c:

Funcia este simetric: f9(x1,x2) = f9(x2,x1).

Aceste funcii se folosesc la realizarea filtrelor secveniale.

Funciile implicaie:

f11(x1,x2) = x1 ( x2 (direct)

f13(x1,x2) = x2 ( x1 (invers)

Folosind reprezentarea tabelar se poate demonstra c:

(Se observ c prin combinarea prin funcii I a celor 2 funcii implicaie se obine funcia echivalen. Deci, dac x1 ( x2 i x2 ( x1 ( x1 ( x2).

Funciile inhibare (interdicie):

f2(x1,x2) = x1 ( x2 (x1 inhib x2) - inhibare direct

f4(x1,x2) = x2 ( x1 (x2 inhib x1) - inhibare invers.

Tabelar se demonstreaz c:

(se observ c: x1 ( x2 sau x2 ( x1 ( x1 ( x2).

Din definirea FB elementare de dou argumente rezult c se pot genera funcii noi fie prin permutarea argumentelor, fie prin introducerea funciilor n locul argumentelor noilor funcii. Folosirea repetat a celor dou reguli conduce la obinerea de FB complexe. Funcia boolean obinut din funciile f1,f2,...,fk prin utilizarea celor dou reguli, se numete superpoziia funciilor f1,f2,...,fk. Astfel de exemplu se observ c funcia ( se obine prin superpoziia funciilor: (, ( i c.

Din cele prezentate rezult c n afara operaiilor (, ( i c cu variabile i FB, se pot folosi ca operatori de calcul i simbolurile utilizate pentru celelalte funcii elementare.

Din punct de vedere practic intereseaz totui uneori i o serie de funcii de 3 argumente.

De exemplu, funciile:

MAX(x1,x2,x3) i MIN(x1,x2,x3) =

x1 x2 x3 MAXMIN

0 0 0

0 0 1

0 1 0

0 1 1

1 0 0

1 0 1

1 1 0

1 1 10

0

0

1

0

1

1

11

1

1

0

1

0

0

0

3.2.4Metode de reprezentare a Funciilor Booleene

Studiul Funciilor Booleene se face n multe cazuri pe reprezentrile acestora.

Exist o mare diversitate de reprezentri ale FB care pot fi grupate n reprezentri grafice (geometrice) i reprezentri analitice. Reprezentrile din prima categorie sunt intuitive i se folosesc pentru studiul FB cu un numr relativ redus de argumente. Din aceast categorie fac parte reprezentarea prin tabel de adevr, prin diagrame Euler, Venn, Veitch sau Karnough, prin grafuri sau pe hipercub. A doua categorie asigur o reprezentare prin expresii algebrice booleene sau sub form de coduri. Reprezentrile din aceast categorie permit studiul FB cu un numr orict de mare de argumente, cu posibilitatea utilizrii mijloacelor numerice de calcul.

n continuare se va insista asupra celor mai utile reprezentri ale FB pentru scopuri tehnice.

Reprezentarea prin tabele combinaionale

Tabelul de adevr este un tabel finit care conine toate valorile funciei pentru toate combinaiile valorilor argumentelor (se numete de adevr ntruct descrie complet funcia).

Pentru o funcie de n argumente, tabelul conine 2n linii (determinat de numrul combinaiilor posibile ale valorilor argumentelor) i n+1 coloane (dat de valorile argumentelor i de valorile funciei).

x1 x2 ........... xn f(x1,...,xn)

0 0 0

0 0 1

........................................

1 1 0

1 1 1 (1

(2 ...........................

(i({0,1}.

Un alt mod de reprezentare este diagrama Veitch - Karnough.

Aceasta este tot o reprezentare tabelar, dar n raport cu tabelul de adevr este mai compact datorit dispunerii dup dou direcii a valorilor argumentelor.

n cazul general al unei FB de n argumente, diagrama Karnough conine 2p linii i 2q coloane, astfel ca: n = p+q. Dac n este par se consider p = q, iar pentru n impar, se atribuie q = p+1 sau p = q + 1.

Rezult astfel o diagram cu 2p2q = 2p+q = 2n cmpuri n care se trec valorile funciei pentru combinaiile corespunztoare ale valorilor argumentelor indicate la capetele liniilor i coloanelor diagramei; n varianta iniial, combinaiile valorilor argumentelor pe linii i coloane se dispun conform codului binar natural. De exemplu, pentru 3 argumente:

S-a propus aceast reprezentare pornind de la faptul c prin astfel de reprezentri se pot obine simplificri foarte avantajoase pentru

FB. Pentru aceasta ar fi util ca variabilele ce reprezint diverse linii i

coloane alturate, s nu schimbe simultan dect o singur valoare.

Aceasta nseamn c dou combinaii (numere binare) s fie

adiacente. (n general, dou numere ntr-o baz b de numeraie sunt

adiacente dac difer cu o unitate modulo b).

Se observ c ntre cmpurile 2 i 3 nu exist adiacen - simultan se schimb dou variabile. Acest lucru duce la aa numitul hazard n funcionare, ntruct valoarea acestor argumente sunt practic semnale. n funcie de modul cum cele dou semnale sunt ntrziate n schema de comand, funcionarea poate fi complet diferit (dac b are o tranziie mai rapid atunci se trece din 01 n 11, deci se ajunge n cmpul 4, iar dac c i schimb valoarea mai repede, se va efectua tranziia 01 ( 00, deci se ajunge n cmpul 1).

Acest dezavantaj se nltur prin nlocuirea diagramei Veitch prin reprezentarea pe diagrama Karnough bazat pe codul Gray, numit i codul binar reflectat (deriv din cel natural). Acest cod asigur adiacena cmpurilor vecine, iar reprezentarea lui pe diagrama Karnough, n special pentru numrul mare de variabile se face geometric.

Codul Gray se obine din codul binar natural, regula de conversie fiind urmtoarea:

Se pleac de la bitul cel mai puin semnificativ al codului binar natural; dac acest bit este precedat de bitul 0, mai semnificativ, acest bit mai puin semnificativ se pstreaz ca atare; cnd bitul cel mai puin semnificativ este precedat de bitul 1 n codul binar natural,

acesta se complementeaz pentru a obine bitul respectiv n codul Gray. Se continu n acest mod pn la conversia complet a numrului.

Exemplu pentru ordinul 4:

Binar naturalGray (binar reflectat)Imaginea geometric a

codului Gray

B3 B2 B1 B0 G3 G2 G1 G0 G3 G2 G1 G0

0 0 0 0

0 0 0 1

0 0 1 0

0 0 1 1 0 0 0 0

0 0 0 1

0 0 1 1

0 0 1 0

0 1 0 0

0 1 0 1

0 1 1 0

0 1 1 1 0 1 1 0

0 1 1 1

0 1 0 1

0 1 0 0

1 0 0 0

1 0 0 1

1 0 1 0

1 0 1 1 1 1 0 0

1 1 0 1

1 1 1 1

1 1 1 0

1 1 0 0

1 1 0 1

1 1 1 0

1 1 1 1 1 0 1 0

1 0 1 1

1 0 0 1

1 0 0 0

Se observ c toate numerele alturate n mod Gray sunt adiacente ntre ele i n acelai timp este un cod ciclic (ultimul numr este adiacent cu primul).

Pentru fiecare rang n codul Gray, dac bitul are valoarea 1 i se ataeaz un segment de dreapt; dac este 0 el nu primete acest marcaj.

Exista foarte multe linii de simetrie (ngroate).

Reprezentarea grafic a diagramelor Karnough pentru 3, 4, 5 variabile este dat n figura urmtoare:

Exemplu: S se reprezinte prin diagrame Veitch i Karnough funcia f(a,b,c,d) dat prin tabelul de adevr:

a b c df(a,b,c,d)

0 0 0 0

0 0 0 1

0 0 1 0

0 0 1 1

0 1 0 0

0 1 0 1

0 1 1 0

0 1 1 1

1 0 0 0

1 0 0 1

1 0 1 0

1 0 1 1

1 1 0 0

1 1 0 1

1 1 1 0

1 1 1 11

1

1

0

1

0

0

1

0

0

0

0

1

1

0

1

Reprezentarea analitic a FB

Funciile booleene se pot forma prin reunirea variabilelor booleene prin intermediul operaiilor: I, SAU, NU, sau a altor operatori compleci (NICI, NUMAI). n acest mod se obin expresii analitice pentru FB.

Pentru a folosi o notaie comun n reprezentarea att a valorilor directe, ct i a celor complementate, se introduce urmtoarea definire a unei variabile bivalente, notat n general cu xa i care are valoarea x dac a = 1 i dac a = 0. Deci:

Astfel, se poate defini o expresie analitic sub form de conjuncie logic sub forma:

Acesta reprezint un termen conjunctiv de argumente: x1, x2, ..., xj, ai({0,1}, i = 1,2,...,j.

Fie o funcie boole de n argumente: f(x1,x2,...,xn).

Un termen conjunctiv definit mai sus, pentru care: j ( n, poart numele de termen canonic conjunctiv. Dac: j < n, acest termen se numete termen normal conjunctiv.

Se demonstreaz c orice FB de n argumente poate fi reprezentat (descris) printr-o disjuncie de termeni canonici conjunctivi aplicai de funcie n 1 (deci pentru care funcia ia valoarea 1).

f(x1,x2,...,xn) =

Aceast reprezentare poart numele de form canonic disjunctiv (FCD).

Din acest mod de reprezentare rezult c termenii canonici conjunctivi definesc valorile de 1 ale funciei. De aceea se mai numesc i constituieni

ai unitii. Dar, acetia reprezint i intersecii de argumente binare, deci se vor numi i termeni minimali sau minitermeni.

Pentru trecerea de la diagrama tabelar (tabel de adevr, diagram Veitch sau Karnough) la reprezentarea analitic, se folosete urmtorul algoritm:1. n tabel se consider acele combinaii ale argumentelor care sunt aplicate de funcie n 1.

2. Corespunztor n-uplelor de la pasul 1, se construiesc termenii canonici conjunctivi, n care argumentele intr ca atare sau negate dup cum n combinaia considerat au valoarea 1 sau 0.

3. Folosind termenii canonici de la pasul 2, asociindu-i prin operatorul disjuncie, se obine reprezentarea analitic sub form canonic disjunctiv a funciei.

Se consider ca exemplu funcia f(a,b,c) dat prin tabelul de adevr:

a b cf(a,b,c) a b c f(a,b,c)

0 0 0

0 0 1

0 1 0

0 1 10

1

1

0 1 0 0

1 0 1

1 1 0

1 1 11

1

0

0

sau prin diagram Karnaugh:

Conform algoritmului stabilit, cei trei pai conduc succesiv la:

1. (001), (010), (100), (101)

2.

3. f(a,b,c) =

Se poate defini i o expresie analitic sub form de disjuncie logic, sub forma:

, ai({0,1}, i = 1,2,...,j.

Similar cu reprezentrile anterioare, acetia definesc termeni disjunctivi normali, dac j < n i termeni canonici disjunctivi, dac j ( n.

Pentru o FB de n argumente se arat c ea se poate reprezenta ca o conjuncie de termeni canonici disjunctivi cu variabile negate, pentru valorile de zero ale funciei, i anume:

f(x1,x2,...,xn) = .

Aceast reprezentare poart numele de form canonic conjunctiv (FCC) i este dual FCD - conform principiului dualitii pentru latici.

Termenii canonici disjunctivi sunt termeni maximali (maxitermeni).

Se definete un algoritm similar de trecere de la reprezentarea prin diagrama tabelar la reprezentarea analitic:

1. Se consider n-uplele pe care funcia le aplic n zero;

2. Termenii canonici disjunctivi corespunztori acestor n-uple se obin lund argumen- tele ca atare sau negate, dup cum n combinaia respectiv ele au valoarea 0 sau 1;

3. Conectnd termenii canonici disjunctivi prin operatorul conjuncie, se obine reprezen- tarea analitic sub form canonic conjunctiv a funciei.

Pentru acelai exemplu:

1. (000), (011), (110), (111)

2.

3. f(a,b,c) =

Forma canonic conjunctiv se poate obine i plecnd de la FCD negat. n acest caz se poate scrie:

unde s-au considerat n-uplele pe care funcia le aplic n 0.

Negnd i aplicnd relaiile lui de Morgan rezult:

adic tocmai relaia de definire a FCC.

Reprezentarea FB prin simbol de marcare

Simbolul de marcare este o reprezentare numeric a FB i deriv din reprezentarea prin tabel de adevr. n tabelul de adevr, fiecrei combinaii a valorilor argumentelor i corespunde o valoare (0 sau 1) pentru funcie. Se poate spune c fiecare combinaie definete starea funciei.

n cadrul reprezentrii FB prin simbol de marcare se definete numrul de stare, care coincide ca valoare cu numrul combinaiei:

Pentru o ordine dat a argumentelor, irul valorilor binare ale unei funcii n ordine cresctoare a numrului de stare definete complet funcia respectiv.

Cifra binar rezultat din niruirea biilor 0 i 1 ai funciei se numete numr de ordine i se noteaz cu N. Astfel, indicarea ordinii argumentelor i a numrului de ordine constituie marca unei FB. Simbolul de marcare (M) este tocmai reprezentarea simbolic a acestui mod de definire a unei FB i care, pentru o FB de n argumente este de foma:

f(x1,x2,...,xn) =

Dac numrul de ordine se scrie n codul octal se obine o reprezentare mai compact a unei FB.

Aceasta este o reprezentare neoperativ a FB.

S scriem simbolul de marcare pentru funcia dat prin urmtorul tabel de adevr:

a b c f(a,b,c)

0 0 0

0 0 1

0 1 0

0 1 1

1 0 0

1 0 1

1 1 0

1 1 10

1

0

0

1

1

1

0

f(a,b,c) =

Trecerea binar - octal: (01.001.110)2 ( (116)8Deci, n octal: f(a,b,c) =

nlocuind numrul de ordine cu irul cresctor al numrului de stare, n cod octal, se obine forma operativ a simbolului de marcare.

Dac n forma operativ se consider numai numrul de stare pe care funcia le aplic n 1, simbolul de marcare conine aceleai informaii ca i FCD. Aceast reprezentare se numete reprezentare prin simbol D de marcare:

(1)f(x1,x2,...,xn) =

unde: (n1,n2,...,nk) sunt numere de stare n octal pentru care funcia are valoarea 1.

n exemplul dat: f(a,b,c) =

(se indic i valoarea luat de funcie).

ntr-un mod analog, dac se consider numai numrul de stare pentru care funcia ia valoarea 0, prin convenie, FCC poate fi exprimat prin simbolul de marcare C:

(2) f(x1,x2,...,xn) =

unde: (ni,nj,...,nn) sunt numere de stare n octal pentru care funcia are valoarea 0, complementate.

Pentru exemplul dat: f(a,b,c) =

Deoarece, pentru o FB complet definit, mulimile numerelor de stare (n1,n2,...,nk) i (ni,nj,...,nn) sunt disjuncte, iar formele (1) i (2) sunt forme diferite ale aceleiai funcii, se poate scrie:

(3)

(n cazul FB incomplet definite este necesar ca att n (1) ct i n (2) s se indice numrul de stare pe care funcia le aplic n 0 i 1, precum i strile indiferente care voit se aplic n 0 sau 1 (acestea se indic cu asterisc). n aceast situaie, relaia (3) nu mai este adevrat.

Reprezentarea FB prin scheme logice

Schema logic (logigrama) este o reprezentare grafic a FB obinut prin adoptarea unor semne convenionale pentru operaiile logice. Logigrama indic de fapt topologia unui circuit care realizeaz o FB. Astfel, simbolurile grafice adoptate pentru operaiile logice constituie n acest timp i simbolurile circuitelor logice care materializeaz operaiile respective.

n continuare sunt prezentate cele mai utilizate simboluri grafice pentru principalele funcii elementare de 2 argumente:

NU:

Cu aceste simboluri orice FB poate fi reprezentat prin schema logic.

Observaii:

1. Se caut pe ct posibil ca operatorii de acelai fel s fie reprezentai pe aceeai coloan, definind astfel un nivel logic;

2. Relativ la circuitele logice elementare care sunt capabile s comande simultan mai multe module, variabilele odat calculate se folosesc n orice loc folosind acelai rezultat.

Reprezentarea prin diagrame n timp

Diagrama n timp reprezint grafic o FB prin forma semnalelor corespunztoare argumentelor i funciei. Cifrele binare 0 i 1 se ataeaz semnalelor de nivel cobort i respectiv de nivel ridicat, astfel ca s existe o diferent net a acestora. Reprezentarea prin diagrame n timp este deosebit de util n studiul sistemelor secveniale, n a cror evoluie intervine i timpul. De asemenea, folosind aceste reprezentri se pot studia fenomenele tranzitorii de comutare i fenomenele de hazard datorate funcionrii neideale a elementelor care materializeaz variabile sau funcii booleene.

3.3Aplicaii

1. S se stabileasc numrul FB nedegenerate de 3 argumente.

Indicaie: Numrul FB nedegenerate de "n" argumente se poate determina utiliz(nd urmtoarea relaie de recuren:

unde, Ni este numrul FB nedegenerate de i < n argumente. Pentru utilizarea acestei relaii de recuren este necesar adoptarea unei ipoteze logice iniiale, i anume: numrul

FB nedegenerate de zero argumente este 2, funcia, ca orice FB, put(nd lua doar 2 valori

logice, chiar (n lipsa argumentelor; deci: N0 = 2.

2. S se reprezinte prin tabel de adevr, diagram Karnough, analitic, simbol de marcare i schem logic funciile:

a) Funcia de 4 variabile care ia valoarea "1" dac cel puin 3 variabile au aceeai valoare logic;

b) Funcia de 4 variabile care ia valoarea "1" dac prima i ultima variabil (MSB i LSB (n vectorul de intrare) au aceeai valoare logic;

c) Funcia de 4 variabile care ia valoarea logic a majoritii variabilelor (combinaiile imposibile nu pot apare).

3. S se realizeze schema logic care s furnizeze cele 10 FB nedegenerate de 2 argumente utiliz(nd un numr minim de pori logice.

4. Un ascensor pentru ridicarea materialelor transport sarcini (ntre 100 i 800 Kg. Sesizarea masei (ncrcturii ascensorului se face prin (nchiderea a 3 contacte (a, b, c) fixate sub podeaua cabinei. Prin resoarte, se asigur ca ordinea de (nchidere a contactelor, la creterea masei (ncrcturii, s fie: a, b, c. Se cere s se determine funcia logic care comand urcarea ascensorului tiind c acesta poate urca dac este gol (a, b, c - deschise), sau cu sarcini (ntre 100 i 800 Kg (a, b - (nchise, c - deschis). Dac sarcina este sub 100 Kg (a - (nchis, b, c - deschise), sau peste 800 Kg (a, b, c - (nchise) ascensorul nu trebuie s urce.

5. Demonstrai identitatea:

6. Demonstrai c expresiile:

i

nu sunt identice. Ce relaii exist (ntre aceste dou relaii ?

7. Demonstrai c expresiile:

i

sunt identice.

8. Scriei complementul expresiei:

9. S se demonstreze c:

10. S se verifice identitile logice:

11. S se verifice asociativitatea funciilor SAU-EXCLUSIV i ECHIVALEN:

12. S se demonstreze c:

13. Fie: Calculai

14. S se verifice relaiile logice:

, cu (i({0,1}, i = 1,2n

bc

a

00 01 10 11

0

x1

x3

x2

x4

x4

x5

x3

x3

x2x1

x2x1

n = 5

n = 4

n = 3

(

1

0

1

1

1

0

0

0

0

0

1

0

1

cd

ab

1

1

0

1

0

1

1

0

0

1

0

0

1

0

0

1

1

1

0

Veitch :

Karnough :

00 01 10 11

00

01

10

11

d

c

b a

1

1

0

0

1

1

0

0

a

c

b

x

x

x

x

x

x

;

;

;

x

x

;

NU

x

x

;

cele mai utilizate

indic c exist un amplificator cu inversare

SAU: :

x2

x1

x1 ( x2

;

x2

x1

x1 ( x2

;

;

x2

x1

x1 ( x2

(

;

x2

x1

x1 ( x2

+

x2

x1

x1 ( x2

SAU

(OR)

x2

x1

x1 ( x2

;

x2

x1

x1 ( x2

;

;

x2

x1

x1 ( x2

((

;

x2

x1

x1 ( x2

(

x2

x1

x1 & x2

&

I

(AND)

I:

NICI:

x2

x1

x1 ( x2

x1 ( x2

;

;

x2

x1

sau, avnd n vedere relaiile lui de Morgan:

x2

x1

x1 ( x2

, sau n clar :

x2

x1

x1 ( x2

(

(NICI)

(NOR)

NUMAI:

x1 (x2

x1 (x2

x1 ( x2

;

sau, conform relaiei lui de Morgan :

, sau n clar :

x2

x1

x2

x1

x2

x1

x1 ( x2

(

(NUMAI)

(NAND)

x2

x1

x1 x2 ( x1 x2

x2

x1

(SAU EXCLUSIV)

Notare direct

x1 ( x2

x2

x1

(

SUMA MODULO 2:

0

1

1

1

1

1

1

t

t

t

0

0

0

0

0

0

0

f = x1 ( x2

f

x2

x1

1

_990778556.unknown

_990781800.unknown

_990782540.unknown

_990783445.unknown

_990784423.unknown

_990784485.unknown

_990784595.unknown

_990784072.unknown

_990783039.unknown

_990783235.unknown

_990782703.unknown

_990782236.unknown

_990782436.unknown

_990781985.unknown

_990779856.unknown

_990780334.unknown

_990781725.unknown

_990780262.unknown

_990779217.unknown

_990779354.unknown

_990778909.unknown

_990777618.unknown

_990778280.unknown

_990778328.unknown

_990778354.unknown

_990778300.unknown

_990778087.unknown

_990778225.unknown

_990777898.unknown

_978491944.unknown

_990775340.unknown

_990776325.unknown

_990776781.unknown

_990775818.unknown

_990775118.unknown

_990775146.unknown

_978492617.unknown

_978493025.unknown

_990774963.unknown

_978494333.unknown

_978492767.unknown

_978492106.unknown

_936877027.unknown

_957160234.unknown

_957160236.unknown

_978491023.unknown

_957160235.unknown

_936877104.unknown

_957160232.unknown

_957160233.unknown

_957160229.unknown

_957160230.unknown

_936879852.unknown

_936877067.unknown

_897990510.unknown

_936876812.unknown

_936876857.unknown

_936876773.unknown

_897990507.unknown

_897990509.unknown

_897990502.unknown

_897990505.unknown

_897990270.unknown

_897990501.unknown