Buscar

EXERCICIOS ROSEN RELAÇÕES

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 3, do total de 33 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 6, do total de 33 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 9, do total de 33 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Prévia do material em texto

Exercícios Selecionados – seçoes 8.1 a 8.5 – Kenneth Rosen – 6ª edição (em inglês) 1/33 
Sumário 
SEÇÃO 8.1 RELAÇÕES ................................................................................................................ 1 
RESPOSTAS EXERCÍCIOS ÍMPARES ............................................................................................. 6 
SEÇÃO 8.3 – REPRESENTAÇÃO DE RELAÇÕES ............................................................................. 7 
RESPOSTAS EXERCÍCIOS ÍMPARES ........................................................................................... 11 
SEÇÃO 8.4 – FECHO DE RELAÇÕES ........................................................................................... 12 
RESPOSTAS EXERCÍCIOS ÍMPARES ........................................................................................... 15 
SEÇÃO 8.5 – RELAÇÕES DE EQUIVALÊNCIA .............................................................................. 16 
RESPOSTAS EXERCÍCIOS ÍMPARES ........................................................................................... 22 
 
 
SEÇÃO 8.1 RELAÇÕES 
 
1. Liste os pares ordenados na relação R de A = { 0, 1, 2, 3, 4 } em B = { 0, 1, 2, 3 }, onde 
(a,b ) ∈ R se, e só se 
 
O acrônimo gcd (greatest common divisor) é máximo divisor comum, e lcm (least 
common multiple) é mínimo múltiplo comum. 
2. Liste todos os pares ordenados da relação R = { ( a, b ) : a divide b } sobre o conjunto 
{1, 2, 3, 4, 5, 6} 
3. Para cada uma destas relações sobre o conjunto {1, 2, 3, 4} decida se é reflexiva, se é 
simétrica, se é antissimétrica, e se é transitiva. 
 
4. Determine se a relação R sobre o conjunto de todas as pessoas é reflexiva, simétrica, 
antissimétrica, e / ou transitiva, onde ( a, b ) ∈ R se, e somente se, 
 
(a) a é mais alto do que b . 
Exercícios Selecionados – seçoes 8.1 a 8.5 – Kenneth Rosen – 6ª edição (em inglês) 2/33 
(b) a e b nasceram no mesmo dia. 
(c) a tem o mesmo primeiro nome do que b. 
(d) a e b têm um avô comum. 
6. Determine se a relação R sobre o conjunto de números reais é reflexiva, simétrica, 
antissimétrica, e / ou transitiva, onde ( x, y ) ∈ R se, e somente se, 
 
7. Determine se a relação R sobre o conjunto de números inteiros é reflexiva, simétrica, 
antissimétrica, e / ou transitiva, onde ( x, y ) ∈ R se, e somente se, 
 
8. Dê um exemplo de uma relação em um conjunto que seja 
(a) simétrica e antissimétrica. 
(b) nem simétrica, nem antissimétrica. 
12. Que relações, daquelas mostradas nos exercícios 3, 4, e 6 acima são irreflexivas? 
13. Uma relação pode não ser reflexiva e não ser irreflexiva ao mesmo tempo. 
14. Expresse a declaração de que R é uma relação binária irreflexiva através de uma 
fórmula bem formada da lógica de predicados. 
15. Dê um exemplo de relação irreflexiva sobre o conjunto de todas as pessoas. 
19. Que relações nos exercícios 3, 4, e 6 são assimétricas? 
20. Uma relação assimétrica deve ser também antissimétrica? Uma relação 
antissimétrica deve ser uma relação assimétrica? Justifique suas respostas. 
21. Expresse a declaração de que R é uma relação binária assimétrica através de uma 
fórmula bem formada da lógica de predicados. 
22. Dê um exemplo de relação assimétrica sobre o conjunto de todas as pessoas. 
23. Quantas relações diferentes existem a partir de um conjunto com m elementos para 
um conjunto de n elementos? 
Nos exercícios 24 a 26, ache R-1 e R’ 
24. R = { ( a, b ) : a divide b }, sobre o conjunto de inteiros. 
Exercícios Selecionados – seçoes 8.1 a 8.5 – Kenneth Rosen – 6ª edição (em inglês) 3/33 
25. R = { ( a, b ) : a divide b }, sobre o conjunto de inteiros positivos. 
26. R é uma relação entre os Estados brasileiros , onde R = { ( a, b) : a faz fronteira com b} 
27. Suponha que f é uma função injetora de A em A. Seja R a relação definida por: 
R = { ( a, f( a ) ) : a ∈ A }. Qual é a relação inversa R-1 ? 
28. Sejam R1 = { ( 1, 2 ) , ( 2, 3 ) , ( 3, 4 ) } e 
R2 = { ( 1, 1 ), (1, 2), (2, 1), (2, 2), (2, 3), (2, 1), (3, 2) , (3, 3), (3, 4) } , 
relações de { 1, 2, 3 } em { 1, 2, 3, 4 } . Ache 
 
Os exercícios 32 e 33 lidam com estas relações binárias no conjunto dos reais R. 
 
 
36. Seja R a relação de paternidade no conjunto de todas as pessoas, ou seja, 
R = { ( a, b ) : a é pai de b }. 
Quando é que um par ordenado vai estar na relação composta R3 ? 
 
