Noţiuni de algebră booleană

(în lucru)

Definiţie

Algebră booleană = o structură algebrică formată din:O mulţime BDouă operaţii binare notate cu (+) şi (.)O operaţie unară notată cu (‘) pentru care sunt valabile 6 axiome:

Axiomele algebrei booleene

1. Mulţimea B conţine cel puţin două elemente diferite

2. Axioma închiderii: operaţiile (+) şi (.) sunt operaţii interne adică:

∀a,b∈B(i) a+b ∈B(ii) a.b ∈B

Axiomele algebrei booleene

3. Existenţa elementelor neutre pentru operaţiile binare

(i) ∃ element neutru faţă de operaţia (+) notat cu 0 a.î.:∀a∈B , a+0=a

(i) ∃ element neutru faţă de operaţia (.) notat cu 1 a.î.∀a∈B , a.1=a

Axiomele algebrei booleene

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.c

Axiomele algebrei booleene

6. Existenţa elementului opus

∀a ∈B, există elementul opus lui a, notat a’ a.î.:(i) a+a'=1(ii) a.a'=0

Denumirea operaţiilor

Operaţia “ + ” se numeşte sumă logică, adunare logică, surjecţie şi o vom numi pe scurt sumăOperaţia “ . ” se numeşte produs logic, înmulţire logică, conjuncţie şi o vom numi pe scurt produsOperaţia “ ‘ ” se numeşte negare sau complementare

Prioritatea operaţiilor

În cadrul unei algebre booleene operaţiile au urmatoarea prioritate( ) – expresiile din paranteză’ – operaţia de complementare. – operaţia de înmulţire logică+ – operaţia de sumare logică

Principiul dualităţii

• Axiomele algebrei booleene sunt prezentate în perechi fiecare axiomă din pereche fiind duala celeilalte

• O axiomă se poate obţine din duala sa modificând operaţia “+” cu operaţia “.” şi elementul 0 cu elementul 1 (şi invers).

• Exemplu: existenţa elementului opus(i) a + a‘ = 1

↕ ↕(ii) a . a‘ = 0

Proprietăţile algebrei booleene

Idempotenţa∀a∈B(i) a + a = a (ii) a.a = a

Proprietăţile lui 0 şi 1∀a∈B(i) a+1=1(ii) a.0 = 0

Proprietăţile algebrei booleene

Unicitatea lui 0 şi 1Elementele 0 şi 1 sunt unice

Unicitatea elementului opusPentru ∀a∈B , a’ este unic

Distincţia dintre 0 şi 1Elementele 0 şi 1 sunt distincte

Involuţia∀a∈B, (a')'=a

Proprietăţile algebrei booleene

Absorbţia∀a,b∈B(i) a + a.b = a (ii) a.(a+b) = aAsociativitatea

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

Proprietăţile algebrei booleene

De Morgan∀a,b∈B(i) (a + b)’ = a’ . b’(ii) (a . b)’ = a’ + b’

Exemple de algebre booleene

Algebra binarăB={0,1} împreună cu operaţiile

Definire alternativă a operaţiilor

Exemple de algebre booleene

Simboluri– Contact normal deschis (cnd)– Contact normal închis (cni)

K= mulţimea contactelor electrice împreună cu operaţiile:– Legare în serie

– Legare în paralel

– Schimbarea stării contactului

Comutativitate

a b b a≡

a b

b ≡ a

Element neutru

a 1 a≡

a a

0 ≡

Distributivitate

a a a

b c ≡ b c

b a ba

c ≡ a c

Element opus

a a 0≡

a 1

a ≡

Idempotenţa

a a a≡

a a

a ≡

Proprietăţile lui 0 si 1

a 0 0≡

a 1

1 ≡

Absorbţia

a a

a b ≡

a a a

b ≡

De Morgan

a d a b F

b ≡

d F

a b d a F

d F ≡ b

Funcţiile booleene de două variabile

n=2 nr. de variabile22=4 combinaţii de valori pentru variabile222=16 funcţii de 2 variabile

Funcţiile booleene de două variabile

F0 = 0 Funcţia constantă 0F1 = A.B (SI) ANDF2 = AB' Inhibiţie (A dar nu B)F3 = A IdentitateF4 = A B Inhibiţie (B dar nu A)F5 = B IdentitateF6 = AB' + A'B SAU-Exclusiv (XOR), se notează şi A⊕BF7=A+BSAUF8 = (A + B)' SAU-NU (NOR) (în logica matematică denumită funcţia lui Peirce,

se mai notează A ↓BF9 = A'B' + AB Echivalenţă, se notează şi A≡BF10=B' Complement, NU (NOT)F11 = A + B' Implicaţie (B implică A), se notează şi B → AF12 = A'Complement, NU (NOT)F13= A' + B Implicaţie (A implică B), se notează şi A → BF14 = (AB)' SI-NU (NAND) - în logica matematică denumită funcţia Sheffer, se

mai notează A ↑BF15 = 1 Funcţia constantă 1