Algebra Booleana

download Algebra Booleana

of 18

  • date post

    31-Oct-2014
  • Category

    Documents

  • view

    16
  • download

    0

Embed Size (px)

description

BTI

Transcript of Algebra Booleana

1. ELEMENTE DE ALGEBR BOOLEANn teoria circuitelor numerice i n electronica digital n general, semnalele electrice pot lua numai valori discrete, n majoritatea cazurilor aceste valori fiind asociate convenional lui 0 logic i 1 logic. n limbaj tehnic ne vom referi la aceste dou valori cu noiunea de bit (binary digit). Bitul se definete n teoria informaiei i este o unitate de msur a acesteia, echivalent cu informaia transmis prin furnizarea unui mesaj din dou egal probabile. Calculatoarele electronice digitale (numerice) efectueaz operaii logice. De aceea, pentru a studia principiile de operare ale subsistemelor de procesare logic, este necesar s se analizeze unele noiuni de logic matematic. Se disting mai multe direcii de preocupare n logica matematic, printre care logica claselor i logica propoziiilor. n logica claselor se studiaz relaiile dintre clasele (mulimile) de obiecte, prin clas nelegndu-se totalitatea obiectelor care au o anumit proprietate. n logica propoziiilor se studiaz propoziiile din punct de vedere al adevrului sau falsitii lor (este vorba de propoziii matematice). n afar de logica bivalent, n care propoziiile pot fi numai adevrate sau numai false, s-au dezvoltat i alte logici matematice n care se admit i alte valori pentru propoziii. Aceste logici au cptat atributul de polivalente. Majoritatea sistemelor digitale lucreaz n logic bivalent, utiliznd codificarea binar a informaiei. Exist i sisteme care lucreaz pe baza unor logici polivalente. Fie A o propoziie. Dac ea este adevrat vom scrie: A = 1. Dac este fals, vom scrie: A = 0. Astfel, 1 i/sau 0 reprezint valori de adevr (sau valori logice binare) pentru propoziia A. Expresiile n care intervin mai multe propoziii vor fi numite funcii logice. Algebra logic binar a fost fundamentat prin lucrrile matematicianului englez George Boole i din aceast cauz ea mai poart i denumirea de algebr Boole sau algebr boolean. Pentru studiul circuitelor numerice (digitale) se folosete ca suport matematic algebra boolean. Ea are la baz o serie de postulate (axiome) i teoreme.

1

cap.1 Elemente de algebr boolean

1.1 Axiome i teoreme booleeneAlgebra boolean opereaz pe o mulime B = { x / x{0, 1}}. n aceast mulime binar se definesc trei legi de compoziie: complementarea (negare, NU, NOT, inversare logic), disjuncia (sum logic, +, SAU, OR, ) i conjuncia (produs logic, , I, AND, ), pentru care se dau n continuare tabelele de adevr, simbolurile grafice i implementarea prin contacte (figura 1.1) (xy ) x+y 0 1 1 1 (xy ) xy0 0 0 1

x 0 1

x 1 0

x 0 0 1 1

y 0 1 0 1

x 0 0 1 1

y 0 1 0 1

x x

x x

x y

x+y

x y

xy

x x

x

y

x

y

Figura 1.1 Tabelele de adevr, simbolurile grafice i implementarea prin contacte electrice pentru complementare, disjuncie i conjuncie

Toate relaiile definite pe B au un caracter dual, adic relaiile rmn valabile dac se fac schimbrile: + cu i respectiv 0 cu 1 (teorema dualitii). n mulimea B se poate alege o structur de ase axiome duale pe baza crora se definesc teoremele i proprietile care stau la baza algebrei boolene. Acestea sunt prezentate n continuare. Axiome: 1. Mulimea B este o mulime nchis: X,Y B X+YB; X,Y B XYB ; 2. Asociativitatea: X+(Y+Z) = (X+Y)+Z ; X(YZ) = (XY) Z ; 3. Comutativitatea: X+Y = Y+X ; XY = YX ; 2

