lista11 - Propriedades e Conceitos de Relações

SAVE OFFLINE

Matem´ atica Discreta Lista de Exerc´ıcios 11 ˜es: propriedades, representac¸a ˜o, fecho Revis˜ ao Relac¸o

(a) sim´etricas?

(d) irreflexivas?

(b) anti-sim´etricas

(e) reflexivas e sim´etricas?

(c) assim´etricas?

(f) nem reflexivas ne irreflexivas?

˜o R em um conjunto A ´e sim´etrica se e somente se R = R−1 , 19. Mostre que a relac¸a ˜o inversa. em que R−1 ´e a relac¸a ˜o R em um conjunto A ´e reflexiva se e somente se a relac¸a ˜o 20. Mostre que a relac¸a −1 inversa R for reflexiva. ˜o R seja irreflexiva. R2 ´e necessariamente irreflexiva? Dˆe 21. Suponha que a relac¸a uma raz˜ ao para sua resposta. ˜es em {1, 2, 3} por uma matriz 22. Represente cada uma destas relac¸o (a) {(1, 1), (1, 2), (1, 3)} (b) {(1, 2), (2, 1), (2, 2), (3, 3)}

˜o R de A = {0, 1, 2, 3, 4} em B = {0, 1, 2, 3} 1. Liste os pares ordenados na realac¸a em que (a,b) ∈ R se somente se (a) a = b

(b) a + b = 4

(c) {((1, 1), (1, 2), (1, 3), (2, 2), (2, 3), (3, 3)} (d) {(1, 3), (3, 1)}

(c) a > b

˜es em {1, 2, 3} correspondentes a estas matrizes 23. Liste os pares ordenados nas relac¸o

˜es no conjunto {1, 2, 3, 4}, decida se ela ´e reflexiva, se 2. Para cada uma destas relac¸o ´e sim´etrica, se ´e anti-sim´etrica e se ´e transitiva.

(a)

(a) {(2, 2), (2, 3), (2, 4), (3, 2), (3, 3), (3, 4)}

(b) 

1  0 1

(b) {(1, 1), (1, 2), (2, 1), (2, 2), (3, 3), (4, 4)}

0 1 0



(c) 

1 0  1

0  0 0

1 1 1





0 0  0

1  1 1

1 0 1

 1 1  1

(c) {(2, 4), (4, 2)} ˜o R em um conjunto A pode ser usada 24. Como a matriz que representa uma relac¸a ˜o ´e irreflexiva? para determinar se a relac¸a ˜es representadas pelas matrizes no Exerc´ıcio 23 s˜ 25. Determine se as relac¸o ao reflexivas, irreflexivas, sim´etricas, anti-sim´etricas e/ou transitivas. ˜o R em A = 26. Quantos elementos n˜ ao nulos a matriz que representa a relac¸a {1, 2, 3, ..., 100} tem se R for

(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)} ˜o R no conjunto de todos os n´ 3. Determine se a relac¸a umeros inteiros ´e reflexiva, sim´etrica, anti-sim´etrica e/ou transitiva, em que (x, y) ∈ R se somente se

(d) {(a, b) | a = 1}?

(a) {(a, b) | a > b}? (b) {(a, b) | a = 6 b}? (c) {(a, b) | a = b + 1}?

(a) x 6= y. (b) xy ≥ 1. (c) x = y + 1 ou x = y − 1.

(e) {(a, b) | ab = 1}?

˜o R, a partir 27. Como pode ser encontrada a matriz para R, o complementar da relac¸a ˜o em um conjunto finito A? da matriz que representa R, quando R ´e uma relac¸a ˜o representada pela matriz 28. Seja R a relac¸a

(d) x e y s˜ ao ambos negativos ou ambos n˜ ao negativos. (e) x = y 2 . (f) x ≥ y 2 .



MR

˜o R em um conjunto A ´e irreflexiva se para todo a ∈ A, (a, a) ∈ Uma relac¸a / R. Isto ´e, R ´e irreflexiva se nenhum elemento de A for relacionado a si pr´ oprio.

(b) R1 ∩ R2 .

(c) R1 − R2 .

(a) R−1

(a) R2

(a)

2

