Matemática Discreta - Parte V relações

1. Módulo 4:
Relações
•UNIVERSIDADE FEDERAL DE CAMPINA GRANDE
•CENTRO DE ENGENHARIA ELÉTRICA E INFORMÁTICA
•DEPARTAMENTO DE SISTEMAS E COMPUTAÇÃO
•Professor Ulrich Schiel

2. Relações
Ao estudarmos conjuntos:
•propriedades de seus elementos
•relações entre elementos de conjuntos
•relações entre subconjuntos de um conjunto.

3. 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)>

4. 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 é mãe de José.
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é),
mora-em(Maria, Campina Grande)
(Maria, casado-com, José)
(Maria, mora-em, Campina Grande)

5. 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 = S
2

6. 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).

7. Relações Binárias
Definição de uma relação r Í S´T:
•com palavras
•pela enumeração dos pares ordenados que a
satisfazem.
•Por uma fórmula relacional
• Pela definição do conjunto r

Usaremos a notação xry ou r(x,y) para indicar que o par
ordenado (x,y) satisfaz ou pertence à relação r:
x ry Û (x,y) Î r.
Uma relação r Í S´T também é denotada por r(S,T)

8. Relações Binárias
•Exemplos. Sejam S = {1,2} e T = {2,3,4} :
–descrição: x r y são todos pares cuja soma é
ímpar.
–x r y Û x+y = 2n+1, com n Î N
–x r y = {(1,2), (1,4), (2,3)}
–r = {(x,y) | x Î S e y ÎT e x+y é ímpar}
Seja PESSOA um conjunto de pessoas, podemos
ter:
casado-com(PESSOA, PESSOA)

9. Relações Binárias
•Para cada uma das seguintes relações binárias r
em N´N, determine quais dos pares ordenados
apresentados pertencem à r:
a.x r y Û x = y+1(2,2), (2,3), (3,3), (3,2)
b.x r y Û x divide y(4,2), (2,4), (2,5), (2,6)
c.x r y Û x é ímpar(2,3), (3,3), (4,5), (5,6)
d.x r y Û x > y
2
(1,2), (2,1), (5,2), (5,4), (4,3)
e.x r y Û y é uma (a,b), (b,a), (b,i), (b,c), (o,o).
vogal após a letra x

10. Relações n-árias
→Dados os conjuntos S
1
, S
2
, ..., S
n
, uma relação n-ária
em S
1
´S
2
´...´S
n
é um subconjunto de S
1
´S
2
´...´S
n
.
Neste caso para uma relação r em S
1
´S
2
´...´S
n

escrevemos r(s
1
, s
2
, ...,s
n
) se s
1
, s
2
, ...,s
n
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)}
r(x,y,z) Û x=y=z r = {(2,2,2)}
r(x,y,z) Û x>y r = ??

11. Relações unárias
•Uma relação unária r em um conjunto S é um
subconjunto particular de S.
•Um elemento x de S satisfaz ou pertence a r 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 Îr Û x é par.
•Exemplo 2: Para o conjunto pessoa podemos ter a
relação unária maior-de-idade(PESSOA).

12. Relações em um conjunto S
®Uma relação binária em um conjunto S é um
subconjunto de S
2
= (SxS).
Ex.: x r y Û x£y em N
®Analogamente, uma relação n-ária em um conjunto
S é um subconjunto de S
n
.
®Ex.: (x,y,z) Îr Û x+y=z em N.

13. Tipos de relações
Dado uma relação r Í S´T
®r é uma relação um-para-um se cada primeiro elemento s
e cada segundo elemento t aparecem exatamente uma
vez na relação.
®Formalmente:
®(i) todos elementos de S e T participam da relação
®(ii) se (s,t) Î r e (s,t’) Î r então t=t’
®(iii) se (s,t) Î r e (s’,t) Î r então s=s’
®Ex.: Sejam S = {2,5,7,9} e T = {1,3,4,5}
®r = {(2,4), (5,5), (7,3), (9,1)}

14. Definições
®r é uma relação um-para-vários se algum primeiro
elemento s aparece mais de uma vez.
®Ex.: r = {(7,4), (2,5), (2,3)}
®r é uma relação vários-para-um se algum segundo
elemento t fizer par com mais de um primeiro
elemento s..
®Ex.: r = {(2,4), (3,4), (5,2)}
®r é 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.: r = {(7,4), (2,5), (9,4), (2,3)}