37. Seja R a relação no conjunto de pessoas com doutorado, onde ( a, b ) ∈ R se, e só se, a 
foi o orientador de b. 
Quando é que um par ordenado vai estar na relação composta R2 ? E em Rn , onde n é 
um inteiro positivo? 
Exercícios Selecionados – seçoes 8.1 a 8.5 – Kenneth Rosen – 6ª edição (em inglês) 4/33 
 
39. Sejam R1 = { ( a, b ) : a mod 3 = b mod 3 } e R2 = { ( a, b ) : a mod 4 = b mod 4 }, relações 
binárias no conjunto dos inteiros ℤ . Determine 
 
40. Liste de forma tabular as 16 relações binárias de { 0, 1 }. (dica: lembre das diversas 
operações binárias e suas tabelas verdade) 
41. Quantas das relações determinadas no exercício 40 contém o par (0,1)? 
42. Das 16 relações determinadas no exercício 40 informe: 
(a) Quais são as reflexivas ? 
(b) Quais são as irreflexivas? 
(c) Quais são as não reflexivas? 
(d) Quais são as simétricas? 
(e) Quais são as assimétricas? 
(f) Quais são as antissimétricas? 
(g) Quais são as transitivas? 
43. ( a ) Quantas relações binárias existem no conjunto { a, b, c, d }? 
 ( b ) Quantas destas contém o par ( a, a )? 
44. Seja S um conjunto com cardinalidade n e tal que a e b são dois de seus elementos. 
Quantas relações binárias em S existem tal que 
a) ( a, b ) pertence à relação; 
b) ( a, b ) não pertence à relação; 
c) Não existe par começado com a na relação. 
d) Existe pelo menos um par começado com a na relação. 
e) Não existe par começado com a na relação e também não existe par terminado 
com b na relação. 
f) Existe pelo menos um par começado com a na relação ou pelo menos um par 
terminado com b na relação 
45. Quantas relações binárias existem em um conjunto com n elementos tal que sejam 
(a) simétricas; 
(b) antissimétricas; 
(c) assimétricas; 
(d) irreflexivas; 
(e) reflexivas e simétricas; 
(f) nem reflexivas nem irreflexivas. 
 
Exercícios Selecionados – seçoes 8.1 a 8.5 – Kenneth Rosen – 6ª edição (em inglês) 5/33 
46. Quantas relações binárias transitivas existem em um conjunto com cardinalidade 
a) n = 1 ; b) n = 2; c) n = 3 
47. Prove que a argumentação seguinte é falsa: 
Seja R uma relação binária em um conjunto A, e R é simétrica e transitiva. Então R é 
reflexiva, pois pela simetria sempre que ( a, b ) ∈ R, também teremos ( b, a ) , e pela 
transitividade ( a, a ) ∈ R. Portanto R é reflexiva. 
48. Suponha que R e S são relações binárias reflexivas no conjunto A. Prove ou refute as 
proposições abaixo: 
 
49. Mostre que a relação binária R no conjunto A é simétrica se, e somente se, R = R-1 . 
50. Mostre que a relação binária R no conjunto A é assimétrica se, e somente se, R ∩ R-1 
é um subconjunto de S = { ( a, a ) : a ∈ A. 
51 Mostre que a relação binária R no conjunto A é reflexiva se, e somente se, R-1 é 
reflexiva. 
52 Mostre que a relação binária R no conjunto A é reflexiva se, e somente se, a relação 
complementar R’ é irreflexiva. 
53. Mostre que se a relação binária R no conjunto A é reflexiva e transitiva, então Rn= R 
para qualquer inteiro positivo n . 
54. Seja R uma relação binária em { 1, 2, 3, 4, 5 } onde 
{ (1, 1), (1,2), (1, 3), (2,3), (2, 4), (3,1), (3,1) , (3,4), (3,5), (4,2), (4,5), (5, 1), (5, 2), (5, 4) } ⊆ R 
Determine 
a) R2 ; b) R3 ; c) R4 ; d) R5 . 
55. Seja R uma relação reflexiva em A. Mostreque Rn é reflexiva para qualquer n ∈ ℕ+ 
56. Seja R uma relação simétrica em A. Mostre que Rn é simétrica para qualquer n ∈ ℕ+ 
57. Seja R uma relação irreflexiva em A. R2 é necessariamente irreflexiva? Justifique. 
 
 
Exercícios Selecionados – seçoes 8.1 a 8.5 – Kenneth Rosen – 6ª edição (em inglês) 6/33 
RESPOSTAS EXERCÍCIOS ÍMPARES 
 
 
 
 
Exercícios Selecionados – seçoes 8.1 a 8.5 – Kenneth Rosen – 6ª edição (em inglês) 7/33 
 
 
 
SEÇÃO 8.3 – REPRESENTAÇÃO DE RELAÇÕES 
 
1. Represente cada uma destas relações no conjunto { 1, 2, 3 } como uma matriz 
booleana onde ( a, b ) ∉ R ⟺ o elemento da a-ésima linha e b-ésima coluna é igual a 0. 
 
2. Repita o que fez no exercício anterior sobre as relações abaixo em {1,2,3,4} 
 
3. Supondo que as matrizes booleanas abaixo representam relações em {1,2,3}, escreva 
o conjunto de pares ordenados de cada uma. 
 
