lista relações 2022-2 (2)

Prévia do material em texto

Matemática Básica - Lista de
Exerćıcios 08
Relações
1. Liste os pares ordenados na realação R de A = {0, 1, 2, 3, 4} em B = {0, 1, 2, 3}
em que (a,b) ∈ R se somente se
(a) a = b (b) a + b = 4 (c) a > b
2. Para cada uma destas relações no conjunto {1, 2, 3, 4}, decida se ela é reflexiva, se
é simétrica, se é anti-simétrica e se é transitiva.
(a) {(2, 2), (2, 3), (2, 4), (3, 2), (3, 3), (3, 4)}
(b) {(1, 1), (1, 2), (2, 1), (2, 2), (3, 3), (4, 4)}
(c) {(2, 4), (4, 2)}
(d) {(1, 2), (2, 3), (3, 4)}
(e) {(1, 1), (2, 2), (3, 3), (4, 4)}
(f) {(1, 3), (1, 4), (2, 3), (2, 4), (3, 1), (3, 4)}
3. Determine se a relação R no conjunto de todos os números inteiros é reflexiva,
simétrica, anti-simétrica e/ou transitiva, em que (x, y) ∈ R se somente se
(a) x 6= y.
(b) xy ≥ 1.
(c) x = y + 1 ou x = y − 1.
(d) x e y são ambos negativos ou ambos não negativos.
(e) x = y2.
(f) x ≥ y2.
Uma relação R em um conjunto A é irreflexiva se para todo a ∈ A, (a, a) /∈ R.
Isto é, R é irreflexiva se nenhum elemento de A for relacionado a si próprio.
4. Quais relações no Exerćıcio 2 são irreflexivas?
5. Uma relação em um conjunto pode não ser nem reflexiva nem irreflexiva?
6. Dê um exemplo de relação irreflexiva no conjunto de todas as pessoas.
7. Quais relações no Exerćıcio 2 são assimétricas?
8. Quais relações no Exerćıcio 3 são assimétricas?
9. Use quantificadores para expressar o que signifca uma relação ser assimétrica.
10. Quantas relações diferentes existem de um conjunto com m elementos em um
conjunto com n elementos?
11. Sejam A o conjunto dos estudantes de sua escola e B conjunto dos livros na
biblioteca da escola. Sejam R1eR2 as relações que consistem em todos os pares
ordenados (a, b), nos quais é exigido que o estudante a leia o livro b em uma
disciplina, e nos quais o estudante a leu o livro b, respectivamente. Descreva os
pares ordenados em cada uma destas aplicações.
(a) R1 ∪ R2. (b) R1 ∩ R2. (c) R1 − R2. (d) R2 − R1.
12. Seja R a relação no conjunto das pessoas que consiste nos pares (a, b), nos quais a
é progenitor de b. Seja S a relação no conjunto das pessoas que consiste nos pares
(a, b), nos quais a e b são irmãos. O que são S ◦ R e R ◦ S?
Os exerćıcios abaixo tratam destas relações no conjunto dos número reais:
R1 = {(a, b) ∈ R2|a > b}, a relação “maior que”.
R2 = {(a, b) ∈ R2|a ≥ b}, a relação “maior que ou igual a”.
R3 = {(a, b) ∈ R2|a < b}, a relação “menor que”.
R4 = {(a, b) ∈ R2|a ≤ b}, a relação “menor que ou igual a”.
R5 = {(a, b) ∈ R2|a = b}, a relação “igual a”.
R6 = {(a, b) ∈ R2|a 6= b}, a relação “diferente de”.
13. Determine
(a) R2 ∪ R4.
(b) R3 ∪ R6.
(c) R3 ∩ R6.
(d) R4 ∩ R6.
(e) R3 − R6.
(f) R6 − R3.
14. Determine
(a) R2 ◦ R1.
(b) R2 ◦ R2
(c) R3 ◦ R5.
(d) R4 ◦ R1.
(e) R5 ◦ R3.
(f) R3 ◦ R6.
(g) R4 ◦ R6.
(h) R6 ◦ R6.
15. Seja R a relação no conjunto das pessoas com doutorado, tal que (a, b) ∈ R se e
somente se a foi o orientador de tese de b. Quando um par ordenado (a, b) está em
R2? Quando um par ordenado (a, b) está em Rn, quando n é um inteiro positivo?
(Observe que toda pessoa com doutorado tem um orientador de tese.)
16. Quantas das 16 relações diferentes em {0, 1} contêm o par (0, 1)?
17. (a) Quantas relações existem no conjunto {a, b, c, d}?
(b) Quantas relações existem no conjunto {a, b, c, d} que contêm o par (a, a)?
18. Quantas relações existem em um conjunto com n elementos que sejam
(a) simétricas?
(b) anti-simétricas
(c) assimétricas?
(d) irreflexivas?
(e) reflexivas e simétricas?
(f) nem reflexivas ne irreflexivas?
19. Mostre que a relação R em um conjunto A é simétrica se e somente se R = R−1,
em que R−1 é a relação inversa.
20. Mostre que a relação R em um conjunto A é reflexiva se e somente se a relação
inversa R−1 for reflexiva.
21. Suponha que a relação R seja irreflexiva. R2 é necessariamente irreflexiva? Dê
uma razão para sua resposta.
22. Represente cada uma destas relações em {1, 2, 3} por uma matriz
(a) {(1, 1), (1, 2), (1, 3)}
(b) {(1, 2), (2, 1), (2, 2), (3, 3)}
(c) {((1, 1), (1, 2), (1, 3), (2, 2), (2, 3), (3, 3)}
(d) {(1, 3), (3, 1)}
23. Liste os pares ordenados nas relações em {1, 2, 3} correspondentes a estas matrizes
(a)  1 0 10 1 0
1 0 1

(b)  0 1 00 1 0
0 1 0

(c)  1 1 11 0 1
1 1 1

24. Como a matriz que representa uma relação R em um conjunto A pode ser usada
para determinar se a relação é irreflexiva?
25. Determine se as relações representadas pelas matrizes no Exerćıcio 23 são
reflexivas, irreflexivas, simétricas, anti-simétricas e/ou transitivas.
26. Quantos elementos não nulos a matriz que representa a relação R em A =
{1, 2, 3, ..., 100} tem se R for
(a) {(a, b) | a > b}?
(b) {(a, b) | a 6= b}?
(c) {(a, b) | a = b + 1}?
(d) {(a, b) | a = 1}?
(e) {(a, b) | ab = 1}?
27. Como pode ser encontrada a matriz para R, o complementar da relação R, a partir
da matriz que representa R, quando R é uma relação em um conjunto finito A?
28. Seja R a relação representada pela matriz
MR =
 0 1 11 1 0
1 0 1

Encontre a matriz que representa
(a) R−1 (b) R (c) R2
29. Seja R a relação representada pela matriz
MR =
 0 1 00 0 1
1 1 0

Encontre as matrizes que representam
(a) R2 (b) R3 (c) R4
30. Seja R uma relação em um conjunto A com n elementos. Se existirem k elementos
não nulos em MR, a matriz que representa R, quantos elementos não nulos existem
em M−R , a matriz que representa R, o complemento de R?
31. Trace os d́ıgrafos que representam cada uma das relações abaixo.
(a) {(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)}
(b) {(1, 1), (1, 4), (2, 2), (3, 3), (4, 1)}
(c) {(1, 2), (1, 3), (1, 4), (2, 1), (2, 3), (2, 4),
(3, 1), (3, 2), (3, 4), (4, 1), (4, 2), (4, 3)}
(d) {(2, 4), (3, 1), (3, 2), (3, 4)}
32. Trace os d́ıgrafos que representam cada uma das relações abaixo.
(a)
 1 1 0 11 0 1 00 1 1 1
1 0 1 1

(b)
 1 1 1 00 1 0 00 0 1 1
1 0 0 1

(c)
 0 1 0 11 0 1 00 1 0 1
1 0 1 0

Nos exerćıcios abaixo, liste os pares ordenados nas relações representandas
pelos d́ıgrafos.
33.
a
b c
34.
a b
c d
35.
a b
c d
1
36. Como o d́ıgrafo de uma relação R em um conjunto finito A pode ser usado para
determinar se uma relação é assimétrica?
37. Determine se as relações representadas pelos d́ıgrafos mostrados nos exerćıcios 33
a 35 são reflexivas, irreflexivas, simétricas, anti-simétricas e/ou transitivas.
38. Seja R uma relação em um conjunto A. Explique como usar o d́ıgrafo que
representa R para obter o d́ıgrafo que representa a relação inversa R−1.
39. Seja R a relação no conjunto {0, 1, 2, 3} que contém os pares ordenados
(0, 1), (1, 1), (1, 2), (2, 0), (2, 2)e(3, 0). Encontre o
(a) fecho reflexivo de R. (b) fecho simétrico de R.
Nos exerćıcios abaixo, trace o d́ıgrafo do fecho reflexivo das relações com os
d́ıgrafos mostrados.
40.
a b
c d
41.
a b
c d
42. Encontre os d́ıgrafos dos fechos simétricos das relações com os d́ıgrafos mostrados
nos exerćıcios acima.
43. Encontre o d́ıgrafo da menor relação que seja tanto reflexiva quanto simétrica para
cada uma das relações com d́ıgrafos mostrados nos exerćıcios acima.
44. Quando é posśıvel definir o “fecho irreflexivo” de uma relação R, isto é, uma relação
que contenha R, seja irreflexiva e esteja contida em toda relação irreflexiva que
contenha R?
45. Seja R a relação no conjunto {1, 2, 3, 4, 5} que contém os pares ordenados
(1, 3), (2, 4), (3, 1), (3, 5), (4, 3), (5, 1), (5, 2) e (5, 4). Encontre
(a) R2.
(b) R3.
(c) R4.
(d) R5.
(e) R6.
(f) R∗.
46. Seja R a relação no conjunto de todos os estudantes que contém o par ordenado
(a, b) se a e b tiverem, pelo menos, uma aula em comum e a 6= b. Quando (a, b)
está em
(a) R2. (b) R3. (c) R∗.
47. Use representação por matrizes para encontrar os fechos transitivos destas relações
em {1, 2, 3, 4}:
(a) {(1, 2), (2, 1), (2, 3), (3, 4), (4, 1)}(b) {(2, 1), (2, 3), (3, 1), (3, 4), (4, 1), (4, 3)}
(c) {(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)}
(d) {(1, 1), (1, 4), (2, 1), (2, 3), (3, 1), (3, 2), (3, 4), (4, 2)}
48. Encontre a menor relação que contém a relação {(1, 2), (1, 4), (3, 3), (4, 1)} que
seja.
(a) reflexiva e transitiva.
(b) simétrica e transitiva.
(c) reflexiva, simetrica e transitiva.
31 33 35
Respostas:
1. (a) {(0, 0), (1, 1), (2, 2), (3, 3)}
(b) {(1, 3), (2, 2), (3, 1), (4, 0)}
(c) {(1, 0), (2, 0), (2, 1), (3, 0), (3, 1), (3, 2), (4, 0), (4, 1), (4, 2), (4, 3)}
2. (a) Transitiva
(b) Reflexiva, simétrica, transitiva
(c) Simétrica
(d) Anti-simétrica
(e) Reflexiva, simétrica, anti-simétrica, transitiva
(f) Nenhuma destas propriedades
3. (a) Simétrica
(b) Simétrica, transitiva
(c) Simétrica
(d) Reflexiva, simétrica, transitiva
(e) Anti-simétrica
(f) Anti-simétrica, transitiva
4. (c), (d), (f)
5. Sim, por exemplo {(1, 1)} em {1, 2}
6. (a, b) ∈ R se e somente se a for mais alto que b.
7. (a).
8. Nenhuma.
9. ∀a∀b[(a 6= b ∧ (a, b) ∈ R)→ (b, a) /∈ R].
10. 2mn.
11. (a) {(a, b)|a precisa ler ou já leu. b}
(b) {(a, b)|a precisa ler ou já leu. b}
(c) {(a, b)| a precisa ler b, mas ainda não o leu. }
(d) {(a, b)| a já leu b, mas não precisava le-lo. }
12. S ◦ R = {(a, b)|a é progenitor de b e b tem um irmão },
R ◦ S = {(a, b)|a é tia ou tio de b}.
13.
(a) R2.
(b) R6
(c) R3
(d) R3
(e) Ø
(f) R1
14. (a) R1
(b) R2
(c) R3
(d) R2
(e) R3
(f) R2
(g) R2
(h) R2
15. b terminou seu doutorado sob a orientação de alguém que terminou seu doutorado
sob a orientação de a; existe uma única sequência de n + 1 pessoas, começando
com a e terminando com b, tal que cada uma é orientadora da próxima pessoa na
sequência.
16. 8
17. (a) 65536 (b) 32768
18.
(a) 2n(n+1)/2
(b) 2n3n(n−1)/2
(c) 3n(n−1)/2
(d) 2n(n−1)
(e) 2n(n−1)/2
(f) 2n
2
− 2.2n(n−1)
19. Se R for simétrica e (a, b) ∈ R, então (b, a) ∈ R, de modo que (a, b) ∈ R−1.
Logo, R ⊆ R−1. Analogamente, R−1 ⊆ R. Assim, R = R−1. Reciprocamente,
se R = R−1 e (a, b) ∈ R, então (a, b) ∈ R−1, de modo que (b, a) ∈ R.
Portanto, R é simétrica.
20. R é reflexiva se e somente se (a, a) ∈ R para todo a ∈ A se e somente se
(a, a) ∈ R−1 [pois (a, a) ∈ R se e somente se (a, a) ∈ R−1] se e somente se
R−1 é reflexiva.
21. Não, por exemplo, considere R = {(1, 2), (2, 1)}.
22. (a)  1 1 10 0 0
0 0 0

(b)  0 1 01 1 0
0 0 1

(c)  1 1 10 1 1
0 0 1

(d)  0 0 10 0 0
1 0 0

23.
(a) (1, 1), (1, 3), (2, 2), (3, 1), (3, 3)
(b) (1, 2), (2, 2), (3, 2)
(c) (1, 1), (1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2), (3, 3)
24. A relação é irreflexiva se e somente se a diagonal principal da matriz contiver apenas
0s.
25.
(a) Reflexiva, simétrica, transitiva
(b) Anti-simétrica, transitiva
(c) Simétrica
26.
(a) 4950
(b) 9900
(c) 99
(d) 100
(e) 1
27. Mude cada 0 para 1 e cada 1 para 0.
28.
(a)
MR =
 0 1 11 1 0
1 0 1

(b)
MR =
 1 0 00 0 1
0 1 0

(c)
MR =
 1 1 11 1 1
1 1 1

29.
(a)
MR =
 0 0 11 1 0
0 1 1

(b)
MR =
 1 1 00 1 1
1 1 1

(c)
MR =
 0 1 11 1 1
1 1 1

30. n2 − k
31.
(a)
1
2 3
4
2
Usuario
Retângulo
Usuario
Retângulo
Usuario
Retângulo