(1.1) (1.2) (1.3)

BAZELE PROIECTRII CIRCUITELOR NUMERICE 4. Distributivitatea: X+YZ = (X+Y)(X+Z) ; X (Y+Z) = XY+XZ ; 5. Element neutru: X + 0 = 0 + X = X ; X1 = 1 X = X ; 6. Complementul:

(1.4) (1.5) (1.6)

X + X = 1; X X = 0 ;

Teoreme (proprieti): 7. Idempotena: X+X+..+X = X ; XX..X = X ; 8. Elemente neutre: X+1 = 1 ; X0 = 0 ; 9. Involuia: X = X, X = X; 10. Absorbia: X+XY = X ; X(X+Y) = X ; 11. Relaiile lui De Morgan:

(1.7) (1.8) (1.9) (1.10) (1.11)

X + Y = XY ,

XY = X + Y

n general, notnd cu suma i respectiv cu produsul boolean, relaiile De Morgan se scriu:

n

xk =

k =1

k =1

n

xk

i

k =1

n

xk =

xkk =1

n

(1.12)

Pe mulimea B sunt valabile teoremele enunate. Demonstraia lor se poate face folosind axiomele, dar este mai comod dac se folosesc tabelele de adevr. Tabela de adevr stabilete o coresponden ntre valorile de adevr ale variabilelor i valoarea de adevr a funciei. Exemplu: x 0 0 1 1 y 0 1 0 1x+y 0 1 1 1

x+y

x 1 1 0 0

y 1 0 1 0

xy 1 0 0 0

1 0 0 0

Figura 1.2 Relaiile lui De Morgan

3

cap.1 Elemente de algebr boolean

Perechile de operatori NOT i AND, respectiv NOT i OR formeaz fiecare cte un sistem complet, adic orice relaie definit pe B poate fi exprimat folosind numai operatorii unei singure perechi. Circuitul fizic care implementeaz un operator logic se numete poart logic. Sistemele complete prezentate au fost realizate cu cte o singur poart: I-NU (NAND, Scheffer) i SAU-NU (NOR, funcie nici sau funcie Pierce). Un sistem complet de operatori poate exprima orice relaie logic ca n exemplul urmtor, n care ne propunem s implementm operatorii NOT, OR i AND folosind operatori NAND i NOR. NOT NAND x = xx OR x + y = xy AND xy = xy

NOR

x = x+x

x+y = x+y

xy = x + y

Figura 1.3 Implementarea operatorilor NOT, OR i AND folosind operatori NAND i NOR.

Relaii booleene utile: 1) x + 1 = ( x + 1) * 1 = ( x + 1)( x + x ) = x * x + x * x + 1 * x + 1 * x = = x+0+x+x = x+x =1 2) proprietatea de absorbie: x + ( x * y ) = x * (1 + y ) = x i relaia dual: x * ( x + y ) = x * x + x * y = x + xy = x

(1.13)

(1.14)

3) x + x * y = x + y (1.15) Demonstraie: x + y = ( x + y )( x + x )( y + y ) = ( xx + x x + yx + y x )( y + y ) = ( x + xy + xy )( y + y ) == xy + x y + xy + xy y + xy + xy y = xy + x y + xy = x( y + y ) + xy = x + xy 4) x( x + y ) = x * y (duala relaiei precedente). (1.16) (1.17)

1.2 Funcii logiceO funcie f : Bn B se numete funcie boolean. Altfel spus, o funcie boolean de n variabile y = f (x1,x2,..xn), unde xi sunt variabile de intrare, se caracterizeaz prin faptul c att funcia ct i variabilele nu pot lua dect dou valorile distincte, 0 i 1.

4

BAZELE PROIECTRII CIRCUITELOR NUMERICE