4. Faça o mesmo que o exercício anterior mas com relações sobre {1,2,3,4} 
Exercícios Selecionados – seçoes 8.1 a 8.5 – Kenneth Rosen – 6ª edição (em inglês) 8/33 
 
5. Dada uma matriz booleana representando uma relação R, como você pode 
determinar que a relação é irreflexiva? 
6. Dada uma matriz booleana representando uma relação R, como você pode 
determinar que a relação é assimétrica? 
7. Determine se as relações representadas pelas matrizes do exercício 3 são reflexivas, 
irreflexivas, simétricas, antissimétricas, e/ou transitivas. 
8. Determine se as relações representadas pelas matrizes do exercício 4 são reflexivas, 
irreflexivas, simétricas, antissimétricas, e/ou transitivas. 
9. Supondo que usei uma matriz booleana para representar uma relação R sobre 
{1,2,…, 100}, quantos elementos da matriz estão zeradas, no caso em que a relação R é o 
conjunto 
 
10. Idem ao exercício anterior, agora considerando R igual a 
 
11. Dada uma matriz booleana n × n representando uma relação binária R em {1,2,…,n}, 
apresente um algoritmo para obter a matriz que representa a relação complementar R’? 
12. Dada uma matriz booleana n × n representando uma relação binária R em {1,2,…,n}, 
apresente um algoritmo para obter a matriz que representa a relação inversa R-1? 
13. Seja R a relação representada pela matriz booleana 
Determine as matrizes booleanas que representam as relações 
( a ) R-1 (b) R’ ( c ) R ∘ R 
 
Exercícios Selecionados – seçoes 8.1 a 8.5 – Kenneth Rosen – 6ª edição (em inglês) 9/33 
14. Sejam R1 e R2 as relações sobre {1,2,3} representadas pelas matrizes booleanas 
 
Determine as matrizes booleanas que representam 
 
Onde ⊕ é um outro operador para a operação diferença simétrica (havíamos definido Δ). 
15. Seja R a relação representada pela matriz booleana 
 
Ache as matrizes booleanas que representam 
( a ) R2 ( b ) R3 ( c ) R4 
 
16. Seja R a relação sobre um conjunto A com n elementos. Se existem k elementos 
diferentes de 0 na matriz booleana representando R, quantos elementos existirão em 
uma matriz booleana representando a relação inversa R-1 ? 
17. Seja R a relação sobre um conjunto A com n elementos. Se existem k elementos 
diferentes de 0 na matriz booleana representando R, quantos elementos existirão em 
uma matriz booleana representando a relação complementar R’ ? 
18. Desenhe os grafos direcionados representando as relações do exercício 1. 
19. Desenhe os grafos direcionados representando as relações do exercício 2. 
20. Desenhe os grafos direcionados representando as relações do exercício 3. 
21. Desenhe os grafos direcionados representando as relações do exercício 4. 
22. Desenhe o grafo direcionado representando a relação abaixo 
 
Nos exercícios 23 a 28 liste os pares ordenados das relações representadas por cada 
grafo direcionado 
Exercícios Selecionados – seçoes 8.1 a 8.5 – Kenneth Rosen – 6ª edição (em inglês) 10/33 
 
 
29. Através de uma simples inspeção visual de um grafo, como podemos determinar se 
a relação representada pelo grafo é assimétrica? 
30. Através de uma simples inspeção visual de um grafo, como podemos determinar se 
a relação representada pelo grafo é irreflexiva? 
31. Determine se as relações representadas pelos grafos dos exercícios 23 a 25 são 
reflexivas, irreflexivas, simétricas, antissimétricas, e/ou transitivas. 
32. Determine se as relações representadas pelos grafos dos exercícios 26 a 28 são 
reflexivas, irreflexivas, simétricas, antissimétricas, e/ou transitivas. 
33. Seja R uma relação sobre um conjunto A, e G um grafo direcionado representando 
R. Como posso obter o grafo direcionado da relação inversa R-1 a partir do grafo G? 
34. Seja R uma relação sobre um conjunto A, e G um grafo direcionado representando 
R. Como posso obter o grafo direcionado da relação complementar R’ a partir do grafo 
G? 
35. Mostre que se MR é a matriz booleana representando R 
Exercícios Selecionados – seçoes 8.1 a 8.5 – Kenneth Rosen – 6ª edição (em inglês) 11/33 
 
RESPOSTAS EXERCÍCIOS ÍMPARES 
 
 
 
 
Exercícios Selecionados – seçoes 8.1 a 8.5 – Kenneth Rosen – 6ª edição (em inglês) 12/33 
 
 
 
 
SEÇÃO 8.4 – FECHO DE RELAÇÕES 
 
1. Seja R = { (0,1), (1,1), (1,2), (2,0),(2,2),(3,0) } uma relação sobre {0,1,2,3}. 
a) Ache o fecho reflexivo de R b) Ache o fecho simétrico de R 
 
2. Seja R = { ( a,b ) : a ≠ b } uma relação sobre o conjunto dos inteiros ℤ . 
a) Ache o fecho reflexivo de R b) Ache o fecho simétrico de R 
3. Seja R = { ( a,b ) : a é divisor de b } uma relação sobre o conjunto dos inteiros ℤ . 
a) Ache o fecho reflexivo de R b) Ache o fecho simétrico de R 
4. Suponha que você tem um grafo G representando uma relação R. Como se obtém o 
grafo representando o fecho reflexivo de R? 
 
