Relações
Adriano Joaquim de O Cruz
©2002
NCE/UFRJ
[email protected]
Introdução




Relações são associações entre
elementos de diferentes conjuntos
Se o grau de associação é um ou zero
temos uma relação clássica
Se o grau pode variar entre estes
valores a relação é nebulosa
Por exemplo x é maior que y
@2001 Adriano Cruz
NCE e IM - UFRJ
Relações 2
Funções e Relações



Funções e Relações são
mapeamentos.
Funções fazem mapeamentos de
muitos para um.
Relações podem fazer mapeamentos
de muitos para muitos.
@2001 Adriano Cruz
NCE e IM - UFRJ
Relações 3
Produto Cartesiano

Produto cartesiano de dois conjuntos X
e Y é definido como
X  Y  {( x, y ) | x  X e y  Y }

Para n conjuntos (Ai) o produto
cartesiano é definido como
A1  A2   An  {(a1 , a2 ,, an ) | ai  Ai , i  1..n}
@2001 Adriano Cruz
NCE e IM - UFRJ
Relações 4
Relações Clássicas

Uma relação é um subconjunto do produto
Cartesiano
R( A1 , A2 ,, An )  A1  A2   An

O produto cartesiano pode ser considerado
uma relação sem restrições.

Uma relação entre dois conjuntos é chamada
de relação binária.
@2001 Adriano Cruz
NCE e IM - UFRJ
Relações 5
Função Característica

Mede a força da relação entre os pares
1 ( x, y )  R
 R ( x, y )  
0 ( x, y )  R
@2001 Adriano Cruz
NCE e IM - UFRJ
Relações 6
Representação de Relações


Conjuntos de pares.
Considere uma família e relação é primo de
X  {Beatriz, Clara, Débora, Marco}
R  é primode
R XX
R  {( Beatriz, Débora), ( Beatriz, Marco),
(Clara, Débora), (Clara, Marco), ( Débora, Beatriz),
( Débora, Clara), ( Marco, Beatriz), ( Marco, Clara)}
@2001 Adriano Cruz
NCE e IM - UFRJ
Relações 7
Representação de Relações

Matrizes que mostram os valores da
função característica
Beatriz Clara Débora Marco
Beatriz
0
0
1
1
0
0
1
1
Débora
1
1
0
0
Marco
1
1
0
0
primode  Clara
@2001 Adriano Cruz
NCE e IM - UFRJ
Relações 8
Representação de Relações

Diagramas que mostram os elementos
dos conjuntos como pontos e as relações
como ligações entre os pontos
Beatriz
Beatriz
Clara
Clara
Débora
Débora
Marco
Marco
@2001 Adriano Cruz
NCE e IM - UFRJ
Relações 9
Relações Especiais

Considere um conjunto A={0,1,2} e as
relações abaixo em A  A

Relação Identidade I={0,0),(1,1),(2,2)}

Relação Universal
U={(0,0),(0,1),(0,2),(1,0),(1,1),(1,2),(2,0)
,(2,1),(2,2)}
@2001 Adriano Cruz
NCE e IM - UFRJ
Relações 10
Relações em Universos contínuos
y  2x
R  {( x, y ) | y  2 x, x  X , y  Y }
1
 R ( x, y )  
0
@2001 Adriano Cruz
NCE e IM - UFRJ
y  2x
y  2x
Relações 11
Propriedades de Relações Clássicas

Sejam X e Y dois sub-conjuntos de um
universo U.

Sejam os elementos x  X e y  Y.

Seja S o produto cartesiano X Y .

Seja R uma relação clássica em S.
@2001 Adriano Cruz
NCE e IM - UFRJ
Relações 12
Propriedades de Relações Clássicas

Reflexiva: R é reflexiva se (x,x)R para
qualquer xX.

Não reflexiva: R é irreflexiva se existir pelo
menos um x tal que (x,x)R.

Anti-reflexiva: R é anti-reflexiva se não existe
um xX para o qual (x,x)R.
@2001 Adriano Cruz
NCE e IM - UFRJ
Relações 13
Propriedades de Relações Clássicas



cont 1
Simétrica: R é simétrica se para todo
elemento xX e yY temos que se (x,y)R
então (y,x)R.
Assimétrica: R é assimétrica se não existem
elementos xX e yY para os quais (x,y)R
e (y,x)R.
Antissimétrica: R é antissimétrica se para
todo xX e yY, quando (x,y)R e (y,x)R
então x=y.
@2001 Adriano Cruz
NCE e IM - UFRJ
Relações 14
Propriedades de Relações Clássicas