Exemplu: Considerm un rezervor alimentat de trei robinete x, y i z. Ne propunem s meninem rezervorul plin cu ajutorul acestor trei robinete. Rezervorul poate fi meninut plin dac cel puin dou robinete sunt deschise simultan. Dac considerm c un robinet deschis are atribuit valoarea logic 1, atunci funcia care descrie din punct de vedere logic aceast situaie este urmtoarea:

U( x, y, z) = xy z + x yz + xyz + xyz

(1.18)

1.3 Reprezentarea funciilor logicePentru reprezentarea funciilor logice se folosesc n mod curent i n principal trei metode, descrise mai jos.A. Reprezentare prin tabela de adevr

Aceast reprezentare presupune marcarea, ntr-un tabel, a corespondenei dintre valorile de adevr ale variabilelor de intrare i valoarea de adevr a funciei n fiecare punct al domeniului de definiie.Exemplu: Pentru cazul problemei considerate n exemplul anterior, reprezentarea prin tabel arat ca n figura 1.4

x 0 0 0 0 1 1 1 1

y 0 0 1 1 0 0 1 1

z 0 1 0 1 0 1 0 1

U 0 0 0 1 0 1 1 1

Figura 1.4 Exemplu de reprezentare prin tabel a unei funcii logice B. Reprezentarea prin diagrame Karnaugh

Reprezentarea prin diagrame Karnaugh const n a marca punctele domeniului de definiie ntr-o diagram plan i a preciza valoarea funciei n fiecare din aceste puncte.

x \ yz 0 1

00 0 0

01 0 1

11 1 1

10 0 1

Figura 1.5 Reprezentarea funciilor logice prin diagrame Karnaugh

5

cap.1 Elemente de algebr boolean Dac lum n considerare vrful cubului caracterizat prin coordonatele 000, constatm c acest vrf este vecin cu vrfurile 001, 010, 100. n diagrama Karnaugh constatm c 000 este vecin doar cu 001 i 100. Pentru ca diagrama Karnaugh s fie echivalent cu reprezentarea prin cub, ea trebuie s pstreze acelai vecinti, lucru ce devine posibil doar dac ne imaginm latura din stnga a diagramei Karnaugh n continuarea celei din dreapta, iar latura de sus n continuarea celei de jos. n acest fel, punctul 000 devine vecin i cu punctul 010.C. Reprezentarea prin echivaleni zecimali ai mintermilor

Reprezentarea prin echivaleni zecimali ai mintermilor const n indicarea echivalenilor zecimali ai conjunciilor pentru care valoarea funciei este 1 sau a echivalenilor zecimali corespunztori valorii 0 ale funciei.Exemplu:

U( x,y,z ) = R1 ( 3,5,6,7 ) U( x,y,z ) = R0 ( 0,1,2,4 )

(1.19) (1.20)

1.4 Expresii analitice ale funciilor logicen majoritatea aplicaiilor practice este necesar utilizarea formei analitice a funciilor booleene. n acest scop se utilizeaz dou forme de dezvoltare: - forma canonic disjunctiv (FCD) care presupune utilizarea unor funcii elementare numite constitueni ai unitii (termeni minimali sau mintermi); - forma canonic conjunctiv (FCC) care presupune utilizarea unor funcii elementare numite constitueni ai lui zero (termeni maximali sau maxtermi).Notaie:

x, pentru = 1 x = x, pentru = 0

(1.21)

Definiie: Se numete constituent al unitii funcia elementar Q(n) caracterizat prin faptul c k

ia valoarea 1 logic ntr-un un singur punct al domeniului de definiie. Constituentul unitii va fi produsul logic al tuturor variabilelor negate sau nenegate: Q(n) k=

xii=0

n 1

i

,

k(10) = n-1,.. 0 (2)

(1.22)

Pentru ca Q(n) s fie 1 ntr-un anumit punct al domeniului de definiie este k

necesar ca toi termenii produsului s fie 1 logic, ceea ce presupune ca argumentele s aib valoarea xi = i. Aadar rezult urmtoarea regul de scriere a mintermenilor Q(n) : n k con