3. Existenta elementelor neutre pentru operatiile binare (i) element neutru fata de operatia (+) notat cu 0 a.î.: a B , a+0=a (i) element neutru fata de operatia (.) notat cu 1 a.î. a B , a.1=a

4. Comutativitate a,b B (i) a+b=b+a (ii) a.b=b.a

5. Distributivitatea a,b B (i) a+(b.c) =(a+b).(a+c) (ii) a.(b+c)=a.b+a.cAxiomele algebrei booleene

6. Existenta elementului opus a B, exista elementul opus lui a, notat a' a.î.:

(i) a+a'=1

(ii) a.a'=0

Denumirea operatiilor

Operatia " + " se numeste suma logica, adunare logica, surjectie si o vom numi pe scurt suma

Operatia " . " se numeste produs logic, înmultire logica, conjunctie si o vom numi pe scurt produs

Operatia " ' " se numeste negare sau complementare

Prioritatea operatiilor

În cadrul unei algebre booleene operatiile au urmatoarea prioritate

( ) - expresiile din paranteza

' - operatia de complementare

. - operatia de înmultire logica

+ - operatia de sumare logica

Principiul dualitatii

. Axiomele algebrei booleene sunt prezentate în perechi fiecare axioma din pereche fiind duala celeilalte

. O axioma se poate obtine din duala sa modificând operatia "+" cu operatia "." si elementul 0 cu elementul 1 (si invers).

. Exemplu: existenta elementului opus

(i) a + a' = 1

↕ ↕

(ii) a . a' = 0

Proprietatile algebrei booleene

Idempotenta a B (i) a + a = a (ii) a.a = a

Proprietatile lui 0 si 1 a B (i) a+1=1

(ii) a.0 = 0

Proprietatile algebrei booleene

Unicitatea lui 0 si 1 Elementele 0 si 1 sunt unice

Unicitatea elementului opus Pentru a B , a' este unic

Distinctia dintre 0 si 1 Elementele 0 si 1 sunt distincte