cont 2
Transitiva: R é transitiva se para todo x,y,z
temos que se (x,y)R e (y,z) R então
(x,z)R.
Conectada: R é conectada se para todo x e y
temos que se xy então (x,y)R ou (y,x)R.
@2001 Adriano Cruz
NCE e IM - UFRJ
Relações 15
Propriedades de Relações Clássicas



cont 3
Única à esquerda: R é única à esquerda
quando para todo x,y,z temos que se (x,z)R
e (y,z)R então x=y.
Única à direita: R é única à direita quando
para todo x,y,z temos que se (x,y)R e
(x,z)R então y=z.
Bi-única: uma relação que é única à direita e
à esquerda é chamada de bi-única.
@2001 Adriano Cruz
NCE e IM - UFRJ
Relações 16
Relação R=é primo de



A relação não é reflexiva porque uma pessoa
não é prima de si mesmo, logo ela é
antireflexiva porque não há elemento de R
que seja primo de si mesmo.
A relação é simétrica porque se Beatriz é
prima de Débora então Débora e prima de
Beatriz e portanto não assimétrica.
A relação também não é antissimétrica
porque ela é não é reflexiva nem assimétrica.
@2001 Adriano Cruz
NCE e IM - UFRJ
Relações 17
Relação R=é primo de cont 1

A relação não é transitiva porque Débora e
prima de Clara e Clara é prima de Marco
mas Débora não é prima de Marco.

A relação não é conectada porque existem
pares de elementos diferentes para os quais
a relação não se aplica. Por exemplo, Marco
não é primo de Débora.
@2001 Adriano Cruz
NCE e IM - UFRJ
Relações 18
Relação R=é primo de cont 2



A relação não é única à esquerda porque
Beatriz e Clara são diferentes pessoas e
primas de Débora.
A relação não é única à direita porque
Débora é prima de Beatriz e Clara que são
diferentes pessoas.
Como a relação não nem única à esquerda
nem à direita ela não é bi-única.
@2001 Adriano Cruz
NCE e IM - UFRJ
Relações 19
Relações Clássicas de Equivalência

Relações que são reflexivas, simétricas e
transitivas são chamadas de relações de
equivalência.

A relação de similaridade entre triângulos é
uma relação de equivalência.

A relação trabalha no mesmo edifício que é
uma relação de equivalência.
@2001 Adriano Cruz
NCE e IM - UFRJ
Relações 20
Relações Clássicas de Tolerância


Relações que são reflexivas e simétricas são
chamadas de relações de tolerância.
A relação nítida “A cidade x é perto da cidade y”
é uma relação de tolerância.
– A cidade x obviamente é perto dela mesma
(reflexiva).
– Se a cidade x é perto da cidade y então a cidade
y é perto da cidade x (simétrica).
– Não é certo que se x é perto de y e y é perto de z
então x é perto de z (transitiva).
@2001 Adriano Cruz
NCE e IM - UFRJ
Relações 21
Tipos de Relações
Reflexiva Antireflex Simétrica Antisimét Transitiva
Equiv
Quase
Equiv
Tolerância
Ordem
Parcial
X
X
X
X
X
X
X
X
@2001 Adriano Cruz
X
NCE e IM - UFRJ
X
Relações 22
Operações com Relações Clássicas


Sejam R e S duas relações no universo
Cartesiano XY.
Sejam as relações
0 0  0 
0 0  0 

O
   
0 0  0 


@2001 Adriano Cruz
1
1
E

1

NCE e IM - UFRJ
1  1
1  1

  

1  1
Relações 23
Operações com Relações Clássicas cont 1
União :
R  S   RS ( x, y )  max[ R ( x, y ),  S ( x, y )]
Interseção:
R  S   RS ( x, y )  min[ R ( x, y ),  S ( x, y )]
Complemento :
 R ( x, y )  1   R ( x, y )
