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
Modelos matemáticos de fenômenos da natureza
podem ser divididos em três grandes categorias:
Estruturas de Ordem
<C, R>
Estruturas Algébricas
<C, Op>
Estruturas Topológicas (Geometria, Análise)
<C, P(C)>
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.
‫‫‬Notação: casado-com(Maria, José),
‫(‫‬Maria, casado-com, José)
‫‫‬mora-em(Maria, Campina Grande)
‫(‫‬Maria, mora-em, Campina Grande)
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-vários se algum primeiro
elemento s aparece mais de uma vez.
 Ex.:  = {(7,4), (2,5), (2,3)}
  é uma relação vários-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 vários-para-vários 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)}
Definições fracas
  é uma relação um-para-um se se cada primeiro
elemento s e cada segundo elemento t aparecem no
máximo uma vez na relação
  é uma relação um-para-vários se algum primeiro
elemento s pode aparecer mais de uma vez.
  é uma relação vários-para-um se algum segundo
elemento t pode fazer par com mais de um primeiro
elemento s..
  é uma relação vários-para-vários se é um-paravários e vários-para-um.
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 s  B, então podemos aplicar as
operações de conjuntos à  e s resultando em novos
subconjuntos de S2, isto é, em novas relações
binárias:
• x (  s) y  x  y ou x s y.
• x (  s) y  x  y e x s y.
• x ’ y  não x  y.
Exercícios
1. Sejam  e s duas relações binárias em S={1,2,3,4,5}
definidas por:
x  y  x = y. e x s y  x < y. Encontre:
a.   s
b. ’
2. Analise as relações
c. s’
pai-de(PESSOA,PESSOA),
d.   s
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.
Exemplos
Seja S = P(N) e seja A  B  A  B. Então:
•  é reflexiva.
•  é transitiva.
•  é anti-simétrica.
Seja S = N os naturais, e x  y  o resto da divisão de
x e y por 10 é o mesmo.
•  é 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, ou seja
 ’ com P e   ’ vale *  ’
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 .
• E o fecho anti-simétrico??
Relações de Ordem
Ordem Parcial
• Uma relação binária em um conjunto S que seja
reflexiva, anti-simétrica e transitiva é dita ser uma
relação de ordem parcial (ordenação parcial) em S.
• Exs.:
- xyxy
- ABAB
- x  y  x divide y
- x  y  x = y2
(em N)
(em P(N))
(em N)
(em {0,1}).
Ordem Parcial
 Se  é uma ordenação parcial em S, então o par (S, ) é