˜o “menor que ou igual a”. R4 = {(a, b) ∈ R |a ≤ b}, a relac¸a 2

(b) 1  1  0 1

˜o “igual a”. R5 = {(a, b) ∈ R |a = b}, a relac¸a



2

˜o “diferente de”. R6 = {(a, b) ∈ R |a 6= b}, a relac¸a 13. Determine

(d) R4 ◦ R1 . (e) R5 ◦ R3 . (f) R3 ◦ R6 .

(g) R4 ◦ R6 .

1 0 1 0

0 1 1 1

1 0  1  1 

(c) 1  0  0 1 

1 1 0 0

1 0 1 0

0 0  1  1 

0  1  0 1

1 0 1 0



0 1 0 1

 1 0  1  0

˜ es representandas Nos exerc´ıcios abaixo, liste os pares ordenados nas relac¸o pelos d´ıgrafos. 33.

14. Determine (a) R2 ◦ R1 . (b) R2 ◦ R2 (c) R3 ◦ R5 .

(c) R4

˜es abaixo. 32. Trace os d´ıgrafos que representam cada uma das relac¸o

˜o “menor que”. R3 = {(a, b) ∈ R2 |a < b}, a relac¸a

(f) R6 − R3 .

(b) R3

(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)}

˜o “maior que ou igual a”. R2 = {(a, b) ∈ R2 |a ≥ b}, a relac¸a

(e) R3 − R6 .

 0 1  0

˜o em um conjunto A com n elementos. Se existirem k elementos 30. Seja R uma relac¸a n˜ ao nulos em MR , a matriz que representa R, quantos elementos n˜ ao nulos existem − , a matriz que representa R, o complemento de R? em MR ˜es abaixo. 31. Trace os d´ıgrafos que representam cada uma das relac¸o

˜ es no conjunto dos n´ Os exerc´ıcios abaixo tratam destas relac¸o umero reais:

(c) R3 ∩ R6 .

1 0 1

Encontre as matrizes que representam

˜o “maior que”. R1 = {(a, b) ∈ R2 |a > b}, a relac¸a

(d) R4 ∩ R6 .

(c) R2

(b) R

 0 MR =  0 1

(d) R2 − R1 .

(a) R2 ∪ R4 .

 1 0  1

˜o representada pela matriz 29. Seja R a relac¸a

˜o no conjunto das pessoas que consiste nos pares (a, b), nos quais a 12. Seja R a relac¸a ´e progenitor de b. Seja S a relac¸a ˜o no conjunto das pessoas que consiste nos pares (a, b), nos quais a e b s˜ ao irm˜ aos. O que s˜ ao S ◦ R e R ◦ S?

(b) R3 ∪ R6 .

1 1 0

Encontre a matriz que representa

˜es no Exerc´ıcio 2 s˜ Quais relac¸o ao irreflexivas? ˜o em um conjunto pode n˜ Uma relac¸a ao ser nem reflexiva nem irreflexiva? ˜o irreflexiva no conjunto de todas as pessoas. Dˆe um exemplo de relac¸a ˜es no Exerc´ıcio 2 s˜ Quais relac¸o ao assim´etricas? ˜es no Exerc´ıcio 3 s˜ Quais relac¸o ao assim´etricas? ˜o ser assim´etrica. Use quantificadores para expressar o que signifca uma relac¸a ˜es diferentes existem de um conjunto com m elementos em um Quantas relac¸o conjunto com n elementos? 11. Sejam A o conjunto dos estudantes de sua escola e B conjunto dos livros na ˜es que consistem em todos os pares biblioteca da escola. Sejam R1 eR2 as relac¸o ordenados (a, b), nos quais ´e 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 ˜es. pares ordenados em cada uma destas aplicac¸o 4. 5. 6. 7. 8. 9. 10.

(a) R1 ∪ R2 .

0 = 1 1

a

a

b

c

d

(h) R6 ◦ R6 .