@2001 Adriano Cruz
NCE e IM - UFRJ
Relações 24
Propriedades das Operações Clássicas
Comutatividade
A B  B  A
A B  B  A
Associatividade A  ( B  C )  ( A  B )  C
A  ( B  C )  ( A  B)  C
Distributividade A  ( B  C )  ( A  B )  ( A  C )
A  ( B  C )  ( A  B)  ( A  C )
@2001 Adriano Cruz
NCE e IM - UFRJ
Relações 25
Propriedades das Operações Clássicas
cont 1
Idempotência
Identidade
@2001 Adriano Cruz
A A  A
A A  A
A  A
A  
A X  X
A X  A
NCE e IM - UFRJ
Relações 26
Propriedades das Operações Clássicas
cont 2
Exclusão
do Meio
A A  E
A A  
De Morgan A  B  A  B
A B  A B
@2001 Adriano Cruz
NCE e IM - UFRJ
Relações 27
Composição de Relações Clássicas
R
X
S
Y
Z
T=R°S
@2001 Adriano Cruz
NCE e IM - UFRJ
Relações 28
Composição de Relações Clássicas
RS 
 y [  R ( x, y)   S ( x, y)]
X Y
  max
  min ou
  produto
 A operação ° é similar à uma
multiplicação de matrizes
@2001 Adriano Cruz
NCE e IM - UFRJ
Relações 29
Exemplo de Composição
x1
y1
z1
x2
y2
z2
x3
y3
z3
R  X Y
x4
@2001 Adriano Cruz
S Y Z
NCE e IM - UFRJ
Relações 30
Exemplo de Composição
1
0
R
0
0

1 0
1 0

0 1
0 1
1 0 0
S  0 0 1 


1 0 0
1
0
RS  
1
1

@2001 Adriano Cruz
0 1
0 1

0 0

0 0
NCE e IM - UFRJ
Relações 31
Exemplo de Composição
x1
z1
x2
z2
x3
z3
1
0
RS  
1
1

0 1
0 1

0 0

0 0
x4
@2001 Adriano Cruz
NCE e IM - UFRJ
Relações 32
Relações Nebulosas



Relações (R) mapeiam elementos de
um conjunto (X) em outro conjunto (Y).
A força da relação é medida em termos
de funções de inclusão que podem
variar entre 0 e 1.
R:XY[0:1]
@2001 Adriano Cruz
NCE e IM - UFRJ
Relações 33
Relações Nebulosas



Sejam Ai conjuntos nebulosos.
Uma relação nebulosa é um subconjunto do
produto Cartesiano
R( A1 , A2 ,, An )  A1  A2   An
O produto cartesiano pode ser considerado
uma relação sem restrições.
@2001 Adriano Cruz
NCE e IM - UFRJ
Relações 34
Função Característica


Mede a força da relação entre os pares
Sejam A(x) e B(x) os graus de
inclusão de x e y nos conjuntos A e B
respectivamente.
 R ( x, y )   AB ( x, y )
 R ( x, y )  min[ A ( x),  B ( x)]
@2001 Adriano Cruz
NCE e IM - UFRJ
Relações 35
Função Característica Exemplo



Conjunto A={(x1,0.2),(x2,0.5),(x3,1)}
Conjunto B={(y1,0.3),(y2,0.9)}.
R=AB
y1
R
@2001 Adriano Cruz
y2
x1
0 .2 0 . 2
x2
0 .3 0 .5
x3
0 .3 0 .9
NCE e IM - UFRJ
Relações 36
Propriedades de Relações Nebulosas


Sejam X e Y dois sub-conjuntos nebulosos
de um universo U.
Sejam os elementos x  X e y  Y com
graus X(x) e Y(y).

Seja S o produto cartesiano X Y .

Seja R uma relação nebulosa em S.
@2001 Adriano Cruz
NCE e IM - UFRJ
Relações 37
Propriedades de Relações Nebulosas





Propriedades com definições similares às
das relações clássicas:
Reflexiva, Não reflexiva, Anti-reflexiva;
Simétrica, Assimétrica, Antissimétrica;
Conectada
Única à esquerda, Única à direita, Bi-única
@2001 Adriano Cruz
NCE e IM - UFRJ
Relações 38
Propriedades de Relações Nebulosas

Transitiva: R é transitiva se para todo x,y,z
temos que se (x,y)R e (y,z) R então
(x,z)R.
Se  R ( xi , x j )  1 e  R ( x j , xk )  2
então R ( xi , xk )  min(1 , 2 )
@2001 Adriano Cruz
NCE e IM - UFRJ
Relações 39
Relações Nebulosas de Similaridade
(Equivalência)