Nos exercícios 5 até 7, desenhe o grafo que representa o fecho reflexivo das relações 
representadas pelos grafos direcionados mostrados. 
Exercícios Selecionados – seçoes 8.1 a 8.5 – Kenneth Rosen – 6ª edição (em inglês) 13/33 
 
8. Suponha que você tem um grafo G representando uma relação R. Como se obtém o 
grafo representando o fecho simétrico de R? 
9. Desenhe os grafos que representam os fechos simétricos das relações representadas 
pelos grafos direcionados nos exercícios 5 até 7. 
10. Qual é a menor relação que contém a relação R = { ( a,b ) ∈ ℕ+ × ℕ+ : a > b } e é 
reflexiva e simétrica? 
12. Suponha que R é uma relação binária em A , |A| = n, representada pela matriz 
booleana MR . Mostre que o fecho reflexivo de R é representado pela matriz MR ∨ I n , 
onde In é a matriz identidade . 
13. Suponha que R é uma relação binária em A , |A| = n, representada pela matriz 
booleana MR . Mostre que o fecho simétrico de R é representado pela matriz MR ∨ MRT, 
onde I MRT é a matriz transposta de MR . 
14. Mostre que se existe o fecho de uma relação R com relação a uma propriedade P, 
então este fecho é a interseção de todas as relações que contém R e têm a propriedade 
P. 
15. Quando é possível definir o fecho irreflexivo de uma relação R? (ou seja, uma 
relação que contém R e que está contida em todas as relações irreflexivas que contém 
R) 
19. Seja R = { (1,3), (2,4), (3,1), (3,5), (4,3),(5, 1), (5,2), (5,4 } uma relação em {1,2,3,4,5}. 
Determine: 
 
Exercícios Selecionados – seçoes 8.1 a 8.5 – Kenneth Rosen – 6ª edição (em inglês) 14/33 
 
21. Seja R a relação no conjunto de todos os estudantes, 
R = { ( a,b ) : a ≠ b e a cursa alguma disciplina com b} 
Determine: 
a) R2 b) R3 c) R* . 
22. Suponha que a relação R é reflexiva. Mostre que R* é reflexiva. 
23. Suponha que a relação R é simétrica. Mostre que R* é simétrica. 
24. Suponha que a relação R é irreflexiva. R* é necessariamente irreflexiva? Justifique.25. Use o algoritmo fechoTransitivo para achar os fechos transitivos das seguintes 
relações em {1,2,3,4} 
 
26. Use o algoritmo fechoTransitivo para achar os fechos transitivos das seguintes 
relações em { a, b, c, d, e } 
 
27. Use o algoritmo de Warshall para achar os fechos transitivos das relações do 
exercício 25. 
28. Use o algoritmo de Warshall para achar os fechos transitivos das relações do 
exercício 26 (troque { a, b, c, d, e }por {1,2,3,4,5}. 
29. Ache a menor relação contendo a relação { (1,2), (1,4), (3,3), (4,1) } que seja 
a) reflexiva e transitiva. 
b) simétrica e transitiva. 
c) reflexiva, simétrica e transitiva 
 
Exercícios Selecionados – seçoes 8.1 a 8.5 – Kenneth Rosen – 6ª edição (em inglês) 15/33 
RESPOSTAS EXERCÍCIOS ÍMPARES 
 
 
 
Exercícios Selecionados – seçoes 8.1 a 8.5 – Kenneth Rosen – 6ª edição (em inglês) 16/33 
 
 
 
 
SEÇÃO 8.5 – RELAÇÕES DE EQUIVALÊNCIA 
 
1. Quais destas relações em {0, 1, 2, 3} são relações de equivalência? Justifique 
 
 
 
Exercícios Selecionados – seçoes 8.1 a 8.5 – Kenneth Rosen – 6ª edição (em inglês) 17/33 
2. Quais relações no conjunto de todas as pessoas são de equivalência? Justifique. 
a) { ( a,b ) : a e b têm a mesma idade } 
b) { ( a,b ) : a e b têm os mesmos pais } 
c) { ( a,b ) : a e b têm pelo menos um genitor em comum } 
d) { ( a,b ) : a e b já se encontraram } 
e) { ( a,b ) : a e b falam uma língua em comum } 
3. Quais destas relações sobre o conjunto de todas as funções de ℤ em ℤ são relações de 
equivalência? Justifique. 
 