chamado de um conjunto parcialmente ordenado (POSET).
Obs.: denotaremos por (S,) qualquer conjunto parcialmente
ordenado (poset).
• Seja (S, ) um poset e seja A  S. Então,  é um conjunto de
pares ordenados de S, alguns dos quais podem ser pares
ordenados de A. O conjunto formado pelos pares ordenados de
A que pertencem a  é dito ser a restrição de  à A (notação |A
e constitui uma ordenação parcial em A.
• Exemplo: (N, x divide y) é um poset.
• Então, ({1,2,3,6,12,18}, x divide y) também é um poset.
Ordem Parcial
 Notação visual de um POSET:
• Exemplo: ({1,2,3,6,12,18}, x divide y)
12
18
6
2
3
1
Predecessor e Sucessor
 Seja (S,) um poset. Se x  y, temos duas
possibilidades:
x = y ou x  y. Se x  y e x  y,
denotamos por x < y e dizemos que x é um
predecessor de y ou que y é um sucessor de x.
 Um dado y pode ter diversos predecessores mas,
se x < y e não há z tal que x < z < y, então dizemos
que x é um predecessor imediato de y.
 Exercício: Considere a relação “x divide y” em
{1,2,3,6,12,18}:
a. Escreva os pares ordenados desta relação;
b. Escreva todos os predecessores de 6;
c. Escreva todos os predecessores imediatos de 6.
Exemplo
Considere o conjunto P({1,2}) e a relação de inclusão
em conjuntos (). Já sabemos que (P({1,2}), ) é um
poset. O conjunto e seu grafo são mostrados abaixo:
P({1,2}) = {, {1}, {2}, {1,2}}
{1,2}
{1}
{2}

Grafo de um Poset
• Se s é finito, então podemos descrever um poset
(S, ) visualmente através de um grafo (Diagrama de
Hasse): cada elemento de S é representado por um
ponto (nó, nodo ou vértice); se x é um predecessor
imediato de y, então o nó de y é desenhado acima
do nó de x e os dois nós são ligados por uma linha.
• (P({1,2}), ):
{1,2}
{1}
{2}

Grafo de um Poset
• Exemplo: Diagrama de Hasse dos divisores de 60
Posets especiais
Uma árvore é um poset (S, ) em que
• existe um elemento r S que é predecessor de
todos outros, isto é para todo s  S temos r  d,
(é chamado de raiz da árvore)
• todo elemento de S, exceto a raiz, possui um
único predecessor imediato.
.
Posets especiais
Dado um poset (S, ) e dois elementos r,s  S,
Definimos t=sup(r,s)‫‫‬como‫‫‬o‫‘‫‬menor’‫‫‬elemento‫‫‬t‫‫‬tal‫‫‬que‫‫‬
r  t e s  t. Análogamente definimos q = inf(r,s)
Escrevemos t = r+s e q = r.s.
Note que nem todo poset possui r+s e r.s
DEFINIÇÃO: Um reticulado é um poset (S, )
em que para quaisquer r,s  S, existe um (único)
sup(r,s) e um único inf(r,s).
•Dado um reticulado finito (S, ), defina sup(S) e inf(S)
Exercício
1. Desenhe o grafo da relação “x divide y” em
{1,2,3,6,12,18}.
Obs. Podemos reconstruir o conjunto de pares
ordenados da relação a partir do grafo.
2. Dado abaixo o grafo de uma ordenação parcial  em
um conjunto S = {a,b,c,d,e,f}, descreva a relação :
e
b
c
a
d
Exercícios
1. Mostre que para todo conjunto S, P(S) é um
reticulado.
2. Encontre
1. Para quaisquer A,B  P(S), sup(A,B) e inf(A,B)
2. sup(P(S)) e inf(P(S)).
2. Um reticulado pode ser uma árvore? Porque?
Mínimo/Máximo e Minimal/Maximal
 Seja (S, ) um conjunto parcialmente ordenado. Se
houver um x S tal que x  y para todo y  S, então,
x é um elemento mínimo do conjunto.
Exercício: mostre que um elemento mínimo, se
houver, é único.
 Seja (S, ) um poset. Um elemento y  S é dito ser
minimal se não houver outro x  S tal que x  y.
Mínimo/Máximo e Minimal/Maximal
Obs.:
• O elemento mínimo (máximo) é sempre minimal
(maximal) mas a recíproca não é verdadeira.
Exercício:
• Mostre que um reticulado tem um único elemento minimal
(o mínimo) e um único maximal (o máximo).
Questão:
• Um poset que tem um elemento mínimo e um
elemento máximo é um reticulado?
Exercícios
1. Desenhe o grafo de um poset com 4 elementos,
2 elementos minimais, nenhum elemento
mínimo, 2 elementos maximais e nenhum
elemento máximo.
2. Desenhe o grafo dos posets abaixo e identifique
quais são árvores ou reticulados:
a. S = {1,2,3,5,6,10,15,30} e x  y  x divide y.
b. S = P({1,2,3}) e A  B  A  B.
c. S = {a,b,c,d} e  = {(a,a), (b,b), (c,c), (d,d),
(a,b), (a,c)}
Ordem Total
 Uma ordenação parcial na qual todo elemento do
conjunto está relacionado com todos os demais
elementos é chamado de cadeia (ordenação total).
 em outras palavras, (S, ) é uma ordem total se para
todo (x,y), vale, ou x  y ou y  x.
• Obs.: o grafo de uma ordenação total tem a forma de
uma linha.
• Exemplo: a relação “” em N é uma ordem total.
Exercícios
1. Analise os conjuntos totalmente ordenados
quanto aos conceitos de árvore, reticulado,
mínimo, minimal, etc.
Relação de Equivalência
 Uma relação binária em um conjunto S que seja
reflexiva, simétrica e transitiva é chamada de uma
relação de equivalência em S.
 Exs.:
1. x  y  x + y é par
(em N)
2. x  y  x = y2
(em {0,1})
3. x  y  x senta na mesma coluna que y
(em sala)
4.  = {(1,1),(2,2),(3,3),(1,2),(2,1)}
(em{1,2,3})
Partição
Seja  a relação em S definida por:
xy  x senta na mesma coluna que y (S = alunos na sala)
 particiona o conjunto S em subconjuntos de forma que
todo aluno da classe pertence a um, e apenas um,
subconjunto.
 Uma partição de um conjunto S é uma coleção de
subconjuntos disjuntos não-vazios de S cuja união resulta
em S.
Os subconjuntos que formam a partição (chamados de
classes de equivalência) são formados pelos elementos
de S que se relacionam.
Classe de Equivalência
 Seja  uma relação de equivalência em S e x um
elemento de S (x S). Denotamos por [x] o conjunto
de todos os elementos de S que se relacionam com
x e chamamos esse conjunto de classe de
equivalência de x.
Assim, [x] = { y : y S e x  y}.
Exemplo: No caso da relação “x senta na mesma
coluna que y”, suponha que João, Pedro e Maria
sentam todos na coluna 3. Então:
[João] = [Pedro] = [Maria] = {João, Pedro, Maria}.
Relação de Equivalência
• Teorema: Seja  uma relação de equivalência em S. Então, as
classes de equivalência distintas de S formam uma partição S,
ou seja, (1) a união das classes resulta em S e (2) classes
distintas são disjuntas.
• Prova: Seja UxS[x]  união de todas as classes de equivalência
de S.
• 1. UxS[x] = S
- UxS[x]  S. Cada classe [x] é um subconjunto de S.
Portanto, UxS[x] também é um subconjunto de S.
- S  UxS[x]. Seja x S . Como xx (reflexiva). temos x  [x].
Portanto, como x é qualquer, todo elemento de S pertence a
alguma classe de equivalência e, portanto, pertence à união
das classes.
Relação de Equivalência
2. Se [x]  [z], então [x]  [z] = .
Vamos mostrar por contradição.
Vamos assumir que [x]  [z]  .
Se [x]  [z]  , então existe yS tal que y [x]  [z]:
- y [x]  [z]
- y [x] e y [z]
- xy e zy
- xy e yz
- xz
• O que nos permite dizer que [x] = [z], o que contradiz
a premissa [x]  [z].
•
•
•
•
Relação de Equivalência
• Corolário: Uma relação de equivalência em um
conjunto S determina uma partição de S e uma
partição de S determina uma relação de
equivalência.
• Prova:
• Do teorema anterior e do fato de que a relação
xy  “x está no mesmo subconjunto da partição
que y” é uma relação de equivalência.
• Obs.: O particionamento de um conjunto em classes
de equivalência é útil porque freqüentemente é
conveniente tratar as classes como entidades.
Exemplo
Seja S = { a/b : a, b Z e b  0}, ou seja, o conjunto de todas as
frações.
 Duas frações a/b e c/d são ditas serem equivalentes (a/b  c/d)
se, e somente se, ad = bc, ou seja:
a/b  c/d  ad = bc
• A relação  é uma relação de equivalência.(verificar).
• Algumas classes de equivalência de  :
• [1/2] = {..., -3/-6, -2/-4, -1/-2, 1/2, 2/4, 3/6,...}
• [3/10]= {..., -9/-30, -6/-20, -3/-10, 3/10, 6/20, 9/30,...}
• Obs.: O conjunto Q dos números racionais pode ser visto como
o conjunto de todas as classes de equivalência de S por .
Exercício
Seja S = N os números naturais e a partição:
 N = P  IP (em que P são os números pares e IP os números
ímpares)
• Defina uma relação de equivalência  determinada por esta
partição.
1. Dadas as funções f(x)=x2+1 e g(x) = cos(2x). O que seria a classe
de equivalência [] para cada uma dessas funções.
2. Se R é o conjunto dos números reais, descreva as partições de S
criadas por  sob f(x) e sob g(x).
Aritmética Modular
Exemplo: Seja Z o conjunto dos inteiros e seja 3 a relação
congruência módulo 3 em Z definida da seguinte forma:
•
x 3 y  x-y = k.3, para algum k Z . ( x  y (mod 3) )
•
Essa relação é uma relação de equivalência:
1. x  x (mod 3)  x-x = 3.0 (k=0)
2. Se x  y (mod 3) então y  x (mod 3).
1. x-y=k.3, para algum k
2. y-x = -k.3
3. y-x = (-k).3
4. y-x = m.3  y  x (mod 3).
3. Se x  y (mod 3) e y  z (mod 3) então x  z (mod 3).
Aritmética Modular
 Seja Z o conjunto dos inteiros e seja n  Z+. Então, a relação
x  y (mod n)  x-y = k.n, para algum k Z, é uma relação de
equivalência.
•
•
•
•
•
Obs.: Toda máquina tem um limite no tamanho dos inteiros que
ela pode armazenar que depende do número fixo de bits que
ela pode armazenar em uma posição de memória.
Suponha que n-1 é o maior inteiro que pode ser armazenado e
que x e y são inteiros tais que 0xn-1 e 0yn-1.
O que acontece se for solicitado a soma x+y e ela exceder o
limite n-1?
R.: ela não pode ser armazenada.
O que fazer?
Aritmética Modular
•
•
•
•
•
•
Realizar a adição módulo n e armazenar o resto r da divisão
de x+y por n.
Se x+y > n-1, então podemos escrever:
• x+y = q.n +r,
0  r < n.
Esta equação pode ser escrita como:
• (x+y) – r = q.n
Ou seja, (x+y) – r é um múltiplo de n, e assim, pela definição
acima:
• x+y  r (mod n)
Isto quer dizer que r pode ser diferente de x+y, mas está na
mesma classe de equivalência [x+y] e, como 0  r  n, está na
faixa dos inteiros que podem ser armazenados.
Portanto, todo número inteiro z em uma base n pode ser
representado como:
– z = q.n + r, para algum 0  r < n. NOTAÇÃO: zn = (r,q)
Adição e Multiplicação Modular
 Seja Zn = {0, 1, 2, ..., n-1}. A adição módulo n,
denotada por +n em Z é definida por x +ny = r, onde r
é o resto da divisão de x+y por n.
• Exemplo: 1 +53 = 4
•
3 +54 = 2
 A multiplicação módulo n, denotada por n em Z é
definida por x  ny = r, onde r é o resto da divisão de
x . y por n.
• Exemplo: 2  53 = 1
•
4  54 = 1
ou seja 65 = (1,1)
ou seja 165 = (1,3)
Exercício
Complete as tabelas abaixo para definir +
notação (r,q):
+5
0
1
2
0
1
3
4
 5
0
1
5
e
2
 5
3
na
4
0
(3,0)
1
2
2
3
3
4
4
(2,1)