·

Engenharia da Computação ·

Matemática Discreta

Send your question to AI and receive an answer instantly

Ask Question

Preview text

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