˜o no conjunto das pessoas com doutorado, tal que (a, b) ∈ R se e 15. Seja R a relac¸a somente se a foi o orientador de tese de b. Quando um par ordenado (a, b) est´ a em R2 ? Quando um par ordenado (a, b) est´ a em Rn , quando n ´e um inteiro positivo? (Observe que toda pessoa com doutorado tem um orientador de tese.) ˜es diferentes em {0, 1} contˆem o par (0, 1)? 16. Quantas das 16 relac¸o ˜es existem no conjunto {a, b, c, d}? 17. (a) Quantas relac¸o

c

b a

b

c

d

˜es existem no conjunto {a, b, c, d} que contˆem o par (a, a)? (b) Quantas relac¸o ˜es existem em um conjunto com n elementos que sejam 18. Quantas relac¸o

1

34.

35.

˜o R em um conjunto finito A pode ser usado para 36. Como o d´ıgrafo de uma relac¸a ˜o ´e assim´etrica? determinar se uma relac¸a ˜es representadas pelos d´ıgrafos mostrados nos exerc´ıcios 33 37. Determine se as relac¸o a 35 s˜ ao reflexivas, irreflexivas, sim´etricas, anti-sim´etricas e/ou transitivas. ˜o em um conjunto A. Explique como usar o d´ıgrafo que 38. Seja R uma relac¸a ˜o inversa R−1 . representa R para obter o d´ıgrafo que representa a relac¸a ˜o no conjunto {0, 1, 2, 3} que cont´em os pares ordenados 39. Seja R a relac¸a (0, 1), (1, 1), (1, 2), (2, 0), (2, 2)e(3, 0). Encontre o (a) fecho reflexivo de R.

14.

(a) R2 . (b) R6

(c) R3 (d) R3

(e) Ø (f) R1

(a) R1 (b) R2 (c) R3

(d) R2 (e) R3 (f) R2

(g) R2 (h) R2

˜o de algu´em que terminou seu doutorado 15. b terminou seu doutorado sob a orientac¸a ˜o de a; existe uma u ´ nica sequˆencia de n + 1 pessoas, comec¸ando sob a orientac¸a com a e terminando com b, tal que cada uma ´e orientadora da pr´ oxima pessoa na sequˆencia.

(b) fecho sim´etrico de R.

16. 8

˜ es com os Nos exerc´ıcios abaixo, trace o d´ıgrafo do fecho reflexivo das relac¸o d´ıgrafos mostrados.

17.

(a) 65536

(b) 32768

(a) 2n(n+1)/2

(d) 2n(n−1)

41.

40.

18.

a

b

a

b

n n(n−1)/2

(e) 2n(n−1)/2

n(n−1)/2

(f) 2n − 2.2n(n−1)

(b) 2 3

2

(c) 3

c

d

c

19. Se R for sim´etrica e (a, b) ∈ R, ent˜ ao (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˜ ao (a, b) ∈ R−1 , de modo que (b, a) ∈ R. Portanto, R ´e sim´etrica.

d

˜es com os d´ıgrafos mostrados 42. Encontre os d´ıgrafos dos fechos sim´etricos das relac¸o nos exerc´ıcios acima. ˜o que seja tanto reflexiva quanto sim´etrica para 43. Encontre o d´ıgrafo da menor relac¸a ˜es com d´ıgrafos mostrados nos exerc´ıcios acima. cada uma das relac¸o ˜o R, isto ´e, uma relac¸a ˜o 44. Quando ´e poss´ıvel definir o “fecho irreflexivo” de uma relac¸a ˜o irreflexiva que que contenha R, seja irreflexiva e esteja contida em toda relac¸a contenha R? ˜o no conjunto {1, 2, 3, 4, 5} que cont´em os pares ordenados 45. Seja R a relac¸a (1, 3), (2, 4), (3, 1), (3, 5), (4, 3), (5, 1), (5, 2) e (5, 4). Encontre (a) R2 . 3

(b) R .

(c) R4 .

20. R ´e 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 ´e reflexiva. 21. N˜ ao, por exemplo, considere R = {(1, 2), (2, 1)}. 22.

(e) R6 .

(d) R .

1  0 0

1 0 0

 1 0  0



1 1 0

 0 0  1

0  1 0



1  0 0

1 1 0

 1 1  1



0 0 0

 1 0  0

(d) 0  0 1

23.

(c) R∗ .

(b) R3 .



(b)

(f) R∗ .

5

˜o no conjunto de todos os estudantes que cont´em o par ordenado 46. Seja R a relac¸a (a, b) se a e b tiverem, pelo menos, uma aula em comum e a 6= b. Quando (a, b) est´ a em (a) R2 .

(c)

(a)

(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)

˜o por matrizes para encontrar os fechos transitivos destas relac¸o ˜es 47. Use representac¸a em {1, 2, 3, 4}: (a) {(1, 2), (2, 1), (2, 3), (3, 4), (4, 1)}

˜o ´e irreflexiva se e somente se a diagonal principal da matriz contiver apenas 24. A relac¸a 0s.

(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)}

