Electronică digitală

Algebra logică şi calculul propoziţional, operează cu propoziţii, despre care are sens să afirmăm că sunt adevărate sau false. Din însăşi definirea propoziţiilor rezultă că o propoziţie poate fi adevărată sau falsă. Propoziţiile pot fi simple şi compuse. Cele compuse se obţin ca rezultat al legăturii propoziţiilor simple, prin intermediul unor conective logice. Adevărul sau falsitatea unei propoziţii compuse este funcţie de valoarea propoziţiilor simple din care se compune şi de tipul legăturii logice.

În logica simbolică se poate face abstracţie de sensul propoziţiilor, operând cu relaţiile de valoare. Convenim ca unei propoziţii adevărate să-i atribuim valoarea binară 1, iar falsitatea acesteia să o notăm cu valoarea binară zero (0).

Propoziţia compusă a cărei valoare depinde de valorile propoziţiilor simple, putând avea tot două valori, se numeşte funcţie logică sau funcţie binară.

Fie A o mulţime nevidă, împreună cu două operaţii binare pe A, denumite reuniune şi intersecţie şi notate cu U şi I.

Prin definiţie, tripletul: ()

IU,,Α=L, (1.1)

este o latice şi se bucură de următoarele proprietăţi:

• comutativitatea:

1221aaaaUU=, , 1221aaaaII=A∈∀21,aa, (1.2)

• asociativitatea: ()

()321321aaaaaaUUUU=, ()()321321aaaaaaIIII=,

A∈∀321,,aaa, (1.3)

• absorbţia:

()1211aaaa=IU, ()1211aaaa=UI, A∈∀21,aa. (1.4)

Proprietăţile (1.2) ÷ (1.4) constituie axiome pentru latici. Se poate observa că în acest sistem de axiome se pot schimba între ele simbolurile U şi I. Evident, acest lucru se poate face în orice afirmaţie care decurge din sistemul de axiome, proprietate cunos-cută sub denumirea de principiul dualităţii pentru latici.

Plecând de la axiomele definite mai sus se poate demonstra şi următoarea proprietate:

• idempotenţa:

aaaa=…UUU, , aaaa=…IIIA∈∀a. (1.6) ()

O latice se poate defini şi ca o mulţime parţial ordonată ≤=,ΑL, care are o cea mai mică margine superioară (c.m.m.m.s.) – s şi o cea mai mare margine inferioară (c.m.m.m.i.) – p, pentru fiecare pereche de elemente. Legătura între cele două definiţii se poate face notând , 21aasU=21aapI=.

Prin definiţie, o latice finită (mărginită) are un element care este c.m.m.m.i., numit ultim element al laticei, notat prin 0, astfel încât:

• legile lui 0:

aa=0U, , (1.7) 00=IaA∈∀a

şi un element care este c.m.m.m.s., numit prim element al laticei, notat prin 1, astfel încât:

• legile lui 1:

11=Ua, , aa=1IA∈∀a. (1.8)

Fie o latice finită şi ()1,0,,,IUA=LA∈a. Un element complementar sau, pe scurt, un complement al elementului a, este elementul a (non a), astfel încât:

• principiul terţului exclus: 1=aaU, (1.9)

care atestă faptul că nu există o a treia posibilitate într-o reuniune cu variabile complementare şi:

• principiul contradicţiei: 0=aaI. (1.10)

Trebuie menţionat că nu orice element dintr-o latice finită are un complement. Astfel, în laticea finită {}(), elementul a nu are complement. De asemenea, complementul unui element al unei latice, dacă acesta există, nu este în mod necesar unic. În schimb, elementele 0 şi 1 au fiecare un complement unic, respectiv 1 şi 0: 1,0,,,1,,0IUa=L10=, 01=.

Dacă într-o latice finită orice element a are un complement unic a, această latice se numeşte complementară.

Prin definiţie o latice este distributivă dacă şi numai dacă: L

• distributivitatea: ()

()()3231321aaaaaaaIUIIU=, A∈∀321,,aaa, (1.11)

()()()3231321aaaaaaaUIUUI=, A∈∀321,,aaa. (1.12)

Proprietatea (1.11) poartă denumirea de distributivitatea reuniunii în raport cu intersecţia iar (1.12) distributivitatea intersecţiei în raport cu reuniunea.