Relações
Relações
Ao estudarmos conjuntos, estamos
interessados em certas propriedades
de seus elementos ou em relações
entre conjuntos. Ou seja, queremos
analisar sua estrutura.
Relações Binárias
‫‫‬
Na vida real, quando dizemos que duas pessoas, Maria e José,
se relacionam, entendemos que Maria e José se distinguem dos
demais pares de pessoas por haver uma relação que eles
satisfazem ou verificam.
‫‫‬
Ex.Maria e José são casados.
‫‫‬
Maria e José são colegas de trabalho.
‫‫‬
Maria e José não se entendem.
‫ ‫‬Maria manda em José
‫‫‬
Em matemática é análogo: distinguimos determinados pares de
objetos dos demais porque seus elementos satisfazem alguma
relação que os elementos dos demais pares, em geral, não
satisfazem.
Relações Binárias
Dados dois conjuntos S e T
Uma relação R entre S e T é dada por
R  SxT
Uma relação binária R em S é dada
por
R  SxS = S2
Relações Binárias
Ex.: Sejam S= {1,2} e T = {2,3}
Temos que SxT = {(1,2), (1,3), (2,2), (2,3)}
• Relação de igualdade: os elementos do par são
iguais.
‫ ‫‬O único par do “universo” (SxT) que satisfaz essa
relação é (2,2),
• Relação menor do que: isto é, primeiro elemento do
par é menor do que o segundo.
‫ ‫‬Três pares se distinguem: (1,2), (1,3), (2,3).
Relações Binárias
Definição de uma relação   ST:
• com palavras
• pela enumeração dos pares ordenados que a
. satisfazem.
• Por uma fórmula relacional
• Pela definição do conjunto 
Usaremos a notação xy ou (x,y) para indicar que o par
ordenado (x,y) satisfaz ou pertence à relação :
x y  (x,y)  .
Uma relação   ST também é denotada por (ST)
Relações Binárias
Exemplos. Sejam S = {1,2} e T = {2,3,4} :
•
•
•
•
descrição: x  y  x+y é ímpar.
x  y  x+y = 2n+1, com n  N
x  y = {(1,2), (1,4), (2,3)}
 = {(x,y) | x  S e y T e x+y é ímpar}
Seja PESSOA um conjunto de pessoas, podemos
ter:
casado-com(PESSOA, PESSOA)
Relações Binárias
•
Para cada uma das seguintes relações binárias 
em NN, determine quais dos pares ordenados
apresentados pertencem à :
a. x  y  x = y+1
((2,2), (2,3), (3,3), (3,2)
b. x  y  x divide y
(2,4), (2,5), (2,6)
c. x  y  x é ímpar
(2,3), (3,4), (4,5), (5,6)
d. x  y  x > y2
(1,2), (2,1), (5,2), (5,4), (4,3))
Relações n-árias
→ Dados os conjuntos S1, S2, ..., Sn, uma relação n-ária
em S1S2...Sn é um subconjunto de S1S2...Sn.
Neste caso para uma relação  em S1S2...Sn
escrevemos (s1, s2, ...,sn) se s1, s2, ...,sn pertence à
relação.
→ Exemplo: A= {1,2}, B = {2}, C = {2,3}.
‫ ‫‬ABC = {(1,2,2), (1,2,3), (2,2,2), (2,2,3)}
‫ ‫‬(x,y,z)  x=y=z
 = {(2,2,2)}
‫ ‫‬(x,y,z)  x>y
 = ??
Relações unárias
• Uma relação unária  em um conjunto S é um
subconjunto particular de S.
• Um elemento x de S satisfaz ou pertence à  se, e
somente se, x pertence ao subconjunto que define a
relação.
• Exemplo 1: O conjunto dos números pares P
(subconjunto de N) é definido pela relação:
x   x é par.
• Exemplo 2: Para o conjunto pessoa podemos ter a
relação unária maior-de-idade(PESSOA).
Relações em um conjunto S
 Uma relação binária em um conjunto S é um