4. Defina 3 relações de equivalência no conjunto dos alunos inscritos em Estruturas 
Discretas. Determine as classes de equivalência de cada relação de equivalência. 
6. Defina 3 relações de equivalência no conjunto de disciplinas oferecidas no curso de 
BSI. Determine as classes de equivalência de cada relação de equivalência. 
7. Mostre que a relação de equivalência lógica no conjunto de todas as proposições é uma 
relação de equivalência. Quais são as classes de equivalência de FALSE e TRUE? 
8. Seja R a relação sobre todos os subconjuntos dos números reais ℝ tal que ( S, T ) ∈ R 
se, e somente se, S e T têm a mesma cardinalidade. Mostre que R é uma relação de 
equivalência. Quais são as classes de equivalência de { 1, 2, 3 } e do conjunto dos 
inteiros ℤ ? 
9. Suponha que A é um conjunto não vazio, e f é uma função com domínio A. Seja R a 
relação sobre A consistindo de todos os pares ordenados ( x,y ) tal que f( x ) = f( y ). 
a) Mostre que R é uma relação de equivalência de R. 
b) Quais são as classes de equivalência de R? 
10. Suponha que A é um conjunto não vazio, e R é uma relação de equivalência sobre 
A. Mostre que existe uma função f com domínio em A e tal que ( x, y ) ∈ R se, e somente 
se, f( x ) = f( y ). 
15. Seja R a relação sobre o conjunto de pares ordenados de inteiros positivos (isto é, 
com R ⊆ ℤ2 × ℤ2 ), tal que ( ( a,b ) , ( c,d ) ) ∈ R se, e somente se, a + d = b + c. 
Mostre que a relação R é uma relação de equivalência. 
16. Seja R a relação sobre o conjunto de pares ordenados de inteiros positivos (isto é, 
com R ⊆ ℤ2 × ℤ2 ), tal que ( ( a,b ) , ( c,d ) ) ∈ R se, e somente se, a d = b c. 
Mostre que a relação R é uma relação de equivalência. 
Exercícios Selecionados – seçoes 8.1 a 8.5 – Kenneth Rosen – 6ª edição (em inglês) 18/33 
17. 
a) Considere a relação R = { ( f, g ) ℱ × ℱ : ∀ x ∈ ℝ , f’( x ) = g’( x ) } , onde ℱ é o 
conjunto de todas as funções diferenciáveis dos reais sobre os reais. Mostre que 
R é uma relação de equivalência. 
b) Quais funções estão na mesma classe de equivalência da função f( x ) = x2 ? 
18. 
a) Seja n um inteiro positivo. 
Considere a relação R = { ( f, g ) 𝒫 × 𝒫 : ∀ x ∈ ℝ , f (n)( x ) = g (n) ( x ) } , onde 𝒫 é o 
conjunto de todos os polinômios com coeficientes em ℝ ( números reais), e o 
índice ( n ) representa a n-ésima derivada da função. Mostre que R é uma relação 
de equivalência. 
b) Quais funções estão na mesma classe de equivalência da função f( x ) = x4 , 
quando n = 3 ? 
Nos exercícios 21 até 23, determine se as relações representadas na forma de grafos 
direcionados são relações de equivalência (só há um grafo em cada exercício). 
 
24. Determine se as relações representadas pelas matrizes booleanas são relações de 
equivalência. 
 
35. Qual é a classe de congruência módulo 5 (denotada por [ n ]5 ), quando n é 
a) 2 b) 3 c) 6 d) -3 
Exercícios Selecionados – seçoes 8.1 a 8.5 – Kenneth Rosen – 6ª edição (em inglês) 19/33 
36. Qual é a classe de congruência módulo 4 (denotada por [ n ]4 ), quando n é 
a) 2 b) 3 c) 6 d) 8 
41. Quais destas coleções de conjuntos são partições de { 1,2,3,4,5,6 }? 
 
41. Quais destas coleções de conjuntos são partições de { -3, -2, -1, 0, 1, 2, 3 }? 
 
44. Quais destas coleções de conjuntos são partições do conjunto de inteiros ? 
a) { x ∈ ℤ : x é par }, { x ∈ ℤ : x é ímpar } 
b) { x ∈ ℤ : x > 0 },{ x ∈ ℤ : x < 0 } 
c) [ 0 ]3 , [ 1 ]3 , e [ 2 ]3 . 
d) { x ∈ ℤ : x < -100 }, { x ∈ ℤ : x > 100 }, { x ∈ ℤ : |x | < 100 } 
e) { x ∈ ℤ : x mod 3 ≠ 0 }, { x ∈ ℤ : x é par }, [ 3 ]6 . 
 
44. Quais destas coleções de conjuntos são partições do conjunto ℤ × ℤ ? 
a) { (x,y) ∈ ℤ×ℤ: x é ímpar ou y é ímpar }, { (x,y) ∈ ℤ×ℤ: x é par }, { (x,y) ∈ ℤ×ℤ: y é 
par } 
b) { (x,y) ∈ ℤ × ℤ: x é ímpar e y é ímpar }, { (x,y) ∈ ℤ × ℤ: ou x é ímpar, ou y é 
ímpar, mas não ambos }, { (x,y) ∈ ℤ × ℤ: x é par e y é par } 
c) { (x,y) ∈ ℤ × ℤ: x > 0 }, { (x,y) ∈ ℤ × ℤ: y > 0}, { (x,y) ∈ ℤ × ℤ: x < 0 e y < 0 }, 
d) { (x,y) ∈ ℤ×ℤ: 3\x e 3\y }, { (x,y) ∈ ℤ×ℤ: 3\x e 3 não é divisor de y }, { (x,y) ∈ 
ℤ×ℤ: 3 não é divisor de x e 3\ y }, { (x,y) ∈ ℤ × ℤ: 3 não é divisor nem de x, nem 
de y } 
e) { (x,y) ∈ ℤ × ℤ: x > 0 e y > 0 }, { (x,y) ∈ ℤ × ℤ: x > 0 e y ≤ 0 }, { (x,y) ∈ ℤ × ℤ: x ≤ 0 e 
y > 0 }; { (x,y) ∈ ℤ × ℤ: x ≤ 0 e y ≤ 0 } 
f) { (x,y) ∈ ℤ×ℤ: x ≠ 0 e y ≠ 0 }, { (x,y) ∈ ℤ×ℤ: x=0 e y≠ 0 }, { (x,y) ∈ ℤ×ℤ: x≠ 0 e y =0 } 
 