15. Definições fracas
®r é uma relação um-para-um fraca se cada primeiro
elemento s e cada segundo elemento t aparecem no
máximo uma vez na relação
®r é uma relação um-para-vários fraca se algum primeiro
elemento s pode aparecer mais de uma vez.
®r é uma relação vários-para-um fraca se algum segundo
elemento t pode fazer par com mais de um primeiro
elemento s..
®r é uma relação vários-para-vários fraca se é um-para-
vários e vários-para-um.
EXERCÍCIO: Defina formalmente todas estas relações

16. Operações sobre relações
•Seja B o conjunto de todas as relações binárias em
um dado conjunto S:
B = P(SxS) = {r: r é uma relação binária em S}
•Isto é, se r Í S
2
, então r Î B.
•Assim, se r e s Î B, então podemos aplicar as
operações de conjuntos a r e s resultando em novos
subconjuntos de S
2
, isto é, em novas relações
binárias:
•x (r È s) y Û x r y ou x s y.
•x (r Ç s) y Û x r y e x s y.
•x r’ y Û não x r y.

17. Exercícios
1. Sejam r e s duas relações binárias em S={1,2,3,4,5}
definidas por:
x r y Û x = y+1. e x s y Û x < y+1. Encontre:
a. r e s
b.r È s
c. r’
d. s’
e. r Ç s
f. r È r’
2. Analise as relações
pai-de(PESSOA,PESSOA),
casado-com(PESSOA, PESSOA) e
trabalha-em(PESSOA, EMPRESA)
Quanto às características
um-para-um forte/fraca,
um-para-muitos forte/fraca, etc.)

18. Propriedades das relações
Seja r uma relação binária em S
2
.
®r é reflexiva quando
xrx para todo x Î S.
®r é simétrica quando
xry se, e somente se yrx para todo x e y Î S.
®r é transitiva quando,
xry e yrz implica xrz para todo x, y e z Î S.
®r é anti-simétrica quando
xry e yrx implica x = y para todo x e y Î S.

19. Exemplos
Seja S = P(N) e seja A r B Û A Í B. Então:
r é reflexiva.
r é transitiva.
r é anti-simétrica.
Seja S = N os naturais, e x r y Û o resto da divisão de
x e y por 10 é o mesmo.
• r é reflexiva.
• r é transitiva.
• r é simétrica

20. Fecho de uma relação
Se uma relação r em um conjunto S não tem uma
certa propriedade, podemos tentar estender r a fim
de obter uma relação r* em S que tenha a
propriedade.
®Uma relação binária r* em um conjunto S é dita ser
o fecho de r em S relativo à propriedade P se:
1.r* tem a propriedade P;
2.r Í r* ;
3.r* é a ‘menor’ relação contendo r com a
propriedade P, ou seja
" r’ com P e r Í r’ vale r* Í r’

21. Fecho de uma relação
•Exemplo:
•Seja S = {1,2,3} e r = {(1,1), (1,2), (3,1), (2,3)}
•Então,
-o fecho reflexivo de r em S é:
r* = {(1,1), (1,2), (3,1), (2,3), (2,2), (3,3)}
-o fecho simétrico de r em S é:
r** = {(1,1), (1,2), (3,1), (2,3), (1,3), (2,1), (3,2)}
- o fecho transitivo de r em S é:
r**' = r È {(1,3), (3,2), (3,3)}
- o fecho transitivo do fecho simétrico r
**
em S é:
r**” = r
**
È {(3,2), (3,3), (2,2)}

22. Exercício
Seja S = {a,b,c,d} e
r = {(c,c), (a,c), (a,d), (b,d), (c,a)}
•Encontre os fechos reflexivo, simétrico e
transitivo de r.
•E o fecho anti-simétrico??
Não existe fecho anti-simétrico mas sim,
redução anti-simétrica

23. 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 r y Û x £ y(em N)
-A r B Û A Í B(em P(N))
-x r y Û x divide y(em N)
-x r y Û x = y
2
(em {0,1}).
-x r y Û x é uma subcadeia de y (no conjunto de
todas as cadeias de símbolos)

24. Ordem Parcial
®Se r é uma relação de ordem parcial em S, então o par (S, r) é
chamado de um conjunto parcialmente ordenado (POSET).
Obs.: Notação: (S,£)
•Seja (S, £) um poset e seja A Í S.
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.