25.

(d) {(1, 1), (1, 4), (2, 1), (2, 3), (3, 1), (3, 2), (3, 4), (4, 2)} (a) Reflexiva, sim´etrica, transitiva (b) Anti-sim´etrica, transitiva (c) Sim´etrica

˜o que cont´em a relac¸a ˜o {(1, 2), (1, 4), (3, 3), (4, 1)} que 48. Encontre a menor relac¸a seja. (a) reflexiva e transitiva. (b) sim´etrica e transitiva.

(c) reflexiva, simetrica e transitiva. 26.

Respostas: 1.

(a) 4950 (b) 9900

27. Mude cada 0 para 1 e cada 1 para 0. 28.

(c) {(1, 0), (2, 0), (2, 1), (3, 0), (3, 1), (3, 2), (4, 0), (4, 1), (4, 2), (4, 3)} (a) Transitiva

(a)

(b) Reflexiva, sim´etrica, transitiva

0 MR =  1 1

(d) Anti-sim´etrica (e) Reflexiva, sim´etrica, anti-sim´etrica, transitiva

1 1 0



1 0  1

(c) 

1 MR =  0 0

0 0 1



(a)

(a) Sim´etrica

(d) Reflexiva, sim´etrica, transitiva

(b) Sim´etrica, transitiva

(e) Anti-sim´etrica

(c) Sim´etrica

(f) Anti-sim´etrica, transitiva







0 MR =  1 0

0 1 1

1 0  1

 1 MR =  0 1

1 1 1

 0 1  1

(b)

(c), (d), (f) Sim, por exemplo {(1, 1)} em {1, 2} (a, b) ∈ R se e somente se a for mais alto que b. (a). Nenhuma. ∀a∀b[(a 6= b ∧ (a, b) ∈ R) → (b, a) ∈ / R]. 2mn . (a) {(a, b)|a precisa ler ou j´ a leu. b}

30. n2 − k 31.

(b) {(a, b)|a precisa ler ou j´ a leu. b}

1

4

2

3

(c) {(a, b)| a precisa ler b, mas ainda n˜ ao o leu. } (d) {(a, b)| a j´ a leu b, mas n˜ ao precisava le-lo. } 12. S ◦ R = {(a, b)|a ´e progenitor de b e b tem um irm˜ ao }, R ◦ S = {(a, b)|a ´e tia ou tio de b}. 13. (a)

2

 1 MR =  1 1

0 1  0

(c)

29.

(f) Nenhuma destas propriedades

4. 5. 6. 7. 8. 9. 10. 11.

(b) 

(c) Sim´etrica

3.

(e) 1

(a) {(0, 0), (1, 1), (2, 2), (3, 3)} (b) {(1, 3), (2, 2), (3, 1), (4, 0)}

2.

(c) 99 (d) 100

MR

0 = 1 1

1 1 1

 1 1  1

1 1 1

 1 1  1

1

4

2

3

b

c

d

(c)

(a)

(b)

a

b

c

d

a

b

c

d

4

1

(b)

2

3

(c)

(d)

a

1

4

2

3

43.

a

b

c

d

(b)

(a)

32. Por simplicidade, indicamos pares de arestas entre os mesmos dois v´ertices em sentidos opostos usando uma flecha dupla, em vez de desenhar duas curvas separadas.

1

2

1

4

3

c

d

a

b

c

d

44. Apenas quando R ´e irreflexiva, em cujo caso ela ´e seu pr´ oprio fecho. 45. (a) {(1, 1), (1, 5), (2, 3), (3, 1), (3, 2), (3, 3), (3, 4), (4, 1), (4, 5), (5, 3), (5, 4)}