46. Quais destas coleções de conjuntos são partições do conjunto ℝ dos números reais? 
(a) { x ∈ ℝ : x < 0 } , { 0 } , { x ∈ ℝ : x > 0 } 
(b) { x ∈ ℝ : ∃ p ∈ ℤ ∃ q ∈ ℤ ( x = p/q ) }, { x ∈ ℝ : ∀ p ∈ ℤ ∀ q ∈ ℤ ( x ≠ p/q )} 
(c) a coleção de intervalos [ k , k+1], k ∈ ℤ . 
(d) a coleção de intervalos ( k , k+1), k ∈ ℤ . 
(e) a coleção de intervalos ( k , k+1], k ∈ ℤ . 
(f) a coleção de conjuntos Ax = { x + n : n ∈ ℤ }, x ∈ [0, 1) 
Exercícios Selecionados – seçoes 8.1 a 8.5 – Kenneth Rosen – 6ª edição (em inglês) 20/33 
47. Liste os pares ordenados das relações de equivalência produzidas pelas partições 
de { 0,1,2,3,4,5 } dadas abaixo 
 
48. Liste os pares ordenados das relações de equivalência produzidas pelas partições 
de { a,b,c,d,e,f,g } dadas abaixo 
 
49. Mostre que a partição dos inteiros formada pelas classes de congruência módulo 6 é 
um refinamento de uma partição dos inteiros formada pelas classes de congruência 
módulo 3. 
50. Mostre que a partição do conjunto de pessoas vivendo no Brasil formada pelos 
conjuntos de pessoas vivendo em cada município (incluindo distritos) é um 
refinamento da partição formada pelos conjuntos de pessoas vivendo em cada Estado 
da Federação. 
Preâmbulo dos Exercícios 52 e 53 
Seja n um inteiro positivo e S um conjunto de strings de 0’s e 1’s. Considere a relação 
Rn={ ( s, t ) ∈ S2 : ( s = t ) ∨ ( | s | ≥ n ∧ | t | ≥ n ∧ s[1… n] = t[1… n] ) }, onde s[1… n] 
representa o prefixo de s com comprimento n. 
Por exemplo, considerando n = 3, 
( 01 , 00 ) ∉ R3 , (0100, 0110 ) ∉ R3 , (1100000, 110111111111101) ∈ R3 . 
Note que nesta relação, qualquer string r com comprimento | r | < n só se relacionapor 
Rn com si mesma. 
Rn é uma relação de equivalência (verifique que ela de fato é reflexiva, simétrica e 
transitiva). 
52. Mostre que a partição de S formada pelas classes de equivalência definidas pela 
relação de equivalência R4 é um refinamento da partição formada pelas classes de 
equivalência definidas pela relação de equivalência R3 . 
53. Mostre que a partição do conjunto S de identificadores (nomes de variáveis) 
permitidos na linguagem C formada pelas classes de equivalência definidas pela 
relação de equivalência R31 é um refinamento da partição formada pelas classes de 
equivalência definidas pela relação de equivalência R8 . 
Exercícios Selecionados – seçoes 8.1 a 8.5 – Kenneth Rosen – 6ª edição (em inglês) 21/33 
( Compiladores das primerias versões de C consideravam identificadores iguais se os 
primeiros 8 caracteres eram iguais, enquanto que o Standard C considera dois 
identificadores iguais se têm seus primeiros 31 caracteres iguais). 
54. Suponha que R1 e R2 são relações de equivalência sobre um conjunto A. Sejam P1 e 
P2 partições de A definidas por R1 e R2 respectivamente. Mostre que 
R1 ⊆ R2 se, e somente se, P1 é um refinamento de P2 . 
55. Ache a menor relação de equivalência sobre o conjunto { a,b,c,d, e } contendo a 
relçaão { ( a,b ) , ( a,c ), ( d,e ) }. 
55. Suponha que R1 e R2 são relações de equivalência em um conjunto S. Determine se 
os seguintes conjuntos são relações de equivalência: 
a) R1 ∪ R2 b) R1 ∩ R2 c) R1 ⊕ R2 
57. A relação em ℝ dada por R = { ( x,y ) ∈ ℝ2 : x – y ∈ ℤ } é uma relação de equivalência 
(verifique!). Qual é a classe de equivalência que R define para 
a) 1 b) 0,5 
63. Se fizermos o fecho transitivo do fecho simétrico do fecho reflexivo de uma relação 
qualquer, nós obtemos uma relação de equivalência, necessariamente? Justifique. 
64. Se fizermos o fecho simétrico do fecho reflexivo do fecho transitivo de uma relação 
qualquer, nós obtemos uma relação de equivalência, necessariamente? Justifique. 
67. Construa um algoritmo que, para uma dada relação R, devolve a menor relação de 
equivalência contendo R 
68. Números de Bell – p( n ) 
Considere que p( n ) denota o número de relações de equivalência diferentes em um 
conjunto com n elementos. Porque uma partição sempre determina uma relação de 
equivalência, p( n ) também denota o número de partições do conjunto. Por 
conveniência, vamos supor que p( 0 ) = 1. 
a) Mostre que , onde C( a , b ) denota, como de 
costume, o total de combinações de a elementos em conjuntos de b elementos 
b) Calcule p( 10 ) 
 