Relações que são reflexivas, simétricas
e transitivas são chamadas de relações
de equivalência.
@2001 Adriano Cruz
NCE e IM - UFRJ
Relações 40
Relações Nebulosas de Tolerância


Relações que são reflexivas e simétricas são
chamadas de relações de tolerância.
A relação nebulosa “A cidade x é perto da cidade
y” é uma relação de tolerância.
– A cidade x obviamente é perto dela mesma
(reflexiva).
– Se a cidade x é perto da cidade y então a cidade
y é perto da cidade x (simétrica).
– Não é certo que se x é perto de y e y é perto de z
então x é perto de z (transitiva).
@2001 Adriano Cruz
NCE e IM - UFRJ
Relações 41
Operações com Relações Nebulosas


Sejam R e S duas relações no universo
Cartesiano XY.
Sejam as relações
0 0  0 
0 0  0 

O
   
0 0  0 


@2001 Adriano Cruz
1
1
E

1

NCE e IM - UFRJ
1  1
1  1

  

1  1
Relações 42
Operações com Relações Nebulosas
cont 1
União :
R  S   RS ( x, y )  max[ R ( x, y ),  S ( x, y )]
Interseção:
R  S   RS ( x, y )  min[ R ( x, y ),  S ( x, y )]
Complemento :
 R ( x, y )  1   R ( x, y )
@2001 Adriano Cruz
NCE e IM - UFRJ
Relações 43
Propriedades das Operações
Comutatividade
A B  B  A
A B  B  A
Associatividade A  ( B  C )  ( A  B )  C
A  ( B  C )  ( A  B)  C
Distributividade A  ( B  C )  ( A  B )  ( A  C )
A  ( B  C )  ( A  B)  ( A  C )
@2001 Adriano Cruz
NCE e IM - UFRJ
Relações 44
Propriedades das Operações cont 1
Idempotência
Identidade
@2001 Adriano Cruz
A A  A
A A  A
A  A
A  
A X  X
A X  A
NCE e IM - UFRJ
Relações 45
Propriedades das Operações cont 2
Exclusão
do Meio
A A  E
A A  
De Morgan A  B  A  B
A B  A B
@2001 Adriano Cruz
NCE e IM - UFRJ
Relações 46
Composição de Relações Nebulosas
R
X
S
Y
Z
T=R°S
@2001 Adriano Cruz
NCE e IM - UFRJ
Relações 47
Composição de Relações Nebulosas
RS 
 y [  R ( x, y)   S ( x, y)]
X Y
  max
  min ou
  produto
 A operação ° é similar à uma
multiplicação de matrizes
@2001 Adriano Cruz
NCE e IM - UFRJ
Relações 48
Exemplo de Composição Nebulosa
x1
x2
1.0
0.8
0.9
0.9
y1
z1
0.7
y2
z2
0.8
x3
0.8
1.0
x4
@2001 Adriano Cruz
y3
z3
R  X Y
S Y Z
NCE e IM - UFRJ
Relações 49
Exemplo de Composição
1 0.8 0 
0 0.9 0 

R
0 0 0.8
0 0 1.0 


0.9 0 0 
S   0 0 0.8


0.7 0 0 
 R ( x1 , z1 )  [(1  0.9)  (0.8  0)  (0  0.7)]
0.9  0  0
 000
RS  
0  0  0.7
0  0  0.7

@2001 Adriano Cruz
0  0  0 0  0.8  0
0  0  0 0  0.8  0

000 000 

000 000 
NCE e IM - UFRJ
Relações 50
Exemplo de Composição
0.9
z1
x1
0.8
x2
0.8
z2
0.7
x3
z3
0.9
0
RS  
 0. 7
 0. 7

0 0.8
0 0.8

0 0

0 0
0.7
x4
@2001 Adriano Cruz
NCE e IM - UFRJ
Relações 51
Relação de Implicação





If x is A then y is B
Esta regra possui uma relação de
implicação R(x,y)
Assuma que x is A’, queremos
descobrir y is B’
B’= A’  R(x,y)
B’ (y)=x[A’(x) R(x,y)]
@2001 Adriano Cruz
NCE e IM - UFRJ
Relações 52
Atribuição de Valores





Produto cartesiano
Expressões matemáticas y=f(x)
Regras linguísticas
Classificação
Métodos de similaridades de dados
@2001 Adriano Cruz
NCE e IM - UFRJ
Relações 53