4.1. VARIABILE ȘI EXPRESII LOGICE

Algebra booleană sau algebra logică este un compartiment al matematicii, în care legile gîndirii sînt studiate cu ajutorul metodelor simbolice.

Variabilele algebrei boolene se notează prin x, y, z, x1, x2, … cu sau fără indicii, iar elememntele 0 şi 1 se numesc constante logice.

Operatorii elementari ai algebrei boolene au următoarele denumiri:

_

- negaţia (inversia, operaţia logică NU);

& - conjuncţia (produsul logic, operaţia logică ŞI);

v – disjunţia (suma logică, operaţia logică SAU).

Operatorii elementari se definesc cu ajutorul unor tabele speciale, numite tabele de adevăr.

Tabelul de adevăr este un tabel, care include toate combinaţiile posibile ale valorilor variabilelor, faţă de care este definit operatorul şi rezultatul operaăiei date.

În fig.1 sînt reprezentate tabelele de adevăr ale negaţiei, conjuncţiei, disjuncţiei.

Negaţia

x

x

0

1

1

0

 

Conjuncţia

x

y

x&y

0

0

1

1

0

1

0

1

0

0

0

1

 

Disjuncţia

x

y

Xvy

0

0

1

1

0

1

0

1

0

1

1

1

Fig.3 Tabelele de adevăr ale operatorilor elementari.

Variabele şi constantele logice, reunite cu ajutorul operatorilor ¯, &, v formează expresii logice, de exemplu:

x&yvz,   1&xvz,

xvy&z,   0vxvy,

x&yvz,    1v0.

Valorile expresiilor logice pot fi calculate, utiliznd tabelele de adevăr ale operatorilor elementari. Pentru evaluarea expresiilor se stabileşte următoarea prioritatea a operaţiilor logice:

1)    negaţia;

2)    conjuncţia;

3)    disjuncţia.

Pentru a sistematiza calculele, evaluarea expresiilor logice se efectuiază în tabelele speciale, numite tabele de adevăr ale expresiilor logice.

Tabelul de adevăr al expresiei logice include toate combinaţiile posibile ale valorilor variabilelor din expresia în studiu şi rezultatele operaţilor logice în ordinea calculării lor.

Definiţia formală a algebrei boolene include un şir de postulate, care concretizează propriităţile constantelor logice şi ale operaţiilor elementare.

În postulatele care urmează se utilizează relaţia de egalitate a expresiilor logice, care, ca şi în cazul algebrei clasice, se notează prin simbolul “=”.

Două expresii logice sunt egale, dacă valorile lor coencid pentru toate combinaţiile posibile ale valorilor variabilelor din expresiile respective.

Egalitatea sau inegalitatea expresiilor logice poate fi stabilită, alcătuind tabelele lor de adevăr.

În continuare sunt prezentate postulatele şi teoremele algebrei boolene.

Postulatul 1. Elementul de identitate în raport cu operatorul & este, iar elementul de identitate în raport cu operatorul v este 0:

x&y=1&x=x

xv0=0vx=x

Postulatul 2. Operatorii & şi v respectă legea comutativităţii:

x&y = y&x;

xvy = yvx.

Postulatul 3. Operatorii & şi v respectă legea distributivităţii.

x&(yvz) = (x&y)(x&z);

xv(y&z) = (xvy)(xvz).

Postulatul 4. Pentru negaţia oricarei variabile x se respectă egalităţile:

x&x = 0;

xvx = 1.

Postulatele sunt afirmaţii care nu necesită demonstraţii.

Teorema 1. (idempotenţa):

x&x = x;

xvx = x.

Teorema 2.

x&0 = 0;

xv1 = 1.

Teorema 3. (dublă negaţie):

x = x

Teorema 4. (asociavitatea):

x&(y&z) = (x&y)&z;

xv(y&z) = (xvy)vz.

Teorema 5. (absorbţia):

x&(xvy) = x;

xv(x&y) = x.

Teorema 6. (de Morgan):

____     _  _

(x&y) = xvy;

___     _   _

(xvy) = x&y.

Teoremele, spre deosebire de postulate, trebuie să fie demonstrate.

Una din cele mai importante proprietăţi ale algebrei boolene este principiul dualităţii.Acest principiu constă în faptul că fiecare egalitate dintr-un postulat sau o teoremă rămîne valabilă, dacă operatorul şi elementul de identitate se schimbă.

Postulatele şi teoremele algebrei boolene sunt folosite pentru simplificarea expresiilor logice.


Ultima modificare: marţi, 7 iunie 2011, 14:40