Functii booleene - modalitati de reprezentare a unei functii

FUNCTII BOOLEENE

1 DEFINITIA FUNCTIEI BOOLEENE

Functia,la modul general,este definite de doua multimi (una numita domeniu de definite si cealalta numita multime in care functia ia valori sau codomeniu) si o relatie care stabileste corespondenta intre elementele celor doua multimi.Fiecarui element din domeniu ii corespunde un singur element din codomeniu.Daca domeniul este multimea numerelor intregi iar codomeniul este tot multimea numerelor intregi,spunem ca avem o functie intreaga cu valori intregi ale variabilei.Daca domeniul este multimea numerelor intregi iar codomeniul multimea numerelor reale avem o functie reala cu valori intregi ale variabilei.

Functia booleana este o functie definite pe produsul cartezian B∙B∙ ∙B cu valori in B.

Exemplu:Functia f: B∙B→B

2 MODALITATI DE REPREZENTARE A UNEI FUNCTII

O functie booleana poate fi reprezentata printr-o expresie booleana care evidentiaza numai relatia dintre elementele domeniului si codomeniului sau printr-un table de adevar,caz in care sunt explicitate toate elementele domeniului de definitie si relatia de corespondenta cu elementele codomeniului.

Prin tabele exista mai multe forme de prezentare,Astfel,pentru functii de doua variabile avem formele date de tabelul a) si b).

a)

0 1 xy

0

1

b)

Observatie! Forma prezentata in tabelul b) utilizeaza un numar mai mic de cellule decat cea din tabelul a).Elementele domeniului de definitie,care in tabelul a) sunt explicite,in tabelul b) se recompun din valorile variabilelor functiei asezate pe orizontala si verticala.

Pentru functiile de trei variabile cele doua forme sunt prezentate in tabelul c) respectiv d),iar pentru functiile de 4 variabile in tabelul e) respective f).

0 0 0 1 1 0 1 1 z

0

1
c)

d)

e)

0 0 0 1 1 0 1 1 yz/wx

00

01

10

11

3 SCHIMBAREA FORMEI DE REPREZENTARE A FUNCTIEI

Trecerea de la o expresie la tabel se face prin calculul valorii functiei pentru fiecare combinatie a variabilelor functiilor(fiecare mintermen).

Exemplu: f(x,y)= + y

f(0,0) = 0 ∙ + + 0 =0 ∙ 1+ 1 ∙ 0= 0 + 0 =0

f(0,1) = 0 ∙ + ∙ 1 =0 ∙ 0 + 1 ∙1=0 + 1=1

f(1,0) = 1 ∙ + ∙ 0 =1 ∙ 0 + 0 ∙ 0=1 + 0=1

f(1,1) = 1 ∙ + ∙ 1 =1 ∙ 0 + 0 ∙ 1= 0 + 0=0

m

m

m

m

Trecerea de la tabel la expresie se face pe baza urmatoarelor reguli:

• Se ia in consideratie numai valoarea 1 a functiei;
• Pentru fiecare valoare 1 a functiei,expresia va contine un mintermen;
• La scrierea mintermenului se utilizeaza asocierea: 0 pentru variabila negate si pentru variabila simpla;
• Expresia rezultata este forma canonica a functiei.

Exemplu:Fie functia data prin tabel:

m

m

m

m

m

m

m

m

Expresia functiei va fi:

f (a,b,c) = c + ac + ab = m + m + m=m(1,5,6)