Relatii Fuzzy

8/18/2019 Relatii Fuzzy

1/13

1

RELATII FUZZY

In acest curs vom prezenta cateva elemente din teoria relatiilor fuzzy binare .

Introducerea relatiilor fuzzy si prezentarea unor notiuni si proprietati legate de ele va

urma o linie asemanatoare definirii multimilor fuzzy si a operatiilor lor (vezi cursul

precedent):

- vom aminti definitia relatiilor crisp binare , proprietati ale lor , tipuri de relatii

crisp;toate aceste definitii si proprietati vor fi exprimate in termenii functiilor

caracteristice

-

definitia relatiilor fuzzy binare, a operatiilor si proprietatilor lor va fi realizata pe

baza celor de la punctual precedent.

(I) Relatii clasice (crisp)

Fie X si Y doua multimi nevide si X x Y produsul lor cartezian.

O relatie crisp intre elementele lui X si elementele lui Y este o submultime a lui X x

Y.In cazul cand X = Y spunem ca R este o relatie crisp binara pe X.

Atunci o relatie crisp binara pe X ( pe scurt, relatie crisp) este o submultime R a lui

XxX X 2 ( 2 X R ).

Notatie: Fie x un element al lui X si y un element al lui Y. Atunci notam:

R y x xRydef

),( ( citim: x si y se afla in relatia R).

Relatiile crisp fiind submultimi ale lui X x Y , toate notiunile si proprietatile referitoare la

submultimi crisp se vor pastra si in cazul lor.

De pilda , functia caracteristica }1,0{: 2 X R asociata unei relatii crisp R este

definita prin :

contrar caz in

xRydaca y x R

,0

,1),(

Observatie. Fie R si Q doua relatii crisp ( relativ la X si Y). Atunci, ca si in cazul

submultimilor crisp, este valabila echivalenta urmatoare:


2/13

2

Q RQ R

Rezulta ca o relatie crisp este determinata de functia sa caracteristica.

Vom identifica relatia crisp R cu functia sa caracteristica }1,0{:

2

X R . De aceea,

putem considera o relatie crisp pe X ca fiind o functie }1,0{: 2 X R .

Exemplul 1 Fie o multime X formata din sase indivizi X={a,b,c,d,e,f}.

Pentru orice X x , notam v(x)=varsta lui x.

Vom lua si un caz concret:

v(a) = v(b) = 20

v(c) = 25; v(d) = 30

v(e) = v(f) = 40Consideram urmatoarea relatie crisp binara pe X:

)()( yv xv xRy

In cazul concret considerat, relatia R va fi reprezentata de urmatoarea tabela booleana:

a b c d e fa 1 1 0 0 0 0

b 1 1 0 0 0 0

c 0 0 1 0 0 0

d 0 0 0 1 0 0

e 0 0 0 0 1 1

f 0 0 0 0 1 1

Observatie: O relatie crisp este perfect determinata de tabela booleana ( =matricea

booleana) asociata.

In continuare, vom aminti o serie de conditii ce definesc importante clase de relatii (pe

multimea X).

Spunem ca o relatie crisp binara R pe X este:


3/13

3

reflexiva, daca : xRx, pentru orice xX

ireflexiva, daca: non xRx, pentru orice xX

tranzitiva, daca : xRy, yRz xRz, pentru orice x,y,zX

totala: daca pentru orice xy, avem xRy sau yRx

antisimetrica: daca : xRy, yRx xy, pentru x,yX

simetrica: daca: xRy yRx, pentru orice x, y X

Considerand relatia crisp R ca o functie }1,0{: 2 X R , proprietatile de mai sus capata

forma urmatoare:

reflexiva: R(x, x) = 1, pentru orice

ireflexiva: R (x, x) = 0, pentru orice

tranzitiva : pentru orice x,y,z X, R(x,y) =1 si R(y,z) = 1 implica R(y,z)= 1

sau, echivalent : R(x,y) R(y,z) R(x,z)

sau, echivalent : R(x,y) R(y,x) = 1

antisimetrica : pentru orice x,y X , R(x,y) = 1 si R(y,x) = 1 implica x = y

simetrica : pentru orice x,y X , R(x,y) = 1 implica R(y,x) = 1

Observatie : (i) O relatie crisp R este reflexiva daca tabela booleana asociata are 1 pe

diagonala principala.

(ii) O relatie crisp R este simetrica daca si numai daca R(x,y) = R(y,x),

pentru orice x, y X . Rezulta ca R este simetrica daca si numai daca tabela booleana

asociata este simetrica.

(iii) O relatie crisp R este antisimetrica daca si numai daca

R(x,y) + R(y,x) 1, pentru orice x, y X .

Proprietatile de mai sus ne permit sa definim cateva tipuri de relatii:

- relatia de echivalenta : reflexiva, simetrica si tranzitiva

- relatia de ordine partiala: reflexiva, antisimetrica si tranzitiva


4/13

4

- relatia de ordine totala: reflexiva, antisimetrica, tranzitiva si totala

- relatia de preordine: reflexiva si tranzitiva

- relatia de ordine slaba :reflexiva, tranzitiva si totala

Ca terminologie, vom spune pe scurt:

- relatie de ordine= ordine= relatie de ordine partiala

- ordine totala= relatie de ordine totala

- preordine= relatie de preordine

- ordine slaba= relatie de ordine slaba

(II) Relatii fuzzy binare

Fie X si Y doua multimi nevide. Am vazut in sectiunea precedenta ca o relatie crisp pe X

poate fi gandita ca o functie }1,0{: 2 X R . Generalizam aceasta notiune astfel:

Definitie. O relatie fuzzy este o submultime fuzzy a lui X x Y , adica o functie

]1,0[: XxY R .

O relatie fuzzy binara ( relatie fuzzy, pe scurt) pe X este o functie ]1,0[: 2 X R .

Pentru orice element x al lui X si orice element y al lui Y numarul real R(x,y) [0, 1]

va fi gradul in care x si y se afla in relatia R.

Exemplul 2.Fie X multimea bunicilor dintr-o familie si Y multimea nepotilor:

X= },{ 21 bb ; Y = },,{ 321 nnn .

Consideram relatia fuzzy ]1,0[: XxY R , cu intelesul :

“ copilul y seamana cu bunicul x”

definita de tabela urmatoare:

1n 2n 3n

1b 0.8 0.5 0.7

2b 0.9 0.6 0.7

Daca y este unul dintre copii si x unul dintre bunici atunci numarul real R(x,y) este

gradul in care copilul y seamana cu bunicul x.


5/13

5

De exemplu:

9.0),( 12 nb R : cea mai mare asemanare (cu gradul 0.9) are loc intre copilul 1n si

bunicul2

b .

Exemplul 3. Fie multimea X = {a,b,c,d,e,f} din Exemplul 1.

Enuntul urmator : “ indivizii x si y sunt de varste apropiate” nu poate fi considerat o

relatie crisp pe X.

Sa ne dam tabela urmatoare:

a b c d e f

a 1 1 0.5 1 0.5 0.9

b 1 1 0.2 1 0.25 0.4

c 0.25 0.2 1 0.3 0.5 0.7d 1 1 0.3 1 0.6 0.8

e 0.5 0.25 0.5 0.6 1 0

f 0.9 0.4 0.7 0.8 0 1

Pentru orice doua elemente x,y ale lui X , sa definim

R(x,y) = numarul real din tabela de pe linia x si coloana y.

Atunci obtinem o relatie fuzzy pe X ce poate reprezenta enuntul “ indivizii x si y sunt de

varste apropiate”.

Observati e. R(x,y) va fi gradul in care indivizii x si y sunt de varste apropiate .Numarul

real R(x,y) apartine intervalului [0, 1].

- Daca R(x,y)= 1 atunci diferenta de varsta intre x si y este insesizabila (x si y pot

sa nu aiba exact aceeasi varsta!- totusi putem spune ca au “aceeasi varsta” ). In

cazul exemplului nostru, indivizii a, b si d au “ aceeasi varsta” , in sensul ca nu

putem distinge diferentele de varsta.

- Daca R(x,y) = 0.9 ( a si f in cazul nostru) atunci x si y vor avea intr-adevar varste

apropiate ( 0.9 este gradul in care varsta lui x se apropie de varsta lui y).- Daca R(x,y) = 0 atunci diferenta de varsta intre x si y este considerabila( e si f in

cazul exemplului)

Exemplul 4. Un grup de experti in degustarea vinului compara cinci soiuri de vin a,b,c,d

si e. Fie X= {a, b, c, d, e} multimea celor cinci soiuri.


6/13

6

Pentru orice soiuri x si y notam:

R(x,y) = proportia in care degustatorii considera vinul x cel putin la fel de bun ca vinul y.

Sa presupunem ca valorile lui R(x,y ) sunt inscrise in tabela urmatoare:

a b c d e

a 1 0.57 0.57 0.29 0.63

b 0.43 1 0.70 0.52 0.28

c 0.43 0,30 1 0.72 0.48

d 0.71 0.48 0.28 1 0.48

e 0.37 0.72 0.52 0.52 1

Se observa ca

R(x,y) + R(y,x) = 1, daca vinul x este diferit de vinul y

R(x,x) = 1: vinul x este cel putin la fel de bun ca x.

Operatii cu relatii fuzzy

Relatiile fuzzy fiind submultimi fuzzy ale lui X x Y definitia operatiilor cu relatii fuzzy

se va incadra in definitia operatiilor cu submultimi fuzzy ( din cursul trecut).

Vom prezenta principalele operatii cu multimi fuzzy.

Fie ]1,0[: Y X R si ]1,0[: Y X Q doua relatii fuzzy pe XxY.

Reuniunea R Q: ]1,0[Y X se defineste prin

(R Q ) (x,y) = R(x,y) Q(x, y) , pentru orice x,y X

Intersectia R Q: ]1,0[Y X se defineste prin

(R Q ) (x,y) = R(x,y) Q(x,y) , pentru orice x,y X

Relatia opusa ]1,0[: Y X R se defineste prin:

),(1),( y x R y x R , pentru orice x,y X

O operatie speciala este compunerea relatiilor fuzzy : daca ]1,0[: Y X R ,

]1,0[: Z Y Q , atunci ]1,0[: Z X Q R este definita de:


7/13

7

}|),(),({),)(( Y y z yQ y x R z xQ R

Daca R, Q sunt relatii fuzzy pe X, atunci Q R este o relatie fuzzy pe X:

}|),(),({),)(( X y z yQ y x R z xQ R

Ridicarea la putere: Fie R o relatie fuzzy pe X, ]1,0[: 2

X R . Definim ]1,0[: 2

X Rn

,

R R Rn ... (de n ori), 1n .

Exemplul 5. Fie X = {a, b, c} si R, Q relatiile fuzzy pe X definite de matricile urmatoare:

R=

15.00

02.03.0

7.001

, Q=

01.00

1.06.00

06.06.0

Atunci

Q R =

1.05.00

1.03.03.0

06.06.0

Exemplificam calculul elementelor matricii

R(c,b) = [R(c,a) Q(a,b)] [R(c,b) Q(b,b)] [R(c,c) Q(c,b)]

= [0 0.6] [0.5 0.6] [1 0.1]

= 0 0.5 0.1 = 0.5

Exercitiu: Fie R si Q matricile din Exemplul 5.

(a)

Sa se calculeze R Q, R Q, R , Q .

(b) Sa se calculeze 3 R , 2Q .

(c) Sa se calculeze RQ R .

Tipuri de relatii fuzzy

Fie X o multime nevida. O relatie fuzzy R pe multimea X ( ]1,0[: 2 X R ) se numeste:

Reflexiva: R(x,x) = 1, pentru orice x X

Ireflexiva: R(x,x) =0 , pentru orice x X

Tranzitiva: pentru orice x, y,z X, R(x,y) R(y,z) R(x,z)

Totala: pentru orice elemente distincte x, y X , R(x,y) R(y,x) = 1

Antisimetrica: pentru orice x, y X, R(x,y) + R(y,x) 1, pentru xy

Simetrica : pentru orice x, y X , R(x,y) = R(y,x).


8/13

8

Observatie. Particularizand aceste definitii la relatii crisp regasim definitiile operatiilor

cu relatii crisp din Sectiunea 1.

O relatiile fuzzy R pe X se numeste:

Ordine fuzzy: daca este reflexiva, antisimetrica si tranzitiva

Ordine fuzzy totala: ordine fuzzy care este totala

Preordine fuzzy: daca este reflexiva si tranzitiva

Ordine fuzzy slaba: preordine fuzzy care este totala

(III) Relatii de preferinta fuzzy

Fie X un univers nevid. Elementele lui X se vor numi alternative.

Vrem sa definim ce ar putea insemna din punct de vedere matematic ca “o alternativa x ar

fi preferata unei alternative y” .

Si in acest caz vom porni de la modelarea crisp a preferintelor. Avem in vedere doua

tipuri de preferinte (existente in literatura):

(a) preferinta slaba, cu intelesul:

“ alternativa x este cel putin la fel de buna ca alternativa y”.

Preferinta slaba este modelata de relatiile crisp reflexive. Ne plasam in acest context

foarte general, impunand in definitia preferintelor slabe numai reflexivitatea:

“ x este cel putin la fel de bun ca x”.

In unele situatii (social choice theory (=teoria alegerilor sociale), microeconomie, teoria

deciziilor ) se cere ca preferinta slaba sa fie o preordine sau chiar o ordine slaba (=

preordine totala).

(b)

preferinta stricta , cu intelesul

“ alternativa x este in mod strict mai buna decat y”.

Preferintele stricte sunt modelate prin relatii ireflexive, sau in unele cazuri prin relatii

ireflexive si tranzitive.

Modelarea fuzzy a preferintelor


9/13

9

Pornind de la discutia de mai sus asupra preferintelor crisp putem trece la modelarea

fuzzy a preferintelor .

Este vorba de preferinte vagi (de tip fuzzy) pentru care putem evalua doar gradul in care

o alternativa ar fi preferata alteia

Este clar ca aceste preferinte vor fi modelate prin relatii fuzzy pe multimea X a

alternativelor. Vom folosi definitiile proprietatilor de reflexivitate, ireflexivitate,

tranzitivitate, etc ale relatiilor fuzzy ( vezi sectiunea 2).

O relatie de preferinta fuzzy slaba (= preferinta fuzzy slaba) pe X este o relatie fuzzy

reflexiva R pe X.

In acest caz, pentru orice doua alternative x si y , numarul real R(x,y) va fi gradul in care

alternativa x este cel putin la fel de buna ca y.

O relatie de preferinta fuzzy stricta (= preferinta fuzzy stricta ) pe X este o relatie fuzzy

ireflexiva pe X.

In acest caz, pentru orice doua alternative x si y , R(x,y) va fi gradul in care alternativa x

este strict mai buna decat y.

In unele situatii, se cere ca preferintele fuzzy slabe si preferintele fuzzy stricte sa fie si

transitive.

Nota. In literatura ( asupra relatiilor crisp sau a relatiilor fuzzy ) uneori se foloseste

terminologia :

- relatii de preferinta = relatii de preferinta slabe.

Partea stricta a unei relatii de preferinta fuzzy

Vom porni tot de la cazul crisp.

Fie R o relatie de preferinta crisp pe X. Definim relatia crisp R P pe X in felul urmator:

R y x P y xdef

R ),(),( si R x y ),(

Aceasta definitie poate fi exprimata si astfel

),(),(),( x y R y x R y x P R

Cum R este reflexiva rezulta imediat ca R P este o relatie de preferinta stricta ( rezulta

imediat ireflexivitatea lui R P ).

R P se numeste partea stricta asociata relatiei de preferinta R.

Cazul fuzzy


10/13

10

Fie R o relatie de preferinta fuzzy pe X. Definim relatia fuzzy ]1,0[: 2 X P R prin

)),(1(),(),(),(),( x y R y x R x y R y x R y x P R

Cum 1),( x x R rezulta

0)),(1(),(),( x x R x x R x x P R

Deci R P este ireflexiva. Atunci R P este o relatie de preferinta fuzzy stricta numita partea

stricta a lui R.

Relatia de indiferenta asociata unei relatii de preferinta fuzzy

Cazul crisp

Fie R o relatie de preferinta crisp pe X. Definim relatia crisp R I pe X in felul urmator :

R y x I y xdef

R ),(),( si R x y ),(

Cazul fuzzy

Fie R o relatie de preferinta fuzzy pe X (deci reflexiva). Definim relatia fuzzy R I pe X

prin:

),(),(),( x y R y x R y x I R pentru orice x,y X.

Observatie. R I este o relatie fuzzy reflexiva si simetrica:

R I (x,x) = R(x,x) R(x,x) = 1 1= 1

R I (x,y) = R(x,y) R(y,x) = R(y,x) R(x,y) = R I (y,x)

R I se numeste relatia de indiferenta asociata lui R.

Observatie Fie 1 R transpusa lui R: ),(),(1 x y R y x R . Atunci

11 )( R R R R P R .Demonstratie:

Este suficient sa demonstram ca 11 )( R R . Aceasta rezulta din: pentru orice x,y X,

),()(),(),(1),(1),( 111 y x R x y R x y R y x R y x R

Exemplu

Fie X={a,b,c} si relatia de preferinta R pe X data de tabelul:


11/13

11

a b c

a 1 0.2 0.3

b 0.5 1 0.4

c 1 0.6 1

Matricial, R se scrie: R=

16.01

4.015.0

3.02.01

. Calculam R P si R I :

R R

1

04.00

6.005.0

7.08.00

Transpusa lui R este

06.07.0

4.008.0

05.00

)( 1

R .

Transpusa lui R este

14.03.0

6.012.0

15.011 R .

06.07.04.005.0

02.00

06.07.04.008.0

05.00

16.014.015.0

3.02.01

)( 1

R R P R

14.03.0

6.012.0

15.01

16.01

4.015.0

3.02.011 R R I

R =

14.03.0

4.012.0

3.02.01

.


12/13

12

L. A. ZADEH (1921 - )


13/13

13

GR. C. MOISIL (1906 – 1973 )

Relatii Fuzzy

Documents

Transcript of Relatii Fuzzy