4

(b) {(1, 1), (1, 2), (1, 3), (1, 4), (2, 1), (2, 5), (3, 1), (3, 3), (3, 4), (3, 5), (4, 1), (4, 2), (4, 3), (4, 4), (5, 1), (5, 3), (5, 5) }

(b)

(a)

b

2 (c)

3

a

1

(c) {(1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (2, 1), (2, 2), (2, 3), (2, 4), (3, 1), (3, 2), (3, 3), (3, 4), (3, 5), (4, 1), (4, 3), (4, 4), (4, 5), (5, 1), (5, 2), (5, 3), (5, 4), (5, 5)}

2

(d) {(1, 1), (1, 3), (1, 4), (1, 5), (2, 1), (2, 3), (2, 4), (2, 4), (2, 5), (3, 1), (3, 2 ), (3, 3), (3, 4), (3, 5), (4, 1), (4, 2), (4, 3), (4, 4), (4, 5), (5, 1), (5, 2), (5, 3), (5, 4), (5, 5)}

3

(e) {(1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (2, 1), (2, 2), (2, 3), (2, 4), (2, 5), (3, 1), (3, 2), (3, 3), (3, 4), (3, 5), (4, 1), (4, 2), (4, 3), (4, 4), (4, 5), (5, 1), (5, 2), (5, 3), (5, 4), (5, 5)}

4

(c) 33. {(a, b), (a, c), (b, c), (c, b)}

34. {(a, c), (b, a), (c, d), (d, b)}

35. {(a, a), (a, b), (a, c), (b, a), (b, b), (b, c), (c, a), (c, b), (d, d)} ˜o ´e assim´etrica se e somente se o d´ıgrafo n˜ 36. A relac¸a ao tiver nenhum lac¸o e nenhum caminho fechado de comprimento 2. 37. Exerc´ıcio 33: irreflexiva, Exerc´ıcio 34: irreflexiva, anti-sim´etrica, Exerc´ıcio 35: sim´etrica. 38. Inverta o sentido de todas as arestas do d´ıgrafo para R. 39. (a) {(0, 0), (0, 1), (1, 1), (1, 2), (2, 0), (2, 2), (3, 0), (3, 3)}

46.

(b) Se existirem dois estudantes c e d tais que a e c tenham uma aula em comum, c e d tenham uma aula em comum e d e b tenham uma aula em comum (c) Se existir uma sequˆencia s0 , ..., sn de estudantes com n≥ 1 tais que s0 = a, sn = b, e para cada i = 1, 2, ...n, si e si−1 tenham uma aula em comum

(b) {(0, 1), (0, 2), (0, 3), (1, 0), (1, 1), (1, 2), (2, 0), (2, 1), (2, 2), (3, 0)}

a

c

(f) {(1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (2, 1), (2, 2), (2, 3), (2, 4), (2, 5), (3, 1), (3, 2), (3, 3), (3, 4), (3, 5), (4, 1), (4, 2), (4, 3), (4, 4), (4, 5), (5, 1), (5, 2), (5, 3), (5, 4), (5, 5)} (a) Se existir um estudante c que tenha uma aula em comum que a e tenha uma aula em comum que b

47.

(a)

(c)

b MR

1  1 = 1 1

1 1 1 1

1 1 1 1

1 1  1  1

MR

0  1 = 1 1

0 0 0 0

0 1 1 1

 0 1  1  1



(b)

d



b 48.



MR

0  0 = 0 0

1 0 0 0

1 1 0 0

 1 1  1  0

MR

1  1 = 1 1

1 1 1 1

1 1 1 1

 1 1  1  1

(d)

40.

a





(a) {(1, 1), (1, 2), (1, 4), (2, 2), (3, 3), (4, 1), (4, 2), (4, 4)} (b) {(1, 1), (1, 2), (1, 4), (2, 1), (2, 2), (2, 4), (3, 3), (4, 1), (4, 2), (4, 4)} (c) {(1, 1), (1, 2), (1, 4), (2, 1), (2, 2), (2, 4), (3, 3), (4, 1), (4, 2), (4, 4)}

41. 42.

c

d 3