Involutia a B, (a')'=a

Absorbtia a,b B (i) a + a.b = a (ii) a.(a+b) = a

Asociativitatea a,b,c B (i) a + (b + c) = (a + b) + c (ii) a . (b . c) = (a . b) . c

De Morgan a,b B (i) (a + b)' = a' . b' (ii) (a . b)' = a' + b'

Exemple de algebre booleene

Algebra binara B= împreuna cu operatiile

Definire alternativa a operatiilor

Simboluri - Contact normal deschis (cnd)

Contact normal închis (cni)

􀁺 K= multimea contactelor electrice împreuna cu operatiile:

-Legare în serie

- Legare în paralel

-Schimbarea starii contactului

Comutativitate

Element neutru

Distributivitate

Element opus

Idempotenta

Proprietatile lui 0 si 1

Absorbtia

De Morgan

Functii booleene (FB)

Definitii

􀁺 O variabila care poate lua doar valorile 0 si 1 va fi denumita variabila binara booleana, variabila bivalenta booleana sau simplu variabila binara.

O functie booleana este o functie f:n→m pentru m,n≥0. Fiecarei n-tuple x=(x1,.,xn) n, functia îi pune în corespondenta o m-tupla unica f(x)=y=(y1,.,ym) m.

Datorita asocierii cu circuitele numerice, componentele x1,.,xn se mai numesc variabile de intrare sau intrari iar componentele vectorului y, y1,.,ym se mai numesc variabile de iesire sau iesiri.

n>1, m=1 functii booleene cu o singura iesire si n intrari.

n>1,m>1 functii booleene cu n intrari si m iesiri.

Functii booleene

Pentru o functie care depinde de n de variabile avem:

2n combinatii de valori pentru variabile

22n=functii de n variabile

Functiile booleene de doua variabile

n=2 nr. de variabile

22=4 combinatii de valori pentru variabile

222=16 functii de 2 variabile

Functiile booleene de doua variabile

F0 = 0 Functia constanta 0

F1 = A.B (SI) AND

F2 = AB' Inhibitie (A dar nu B)

F3 = A Identitate

F4 = A B Inhibitie (B dar nu A)

F5 = B Identitate

F6 = AB' + A'B SAU-Exclusiv (XOR), se noteaza si A B

F7=A+B

F8 = (A + B)' SAU-NU (NOR) (în logica matematica denumita functia lui Peirce, se mai noteaza A ↓B

F9 = A'B' + AB Echivalenta, se noteaza si A≡B

F10=B' Complement, NU (NOT)

F11 = A + B' Implicatie (B implica A), se noteaza si B → A

F12 = A' Complement, NU (NOT)

F13= A' + B Implicatie (A implica B), se noteaza si A → B

F14 = (AB)' SI-NU (NAND) - în logica matematica denumita functia Sheffer, se mai noteaza A ↑B

F15 = 1 Functia constanta 1

Sisteme complete de FB

Un set de FB este complet daca orice FB poate fi exprimata folosind functiile din acel set.

Ex. este un set complet de FB (vezi reprezentarile canonice ale FB).

Ex. este un set complet de FB.

Aratam ca setul poate fi reprezentat de FB din setul Ex.

a+b=a+b a.b=((a.b)')'=(a'+b')' - s-a folosit DeMorgan

a'=a'

Ex. este un set complet de FB.

Aratam ca setul poate fi reprezentat de FB din setul Ex.

a.b=a.b

a+b=((a+b)')'=(a'.b')' - s-a folosit DeMorgan

a'=a'

Ex. este un set complet de FB. S-a notat cu ↓ functia SAU-NU

Aratam ca setul poate fi reprezentat de FB din setul Ex.

a'=(a+a)'=a↓a

a+b=((a+b)')'=(a↓b)'=(a↓b) ↓(a↓b)

a.b=(a'+b')=a' ↓b'=(a↓a) ↓(b↓b)

Ex. este un set complet de FB. S-a notat cu ↑ functia SI-NU

Aratam ca setul poate fi reprezentat de FB din setul Ex.

a'=(a.a)'=a ↑ a

a.b=((a.b)')'=(a ↑ b)'=(a ↑ b) ↑(a ↑ b)

a+b=(a'.b')=a' ↑ b'=(a ↑ a) ↑(b ↑ b)

Reprezentarea functiilor booleene

Reprezentarile FB pot fi:

Grafice

Analitice

Reprezentari grafice

Tabele de adevar

Scheme de operatori (porti logice)

Arbori de decizie binara

Diagrame Veitch-Karnaugh

Scheme cu contacte

Hipercub

Diagrame de semnale

Reprezentari analitice

Simbolice

forme normale necanonice disjunctive si conjunctive

forme normale canonice disjunctive si conjunctive

simbol de marcare

Coduri

vectori booleeni

numere conventionale

notatia cubica pozitionala

Tabele de adevar

Unei functii de n variabile i se asociaza o tabela cu:

2n linii - corespund celor 2n combinatii posibile ale variabilelor

n+1 coloane - n coloane corespunzatoare celor n variabile si o coloana pentru valorile functiei

Functie de 2 variabile

Functie de 3 variabile

Definitii

Un literal este aparitia unei variabile în forma normala sau negata. - Ex. x, x', a, a', x1, x1' etc.

Un termen produs sau termen normal conjunctiv este produsul logic al mai multor literale. Fiecare literal apare o singura data - Ex. x.z', a.b'.c, x1'.x2.x3

Un minterm sau constituent al unitatii este un termen produs care include toate variabilele de care depinde functia. - Ex. Pentru f(x,y,z) x.y.z, x'.y.z sunt mintermi, x.y nu este minterm pentru ca lipseste variabila z - Ex. Pentru f(a,b,c,d) a.b.c.d', a'.b.c.d' sunt mintermi a.d nu este minterm pentru ca lipsesc variabilele b si c

Un maxterm sau constituent al lui 0 este un termen suma care include toate variabilele de care depinde functia. - Ex. Pentru f(x,y,z) x+y+z, x'+y+z sunt maxtermi, x+y nu este maxterm pentru ca lipseste variabila z - Ex. Pentru f(a,b,c,d) a+b+c+d', a'+b+c+d' sunt mintermi a+d nu este maxterm pentru ca lipsesc variabilele b si c

Un termen suma sau termen normal disjunctiv este suma logica a mai multor literale. Fiecare literal apare o singura data - Ex. x+z', a+b'+c, x1'+x2+x3

O expresie suma de produse sau forma normala disjunctiva este formata din suma logica a mai multor termeni produs.

Ex. a.b'.c'+a'.b.c+a'.b.c'

Observatie Pentru simplificare, când nu exista dubii, operatorul "." se poate omite

Ex. ab'c'+a'bc+a'bc'

O expresie produs de sume sau forma normala conjunctiva este formata din produsul logic a mai multor termeni suma.

Ex. (a+b'+c').(a'+b+c).(a'+b+c')

Observatie Pentru simplificare, când nu exista dubii, operatorul "." se poate omite

Ex. (a+b'+c')(a'+b+c)(a'+b+c')

Adiacenta

Doi termeni sunt adiacenti daca ei au acelasi numar de variabile si difera prin forma unei singure variabile.

Ex.

a.b.c' si a.b.c sunt adiacenti pentru ca difera prin forma variabilei c care în primul termen apare negat iar in cel de al doilea apare normal

a'.b.c'.d si a'.b'.c'.d' nu sunt adiacenti pentru ca difera prin forma a doua variabile b si d.

a'+b+c si a+b+c sunt adiacenti pentru ca difera prin forma variabilei a care în primul termen apare negat iar in cel de al doilea apare normal

a+b+c'+d' si a'+b'+c'+d' nu sunt adiacenti pentru ca difera prin forma a doua variabile a si b.

Tabela de adevar si mintermi

Regula:

Fiecarei combinatii de valori îi corespunde un minterm în care

xi apare normal daca pentru combinatia respectiva xi=1

xi apare negat daca pentru combinatia respectiva xi=0

Functie de 2 variabole Functie de 3 variabile

Tabela de adevar si maxtermi

Regula:

Fiecarei combinatii de valori îi corespunde un maxterm în care

xi apare negat daca pentru combinatia respectiva xi=1

xi apare normal daca pentru combinatia respectiva xi=0

Tabele de adevar si mintermi

Functie de 2 variabile

Tabele de adevar

Functie de 3 variabile

Forma canonica normal disjunctiva

O functie f(x1,x2,...,xn) poate fi scrisa sub forma canonica normal disjunctiva: 2n-1 f(x1,x2,...,xn)= K.mK K=0

unde K=f(kn-1,kn-2,...,k1,k0) este valoarea functiei din tabelul de adevar corespunzator mintermului mk

FCND este formata din suma logica a mintermilor pentru care functia ia valoarea 1. Observatie: FCND are atâtia mintermi câte valori de 1 are functia

Forma canonica normal conjunctiva

O functie f(x1,x2,...,xn) poate fi scrisa sub forma canonica normal conjunctiva: 2n-1

f(x1,x2,...,xn)= K+MK) K=0

unde K=f(kn-1,kn-2,...,k1,k0) este valoarea functiei din tabelul de adevar corespunzator maxtermului Mk

FCNC este formata din produsul logic al maxtermilor pentru care functia ia valoarea 0.

Observatie: FCNC are atâtia maxtermi câte valori de 0 are functia

Reprezentarea FB folosind simboluri

Exista doua variante

ANSI/IEEE 91-1973

ANSI/IEEE 91-1984 si IEC

Reprezentarea FB folosind simboluri

Diagrama Veitch Karnaugh (V-K)

metoda grafica de a reprezenta într-o forma condensata tabelul de adevar al unei FB poate fi folosita pentru reprezentarea FB cu un numar oricât de mare de variabile însa, în mod practic, se utilizeaza pentru reprezentarea FB cu pâna la 6 variabile

Structura

Daca n este numarul de variabile, diagrama V-K va avea 2n casute, una pentru fiecare din cei 2n mintermi (maxtermi) ai FB deci, câte una pentru fiecare linie a tabelului de adevar al functiei

casute sunt aranjate în astfel încât mintermii (maxtermii) sunt reprezentati într-o dispozitie geometrica care permite evidentierea mintermilor adiacenti

Liniile si coloanele diagramei V-K sunt etichetate astfel încât combinatia variabilelor de intrare pentru fiecare casuta este determinata cu usurinta din etichetele atasate liniei si coloanei corespunzatoare casutei

Diagrama V-K pentru n=2