Exercícios Selecionados – seçoes 8.1 a 8.5 – Kenneth Rosen – 6ª edição (em inglês) 22/33 
RESPOSTAS EXERCÍCIOS ÍMPARES 
 
 
 
 
 
Exercícios Selecionados – seçoes 8.1 a 8.5 – Kenneth Rosen – 6ª edição (em inglês) 23/33 
 
 
Exercícios Selecionados – seçoes 8.1 a 8.5 – Kenneth Rosen – 6ª edição (em inglês) 24/33 
 
 
 
Exercícios Selecionados – seçoes 8.1 a 8.5 – Kenneth Rosen – 6ª edição (em inglês) 25/33 
 
 
 
Exercícios Selecionados – seçoes 8.1 a 8.5 – Kenneth Rosen – 6ª edição (em inglês) 26/33 
 
SEÇÃO 8.6 – ORDENS PARCIAIS 
 
1.Quais destas relações em {0,1,2,3} são ordens parciais? Para as que não forem ordens 
parciais, justifique. 
 
2.Quais destas relações em {0,1,2,3} são ordens parciais? Para as que não forem ordens 
parciais, justifique. 
 
 
3. Verifique se ( S, R ) é um conjunto parcialmente ordenado, quando S é o conjunto de 
todas as pessoas e ( a, b ) ∈ R se, e só se, 
a) a é mais alto do que b 
b) a não é mais alto do que b. 
c) a = b ou a é um ancestral de b 
d) a e b têm um amigo em comum. 
4. Verifique se ( S, R ) é um conjunto parcialmente ordenado, quando S é o conjunto de 
todas as pessoas e ( a, b ) ∈ R se, e só se, 
a) a não é mais baixo do que b 
b) a pesa mais do que b. 
c) a = b ou a é um descendente de b 
d) a e b não têm um amigo em comum. 
5. Quais destes são c.p.o.? 
a) (ℤ , = ) , b) ( ℤ , ≠ ) c) ( ℤ , ≥ ) d) ( ℤ , não é divisor de ) 
6. Quais destes são c.p.o.? 
Exercícios Selecionados – seçoes 8.1 a 8.5 – Kenneth Rosen – 6ª edição (em inglês) 27/33 
a) ( ℝ , = ) b) ( ℝ , < ) c) ( ℝ , ≤ ) d) ( ℝ , ≠ ) 
7. Determine se as relações representadas por estas matrizes de zeros e uns são ordens 
parciais 
 
8. Determine se as relações representadas por estas matrizes de zeros e uns são ordens 
parciais 
 
 
Nos exercícios 9 a 11, determine se a relação representada pelo grafo direcionado é 
uma ordem parcial 
 
12. Mostre que se ( S, R ) é um c.p.o. então ( S, R-1 ) também é um c.p.o. (lembrando que 
R-1 é a relação inversa a R). 
O conjunto parcialmente ordenado ( S, R-1 ) é dito o dual de ( S, R ) 
13. Ache o dual de cada conjunto parcialmente ordenado 
 
14. Quais dos pares de elementos são comparáveis no c.p.o ( ℤ+ , / )? 
a \ b indica que a é divisor de b. 
a) 5, 15 b) 6, 9 c) 8, 16 d) 7,7 
Exercícios Selecionados – seçoes 8.1 a 8.5 – Kenneth Rosen – 6ª edição (em inglês) 28/33 
15. Ache dois elementos não comparáveis nos seguintes c.p.o.’s: 
a) ( 𝒫( {0,1,2} , ⊆ ), onde 𝒫 indica conjunto potência b) ( { 1,2,4,6,8 } , \ ) 
16. Com S = {1,2,3,4 }, e usando a ordem lexicográfica em S2 
(por exemplo (3, 1) ≼ (3, 4) )porque 3 = 3 e 1 ≤ 4) 
a) ache todos os pares R = { ( a,b ) ∈ S2 : ( a,b ) ≼ ( 2,3 ) ∧ ( a,b ) ≠ ( 2,3 ) } , 
b) ache todos os pares R = { ( a,b ) ∈ S2 : ¬ ( ( a,b ) ≼ ( 3,1 ) ) } 
c) desenhe o diagrama de Hasse para o c.p.o. ( S2 , ≼ ) 
17. Ache a ordem lexicográfica destas tuplas 
a) ( 1, 1, 2 ) , ( 1, 2 , 1 ) b) ( 0, 1, 2, 3 ) , ( 0, 1, 3, 2 ) c) ( 1,0,1,0,1) , ( 0,1,1,1,0) 
18. Ache a ordenação lexicográfica destas strings de letras minúsculas em inglês 
a) quack, quick, quicksilver, quicksand, quacking 
b) open, opener, opera, operand, opened 
c) zoo, zero, zoom, zoology, zoological 
19. Ache a ordenação lexicográfica das strings de bit 0, 01, 11, 001, 010, 011, 0001, 0101 
baseada na ordem 0 < 1. 
22. Desenhe o diagrama de Hasse para a divisibilidade no conjunto 
 
23. Desenhe o diagrama de Hasse para a divisibilidade no conjunto 
 