25. Grafo de um Poset
•Se S é finito, então o POSET (S, £) pode ser
representado visualmente através de um grafo
(Diagrama de Hasse): A ordem é dada pela posição
vertical do vértice.
Exemplo: (P({1,2}), Í)= {Æ, {1}, {2}, {1,2}}:
{1}
{1,2}
{2}
Æ

26. Ordem Parcial
®Notação visual de um POSET (Diagrama de
HASSE):
•Exemplo: ({1,2,3,6,12,18}, x divide y)
1
2 3
6
12 18

27. Grafo de um Poset
•Exemplo: Diagrama de Hasse dos divisores de 60

28. Predecessor e Sucessor
®Seja (S,£) um poset e x £ y,
®Se x £ y e x ¹ y, então x é um predecessor de y ou
y é um sucessor de x (notação x < y ).
®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.

29. Mínimo/Máximo e Minimal/Maximal
®Seja (S, £) um POSET. Um elemento y Î S é dito ser
minimal se não houver outro x Î S tal que x £ y.
® ou seja, y não tem predecessores
®Seja (S, £) um POSET. Se houver um x ÎS tal que x
£ y para todo y Î S, então, x é um elemento mínimo
do conjunto.
Obs.1: um elemento mínimo, se houver, é único.
Obs.2: o mínimo é minimal
Obs.3: Um POSET que possuir um único elemento
minimal, este será o elemento mínimo.
® Analogamente define-se elemento maximal e
elemento máximo.

30. Posets especiais
Uma árvore com raiz é um poset (S, £) que
• tem um elemento mínimo, chamado de raiz da árvore.
• todo elemento de S, exceto a raiz, possui um
único predecessor imediato.
EXEMPLO:
.
b
c
a
d
e

31. 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. Analogamente define-se q = inf(r,s)
Escrevemos t = r+s e q = r.s.
Note que em um poset nem sempre existem r+s e r.s
Uma árvore sempre terá r.s para todos r e s em S
Uma árvore nunca terá r+s para r ¹ s.

32. Posets especiais
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, £), definimos
• sup(S) o elemento máximo de S e
•inf(S) o elemento mínimo de S
EXEMPLO:

33. Exercícios
• Mostre que um reticulado finito 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 sempre é um reticulado?

34. Exercício
1.Desenhe o grafo da relação “x divide y” em
{1,2,3,6,12,18}.
Obs. Podemos reconstruir o POSET da relação a
partir do grafo.
1.Seja o grafo de uma ordenação parcial £ em um
conjunto S = {a,b,c,d,e},
1.analise a relação £
2.Existem sup(S) e inf(S)?
b
c
a
d
e

35. 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)).
3.Um reticulado pode ser uma árvore? Porque?