subconjunto de S2 = (SxS).
Ex.: x  y  xy em N
 Analogamente, uma relação n-ária em um conjunto
S é um subconjunto de Sn.
 Ex.: (x,y,z)   x+y=z em N.
Definições
Seja  uma relação binária em SxT. Então, 
consiste de um conjunto de pares ordenados da
forma (s,t).


 é uma relação um-para-um se cada primeiro
elemento s e cada segundo elemento t aparecem
exatamente uma vez na relação.
Formalmente: se (s,t)   e (s,t’)   então t=t’ e se
(s,t)   e (s’,t)   então s=s’

Ex.: Sejam S = {2,5,7,9} e T = {1,3,4,5}

 = {(2,4), (5,5), (7,3), (9,1}
Definições
  é uma relação um-para-muitos se algum primeiro
elemento s aparece mais de uma vez.
 Ex.:  = {(7,4), (2,5), (2,3)}
  é uma relação muitos-para-um se algum segundo
elemento t fizer par com mais de um primeiro
elemento s..
 Ex.:  = {(2,4), (3,4), (5,2)}
  é uma relação muitos-para-muitos se pelo menos
um s fizer par com mais de um t e pelo menos um t
fizer par com mais de um s..
 Ex.:  = {(7,4), (2,5), (9,4), (2,3)}
Operações sobre relações
• Seja B o conjunto de todas as relações binárias em
um dado conjunto S:
B = P(SxS) = {:  é uma relação binária em S}
• Isto é, se   B, então   S2 .
• Assim, se  e   B, então podemos aplicar as
operações de conjuntos à  e  resultando em novos
subconjuntos de S2, isto é, em novas relações
binárias:
• x (  ) y  x  y ou x y
• x (  ) y  x  y e x y
• x ’ y  não x  y.
Exercícios
1. Sejam  e  duas relações binárias em S={1,2,3,4,5}
definidas por:
x  y  x = y e x  y  x < y. Encontre:
a.   
b. ’
2. Analise as relações
c. ’
pai-de(PESSOA,PESSOA),
d.   
casado-com(PESSOA, PESSOA) e
trabalha-em(PESSOA,EMPRESA)
e.   ’
Quanto às características
um-para-um, um-para-muitos, etc.)
Propriedades das relações
Seja  uma relação binária em S.
  é reflexiva quando
xx para todo x  S.
  é simétrica quando
xy se, e somente se yx para todo x e y  S.
  é transitiva quando,
xy e yz implica xz para todo x, y e z  S.
  é anti-simétrica quando
xy e yx implica x = y para todo x e y  S.
Exemplo
Seja S = N os naturais, e x  y  x+y é par.

 é reflexiva.

 é transitiva.

 é simétrica
Fecho de uma relação
Se uma relação  em um conjunto S não tem uma
certa propriedade, podemos tentar estender  a fim
de obter uma relação * em S que tenha a
propriedade.
 Uma relação binária * em um conjunto S é dita ser
o fecho de uma relação  em S relativo à
propriedade P se:
1 * tem a propriedade P;
2   * ;
3 * é a ‘menor’ relação contendo  com a
propriedade P
Fecho de uma relação
Obs.: a nova relação * conterá todos os pares
ordenados que  contém mais os pares ordenados
adicionais necessários para que a propriedade
desejada se verifique. Portanto,   *.
• Exemplo:
• Seja S = {1,2,3} e  = {(1,1), (1,2), (1,3), (3,1), (2,3)}
• Então,
- o fecho reflexivo de  em S é:
* = {(1,1), (1,2), (1,3), (3,1), (2,3), (2,2), (3,3)}
- o fecho simétrico de  em S é:
* = {(1,1), (1,2), (1,3), (3,1), (2,3), (2,1), (3,2)}
Exercício
Seja S = {a,b,c,d} e
 = {(c,c), (a,c), (a,d), (b,d), (c,a)}
• Encontre os fechos reflexivo, simétrico e
transitivo de .