Nos exercícios de 25 a 27, liste todos os pares ordenados da ordem parcial indicadas 
pelos diagramas de Hasse 
 
 
Exercícios Selecionados – seçoes 8.1 a 8.5 – Kenneth Rosen – 6ª edição (em inglês) 29/33 
Seja ( S, ≼ ) um c.p.o. Dizemos que y ∈ S cobre um elemento x ∈ S se x ≺ y e não existe 
elemento z ∈ S tal que x ≺ z ≺ y. O conjunto de pares ( x,y ) tal que y cobre x é chamada 
de relação de cobertura do c.p.o. ( S, ≼ ). 
28. Qual é a relação de cobertura de da ordem parcial { ( a,b ) : a \ b } em {1,2,3,4,6,12 }? 
29. Qual é a relação de cobertura de da ordem parcial { ( A,B ) : A ⊆ B } no conjunto 
potência de { a,b,c }? 
30. Mostre que ( x,y ) pertence à relação de cobertura de um c.p.o. ( S, ≼ ) se, e somente 
se, x é menor do que y e existe uma aresta ligando x e y no diagrama de Hasse do c.p.o. 
31. Mostre que um c.p.o. finito pode ser reconstruído a partir de sua relação de 
cobertura. (Dica: mostre que o ordem parcial é o fecho reflexivo do fecho transitivo da 
relação de cobertura) 
32. Responda as perguntas sobre a ordem parcial representada pelo diagrama de Hasse 
 
a) Ache os elementos maximais. 
b) Ache os elementos minimais. 
c) Caso exista, qual é o elemento máximo? 
d) Caso exista, qual é o elemento mínimo? 
e) Ache os limites superiores de { a,b,c } 
f) Ache o menor limite superior de { a,b,c } se existir. 
33. Responda as perguntas sobre a ordem parcial do c.p.o. ( {3,5,9,15, 24,25} , \ ) 
a) Ache os elementos maximais. 
b) Ache os elementos minimais. 
c) Caso exista,qual é o elemento máximo? 
d) Caso exista, qual é o elemento mínimo? 
e) Ache os limites superiores de { 3,5 } 
f) Ache o menor limite superior de { 3,5 }se existir. 
g) Ache os limites inferiores de { 15, 45 } 
h) Ache o maior limite inferior de { 15, 45 } se existir 
 
Exercícios Selecionados – seçoes 8.1 a 8.5 – Kenneth Rosen – 6ª edição (em inglês) 30/33 
34. Responda as perguntas sobre a ordem parcial do c.p.o. 
( {2,4,6,9,12,18,27,36,48,60,72} , \ ) 
a) Ache os elementos maximais. 
b) Ache os elementos minimais. 
c) Caso exista, qual é o elemento máximo? 
d) Caso exista, qual é o elemento mínimo? 
e) Ache os limites superiores de { 2,9 } 
f) Ache o menor limite superior de { 2,9 }se existir. 
g) Ache os limites inferiores de { 60,72 } 
h) Ache o maior limite inferior de { 60,72 } se existir 
 
35. Responda as perguntas sobre a ordem parcial do c.p.o. 
( { {1}, {2}, {4}, {1,2} , {1,4}, {2,4}, {3,4}, {1,3,4}, {2,3,4} }, ⊆ ) 
a) Ache os elementos maximais. 
b) Ache os elementos minimais. 
c) Caso exista, qual é o elemento máximo? 
d) Caso exista, qual é o elemento mínimo? 
e) Ache os limites superiores de { {2}, {4} } 
f) Ache o menor limite superior de { {2}, {4} }se existir. 
g) Ache os limites inferiores de { { {1,3,4}, {2,3,4} }} 
h) Ache o maior limite inferior de { { {1,3,4}, {2,3,4} }}se existir 
36. Indique o conjunto parcialmente ordenado ( c.p.o. ) que 
a) tem um elemento minimal, mas não tem elemento maximal; 
b) tem um elemento maximal, mas não tem elemento minimal; 
c) não tem nem elementos maximais, nem elementos minimais. 
40. 
a) Mostre que se existe um elemento máximo em um c.p.o., então ele é único. 
b) Mostre que se existe um elemento mínimo em um c.p.o., então ele é único. 
41. 
a) Mostre que se existe um elemento máximo em um c.p.o., e existe um maximal 
então o maximal é único. 
b) Mostre que se existe um elemento mínimo em um c.p.o., e existe um minimal, 
então o minimal é único. 
42. 
a) Mostre que se existe um limite superior mínimo de um conjunto em um c.p.o., 
então ele é único. 
Exercícios Selecionados – seçoes 8.1 a 8.5 – Kenneth Rosen – 6ª edição (em inglês) 31/33 
b) Mostre que se existe um limite inferior máximo de um conjunto em um c.p.o., 
então ele é único. 
 
RESPOSTAS EXERCÍCIOS ÍMPARES 
 
 
 
Exercícios Selecionados – seçoes 8.1 a 8.5 – Kenneth Rosen – 6ª edição (em inglês) 32/33 
 
 
 
Exercícios Selecionados – seçoes 8.1 a 8.5 – Kenneth Rosen – 6ª edição (em inglês) 33/33

Outros materiais

Materiais relacionados

Perguntas relacionadas

Materiais recentes

Perguntas Recentes