36. Ordem Total
®Uma ordem parcial na qual todo elementos estão
relacionados entre si é chamado de cadeia (ordem
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 ordem total tem a forma de
uma linha.
•Exemplo: a relação “£” em N é uma ordem total.

37. Exercícios
1.Analise os conjuntos totalmente ordenados
quanto aos conceitos de árvore, reticulado,
mínimo, minimal, etc.

38. Exercícios
1.Desenhe o grafo de um POSET tal que
1.Tenha 2 elementos minimais e um elemento máximo.
2.Que não seja uma árvore.
2.Desenhe o grafo dos POSETs abaixo e identifique quais
são árvores ou reticulados:
1.S = {1,2,3,5,6,10,15,30} e x r y Û x divide y.
2.S = P({1,2,3}) e A r B Û A Í B.
3. Para S = {a,b,c,d} e r = {(a,a), (d,d), (a,b), (b,c), (a,d),
(c,d)}. encontre r’ o fecho simétrico de r e r” o fecho
transitivo de r’ .

39. 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 r y Û x + y é par (em N)
2.x r y Û x = y
2
(em {0,1})
3.x r y Û x senta na mesma coluna que y(em sala)
4.r = {(1,1),(2,2),(3,3),(1,2),(2,1)}(em{1,2,3})

40. Partição
Seja r a relação em S definida por:
xry Û x senta na mesma coluna que y (S = alunos na sala)
r 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.
Toda relação de equivalência em S determina uma
partição (cada parte é uma classe de equivalência).

41. Classe de Equivalência
®Seja r uma relação de equivalência em S e x um elemento
de S (x ÎS).
®[x] é o conjunto de todos os elementos de S que se
relacionam com x. É a classe de equivalência de x.
Assim, [x] = { y : y ÎS e x r 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}.

42. Relação de Equivalência
•Teorema: Seja r 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.

43. Relação de Equivalência
Prova: (1) a união das classes resulta em S e .
•Seja U
xÎS
[x] º união de todas as classes de
equivalência de S.
•1. U
xÎS
[x] = S
-U
xÎS
[x] Í S. Cada classe [x] é um subconjunto de
S. Portanto, U
xÎS
[x] também é um subconjunto de
S.
-S Í U
xÎS
[x]. Seja x ÎS . Como xrx (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.

44. Relação de Equivalência
•(2) classes distintas são disjuntas
•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]
-xry e zry
-xry e yrz
-xrz
•O que nos permite dizer que [x] = [z], o que contradiz
a premissa [x] ¹ [z].

45. 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
xry Û “x está no mesmo subconjunto da partição
que y” é uma relação de equivalência.

46. Exemplo
Seja S = { a/b : a, b ÎZ e b ¹ 0}, ou seja, o conjunto de
todas as frações de inteiros.
®Definimos uma relação » como sendo:
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 ».

47. Exercício
1. 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.
2. Dadas as funções f(x)=x
2
+1 e g(x) = cos(2x). O que
seria a classe de equivalência [p] para cada uma
dessas funções. (N.B. xry <=> f(x) = f(y)
Se R é o conjunto dos números reais, descreva as
partições de S criadas por r sob f(x) e sob g(x).

48. Exercício
cos(2* p) = 1
p
2
+1 = 10,8696
x
2
+1
cos(2*x)

49. Aritmética Finita ou Modular
É uma aritmética com um número finito de números
inteiros
0,1,2,3,4,..,n-1, n, n+1, n+2, n+(n-1), 2n,..
Com 0 » n » 2n ..., 1 » n+1 » n+2...
EXEMPLOS:
- O relógio
- O computador
- notação decimal

50. 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.REFLEXIVA: x º x (mod 3) Û x-x = 3.0 (k=0)
2.SIMÉTRICA: 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 = m.3 Û y º x (mod 3).
3.TRANSITIVA: Se x º y (mod 3) e y º z (mod 3) então x º z
(mod 3).

51. Aritmética Modular
®Seja Z o conjunto dos inteiros e seja n Î Z
+
.
® Então, a relação
x º
n
y (mod n) Û x-y = k.n, para algum k ÎZ,
é uma relação de equivalência.
•

52. Aritmética Modular
®APLICAÇÃO:.
•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?

53. 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 está na mesma classe de
equivalência [x+y] e, como 0 £ r £ n, está na
faixa dos inteiros que podem ser armazenados.

54. Aritmética Modular
•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: z
n
= (r,q)
Com isso podemos armazenar números
maiores que n, enquanto tivermos q < n

55. Adição e Multiplicação Modular
®Seja Z
n
= {0, 1, 2, ..., n-1}. A adição módulo n,
denotada por +
n
em Z é definida por x +
n
y = r,
onde r é o resto da divisão de x+y por n.
•Exemplo: 1 +
5
3 = 4 ou seja 4
5
= (4,0)
• 3 +
5
4 = 2 ou seja 7
5
= (2,1)

56. Adição e Multiplicação Modular
®A multiplicação módulo n, denotada por ·
n
em
Z é definida por x ·
n
y = r, onde r é o resto da
divisão de x . y por n.
•Exemplo: 2 ·
5
3 = 1 ou seja 6
5
= (1,1)
• 4 ·
5 4 = 1 ou seja 16
5 = (1,3)

57. Exercícios
1. Complete as tabelas abaixo para definir +
5
e ·
5
na notação (r,q):
+
5
01234
0
1
(3,0)
2
3
4
·
5
0 1 2 3 4
0
1
2
(3,1)
3
4
2. Considerando a população de uma cidade, as relações
mesmo-bairro(x,y) e mesma-rua(x,y) são duas relações de equivalência.
Mostre que a relação
mesmo-bairro(x,y) È mesma-rua(x,y) não é uma relação de
equivalência.
Sugestão: considere cada habitante como uma tripla (p:pessoa,b:bairro,r:rua)

58. Exercícios
1. Dadas as funções f(x)=x
2
+1 e g(x) = cos(2x). O que
seria a classe de equivalência [p] para cada uma
dessas funções.
2.Se R é o conjunto dos números reais, descreva as
partições de S criadas por r sob f(x) e sob g(x).
3.Defina a relação de equivalência que particiona os
números inteiros em pares e ímpares.