Resolução de Exercícios

Pontifícia Universidade Católica do Rio Grande do Sul Data05062024 Escola Politécnica Matemática Discreta Professor Iuri Jauris Nome Prova 2 LEIA COM ATENÇÃO AS INSTRUÇÕES A SEGUIR Esta prova é INDIVIDUAL Esta avaliação será presencial e deverá ser feita na aula do dia 1206 Questões discursivas e encerramento do horário estipulado Esta avaliação deve ser resolvida totalmente a mão Não será aceita prova resolvida em uma mesa digitalizadora Word etc que digitalizam fórmulas e equações como também a utilização de programas que digitalizam fórmulas e equações Após o final do prova não será aceite entrega da prova Q1 15 Considere as relações R S e T a seguir contidas em A X B sendo A 0 2 4 B 1 2 3 Escreva o que se pede Determine o domínio e a imagem de cada uma das relações Classifique as relações como um para um ou um para muitos ou muitos para um ou muitos para muitos a R A X B tal que xRy y x 1 b S A X B tal que xSy x y c T A X B tal que xTy y x 1 Q2 15 Sejam S e W as relações de R em R definidas por S x y y x 1 W x y x 1 ou y x² x 2 a Represente graficamente em gráficos cartesianos as relações S e W b Represente graficamente a relação S W Q3 10 Considere a relação T R X R definida por x T y x² y² 1 a Qual é o domínio e contradomínio e a imagem dessa relação b Essa é uma relação funcional Se sim então responda A função será injetora Sobrejetora Bijetora A inversa será funcional Q4 20 Seja A 1 2 3 4 Verifique se as relações definidas em A dadas a seguir possuem as propriedades reflexivas simétricas antisimétricas ou transitivas e diga qual ou quais formam relações de equivalência ou relações de ordem Assinale com S de sim ou N de não R1 1 2 2 3 21 3 1 4 4 Transitiva Rel Equivalência Rel Ordem Reflexiva Antisimétrica Simétrica R2 1 2 3 4 1 3 Antisimétrica Simétrica Transitiva Rel Equivalência Rel Ordem R3 11 2 2 3 4 1 2 3 1 Reflexiva Antisimétrica Simétrica Transitiva Rel Equivalência Rel Ordem R4 1 1 2 2 3 3 4 4 1 4 Transitiva Rel Ordem Reflexiva Antisimétrica Simétrica Q 5 10 Verifique se a relação R N x N definida como xRy x y é par é uma relação de equivalência Lembrete Uma provademonstração NÃO PODE ser construída através de exemplos Q6 20 Seja A 8 7 5 3 2 0 1 2 4 6 7 9 e considere a relação de equivalência R em A como y R x x y mod 4 a Descreva quais as classes dessa relação e também quais os elementos de A pertencem a cada classe de equivalência dessa relação b Construa um GRÁFO para essa relação R Q7 10 Considere a relação de ordem R de A X A definida por x R y xy sendo o conjunto A 2 6 8 10 12 16 a Construa a digrafçao de Hasse dessa relação de ordem b Esta é uma relação de ordem parcial ou total Justifique BOA PROVA Matemática Discreta Q1 A 0 2 4 B 1 2 3 a R A x B tal que xRy y x 1 Para y 1 temos 1 0 1 1 0 2 e 1 0 4 Não temos pares da forma x 1 Para y 2 temos 2 0 1 2 2 2 e 2 4 1 Temos um par 0 2 Para y 3 3 0 1 3 2 1 e 3 4 1 Temos um par 0 3 Logo os pares ordenados que satisfazem R são 0 2 e 0 3 Além disso temos que DomR 0 ImR 2 3 e a relação é classificada como um para muitos b S A X B tal que xSy x y Temos que 0 não divide x para todo y B Já o número 2 divide 2 e 4 não divide ninguém Logo o único par orde nado é 2 2 Assim DomS 2 ImS 2 e S é uma relação um para um c T A x B tal que xTy x y é par Como todo elemento de A é par temos que xT y y é par Logo os pares ordenados que satisfazem T são 0 2 2 2 e 4 2 Assim DomT A ImT 2 e T é uma relação muitos para um Q2 S R x R tal que xSy y x² e W R x R x1u2 xWy y x 2 a Para representar graficamente as relações vamos esboçar os gráficos y x² e y x 2 e demarcar os pontos que satisfazem as relações b S W S W satisfaz as duas relações ao mesmo tempo c S W S W são os pontos em que y x² e y x 2 Q3 T R x R tal que xT y y x² 1 a O domínio e o contradomínio de T são R Vamos determinar a imagem Temos que para todo x R x² 0 x² 1 1 ImT y R y 1 b A relação T é funcional pois cada x se relaciona com apenas um y No entanto T não é injetora Vejamos um contraexemplo temos que 1² 1 2 1² 1 1T2 e 1T2 mas 1 1 Além disso a relação não é sobrejetora pois ImT R Por fim como T não é injetora também não é bijetora e sua inversa não será funcional Q4 R1 12 23 22 31 44 N Reflexiva Não temos o par 11 N Antissimétrica 1R1 2 e 2R1 1 mas 1 2 N Simétrica 2R3 mas não temos 3R2 N Transitiva 1R1 2 e 2R1 3 mas não temos 1R1 3 N Rel de Equiv N Rel de Ordem Não é transitiva R2 12 23 34 13 N Reflexiva Não temos 11 S Antissimétrica N Simétrica Temos 12 mas não temos 21 N Transitiva Temos 23 e 34 mas não temos 24 N Rel Equiv N Rel Ordem R3 11 22 33 44 22 91 S Reflexiva N Antissimétrica Temos 12 e 21 com 1 2 S Simétrica S Transitiva S Rel Equiv N Rel Ordem R4 11 22 33 44 12 34 S Reflexiva S Antissimétrica N Simétrica Temos 12 mas não temos 21 S Transitiva N Rel Equiv N Rel Ordem Q5 A relação R N x N tal que xR y x y é par é uma relação de equivalência Vejamos Reflexividade Para todo x N temos x x 2x x x é par xR x Simetria para todo x N e todo y N temos x y é par y x é par pois x y y x Comutatividade da adição em N Transitividade Se xR y e yR z então x y é par e y 2 é par Logo x y y z é par x 2y z 2k 2k z 2k1 2z xR z Q6 A 8 7 5 3 2 1 0 1 2 4 6 7 9 e 2 R y x y mod k a As classes de equivalência são o 8 0 4 Resto 4 1 7 3 1 5 9 Resto 1 2 2 2 6 Resto 2 7 5 1 7 Resto 3 b O grafo sera a relacao bse e somente se aRb Q7 A 2 6 8 10 12 16 e 2R9 xLy a O diagrama de Hasse sera 12 16 6 8 10 2 b Esta e uma relacao de ordem parcial pois alguns pares nao sao comparaveis Por exemplo 10 12 e 12 1o logo 10 12 e R e 12 10 e R