Baixe o app para aproveitar ainda mais
Prévia do material em texto
MAT 01375 – Matema´tica Discreta B 2016/2 Lista de Exerc´ıcios 4 1. Seja A = {a, b, c}. Determine a representac¸a˜o matricial das seguintes relac¸o˜es em A× A. a) S1 = {(a, a), (a, b), (a, c)} b) S2 = {(a, b), (b, a), (b, b), (c, c)} c) S3 = {(a, a), (a, b), (a, c), (b, b), (b, c), (c, c)} d) S4 = {(a, c), (c, a)} Quais das relac¸o˜es acima sa˜o reflexivas, irreflexivas, sime´tricas, antissime´trica e/ou transitivas? 2. Classifique as relac¸o˜es abaixo, dadas por sua representac¸a˜o matricial, quanto a re- flexividade, simetria e transitividade. Justifique sua resposta. T = 1 1 1 0 1 1 1 1 1 , M = 1 0 1 0 0 1 0 1 1 0 1 0 0 1 0 1 , e N = 1 1 1 0 1 1 1 0 1 1 1 0 0 0 0 1 . 3. Seja A = {a, e, i, o, u}. Apresente um exemplo de uma relac¸a˜o em A que e´: a) injetora e reflexiva b) sobrejetora e sime´trica c) anti-sime´trica e transitiva d) injetora e na˜o total e) funcional e sobrejetora f) reflexiva e anti-sime´trica g) na˜o sime´trica e na˜o anti-sime´trica h) transitiva e sime´trica e na˜o reflexiva 4. Seja A um conjunto e R ⊆ A× A. Prove ou deˆ um contra-exemplo: a) Se R e´ sime´trica e transitiva, enta˜o R e´ reflexiva. b) Se R e´ reflexiva, enta˜o R e´ total. c) Se R e´ reflexiva, enta˜o R e´ sobrejetora. d) Se R e´ funcional, enta˜o R na˜o e´ transitiva. e) Se R e´ sime´trica, enta˜o a relac¸a˜o R−1 coincide com R. 5. Fac¸a o grafo das relac¸o˜es S1, S2, S3, S4, T,M,N , dos exerc´ıcios 1 e 2 acima. 6. Verifique quais das relac¸o˜es S1, S2, S3, T,M,N sa˜o de equivaleˆncia e quais sa˜o de ordem. Justifique sua resposta. 7. Seja R a relac¸a˜o de equivaleˆncia dada pela congrueˆncias mo´dulo n, ou seja, dizemos que (a, b) ∈ R ⇐⇒ a e b teˆm o mesmo resto na divisa˜o por n. Em cada caso abaixo, descreva a classe de equivaleˆncia [ 4 ]n, com a) n = 3. b) n = 5. c) n = 6. 8. Seja R a relac¸a˜o em N× N definida por: ( (a, b), (c, d) ) ∈ R⇐⇒ a+ d = b+ c. a) Mostre que R e´ uma relac¸a˜o de equivaleˆncia. b) Determine as classes de equivaleˆncia de [(1, 1)]R, [(2, 1)]R e [(3, 2)]R. 9. Seja S uma relac¸a˜o em R× R = R2 definida por: ( (a, b), (c, d) ) ∈ S ⇐⇒ a = c. a) S e´ funcional? S e´ sobrejetora? b) Mostre que S e´ uma relac¸a˜o de equivaleˆncia em R2. c) Descreva [(2, 3)]S 10. Seja S uma relac¸a˜o em R× R = R2 definida por: ( (a, b), (c, d) ) ∈ S ⇐⇒ a+ 2b = c+ 2d. a) Mostre que S e´ uma relac¸a˜o de equivaleˆncia. b) Determine as classes de equivaleˆncia de [(1, 1)]S e [(2, 3)]S. c) S e´ total? S e´ injetora? Justifique. 11. Seja R uma relac¸a˜o sobre Z dada por xRy ⇐⇒ 4 | (x+ 3y). a) Mostre que a relac¸a˜o R e´ uma relac¸a˜o de equivaleˆncia; b) Descreva a classe de equivaleˆncia [0]R. c) Descreva a classe de equivaleˆncia [3]R. 12. Verifique se as relac¸o˜es definidas abaixo sa˜o relac¸o˜es de ordem parcial. Justifique suas respostas. (a) A relac¸a˜o em {a, b, c, d} representada pela matriz 1 1 1 1 0 1 0 1 0 0 1 0 0 0 0 1 . (b) A relac¸a˜o em {a, b, c, d} representada pela matriz 1 1 1 0 0 1 0 1 0 0 1 0 0 0 0 1 . (c) A relac¸a˜o em {1, 2, 3} representada pela matriz 1 1 1 0 1 0 1 0 1 . 13. Fac¸a o grafo das relac¸o˜es do exerc´ıcio anterior. 14. Verifique se as relac¸o˜es dadas abaixo sa˜o relac¸o˜es de ordem parcial. Justifique suas respostas. (a) Seja S(R) o conjunto de todas as func¸o˜es f : [0, 1] → [0, 1]. A relac¸a˜o R ⊆ S(R)× S(R) e´ definida por fRg ⇐⇒ (∀x ∈ [0, 1])[f(x) ≤ g(x)]. (b) Seja B = P({1, 2, 3}). Para dois conjuntos C,D ∈ P({1, 2, 3}), definimos a relac¸a˜o R por: C RD se C = ∅ ou se C,D 6= ∅ e max{i : i ∈ C} ≤ max{i : i ∈ D}. 15. Quais dos pares de elementos dados abaixo sa˜o compara´veis no conjunto parcial- mente ordenado (N∗, | ) com | a relac¸a˜o de divisibilidade? Justifique. (a) 5 e 15 (b) 6 e 9 (c) 8 e 16 (d) 7 e 17 (e) 10 e 15. 16. Determine dois elementos na˜o compara´veis nos conjuntos parcialmente ordenados abaixo. (a) (P({0, 1, 2}),⊆) (b) ({1, 2, 4, 6, 8}, | ). 17. Seja R ⊆ Z× Z a relac¸a˜o definida por: (a, b) ∈ R⇐⇒ (∃ t ∈ N∗) b = at. (a) Mostre que R e´ uma relac¸a˜o de ordem parcial em Z. (b) (Z, R) e´ um conjunto totalmente ordenado? 18. Seja S uma relac¸a˜o em R× R = R2 definida por: ((a, b), (c, d)) ∈ S ⇐⇒ a ≤ c ou b ≤ d. (a) S e´ funcional? S e´ sobrejetora? (b) S e´ uma relac¸a˜o de ordem parcial ? 19. Seja (A,R) um POSET. Mostre que ( A,R−1 ) e´ um POSET.
Compartilhar