·

Engenharia de Computação ·

Matemática Discreta

Send your question to AI and receive an answer instantly

Ask Question

Preview text

Trabalho 3 Nomes Data22052023 LEIA COM ATENÇÃO AS INSTRUÇÕES A SEGUIR Este trabalho poderá ser realizado em duplas ou trios Não deverá ser individual A entrega desta avaliação será unicamente presencial e deverá ser feita durante a aula do dia 2405 Questões sem resoluçãodesenvolvimento serão anuladas Esta avaliação deverá ser resolvida totalmente a mão Não será aceito trabalho resolvido em mesa digitalizadora ou programas que digitalizam fórmulas e equações como equation mathtype word etc Após o final do prazo não será aceito entregar este trabalho Q1 20 Seja A 3 5 7 De exemplos se possível de relações que satisfaçam as condições a baixo Se não for possível justifique a R1 a relação que só possua as propriedades simétrica e antisimétrica b R2 a relação que seja só antisimétrica e transitiva mas não reflexiva c R3 a relação seja não seja nem simétrica nem transitiva d R4 a relação que só possua as propriedades reflexiva e simétrica mas não transitiva Q2 20 Seja A 2 4 6 8 Verifique se as relações definidas em A dadas a seguir possuem as propriedades reflexiva simétrica antisimétrica e transitiva e qual ou quais formam relações de equivalência ou relações de ordem Assinale com S de sim ou com N de não a R1 2 4 4 2 2 2 Reflexiva Antisimétrica Simétrica Transitiva Rel Equivalência Rel Ordem b R2 2 2 4 4 6 6 8 8 2 4 4 6 6 8 Reflexiva Antisimétrica Simétrica Transitiva Rel Equivalência Rel Ordem c R3 2 2 4 4 6 6 2 4 2 6 2 8 Reflexiva Antisimétrica Simétrica Transitiva Rel Equivalência Rel Ordem d R4 4 4 6 6 8 8 46 68 86 Reflexiva Antisimétrica Simétrica Transitiva Rel Equivalência Rel Ordem Pontifícia Universidade Católica do Rio Grande do Sul Escola Politécnica Matemática Discreta Professor Iuri Jauris Q3 20 Seja A 9 6 5 3 2 1 0 1 2 4 7 10 11 12 e definida a relação binária R em A como 𝑥 𝑦 𝐴 𝑥𝑅𝑦 𝑥 𝑦𝑚𝑜𝑑 9 a Quais são as classes de equivalência dessa relação em A b Descreva os elementos de A que pertencem a cada classe Q4 10 Seja a relação R definida por a b c d R a d b c PROVE que R é uma relação de equivalência Lembrete Uma prova NÃO PODE ser construída através de exemplos Q5 Considere a relação R de zx z definida por x R y xy 10 a Prove que R é uma relação ordem em zx z 10 b Considere a mesma relação R de ordem acima porém agora de B x B sendo o conjunto B 1 5 9 15 18 45 Esta relação é uma relação de ordem total ou parcial em B Justifique 05 c Considere a relação R de ordem acima no conjunto B 1 5 9 15 18 45 Construa o diagrama de Hasse representativo dessa relação 05 d Crie um subconjunto B z com 5 elementos de forma que a relação R nesse subconjunto que você criou seja uma relação de ordem total BOM TRABALHO Q2 a N Reflexiva Pois 44 R1 N Antisimétrica Pois 24 e 42 R1 e 2 4 S Simétrica Pois 24 R1 42 R1 e 22 R1 22 R1 N Transitiva Pois 42 e 24 R1 mas 44 R1 N Rel Equivalência Pois não é reflexiva N Rel Ordem Pois não é reflexiva b S Reflexiva Pois 22 44 66 e 88 R2 S Antisimetrica Pois não existe abba R2 com a b N simétrica Pois 24 R2 e 42 R2 N Transitiva Pois 24 46 R2 mas 26 R2 N Rel Equivalência Pois não é Transitiva N Rel Ordem Pois não é transitiva Q1 a Não é possível sem R1 ser também transitiva pois como R1 é simétrica e antisimétrica então se ab R1 entã ba R1 e ab Logo todos elementos de R1 tem a forma aa donde ela é transitiva b R2 33 c R3 3557 d R4 33557735533773 é reflexiva e simétrica e não transitiva pois 53 e 37 R4 mas 57 R4 c N Reflexiva Pois 88 R3 S Antisimétrico Pois não existem ab e ba R3 com a b N Simétrica Pois 24 R3 e 42 R3 S Transitiva Pois não existem ab e bc R3 com ac R3 N Rel Equivalência Pois não é reflexiva N Rel Ordem Pois não é reflexiva d N Reflexiva Pois 22 R4 N Antisimétrica Pois 68 e 86 R3 e 6 8 N Simétrica Pois 96 R3 e 64 R3 N Transitiva Pois 46 e 68 R3 mas 48 R3 M Rel Equivalência Pois não é reflexiva N Rel Ordem Pois não é reflexiva Q3 a 0 1 2 12 4 3 7 1 b 0 90 1 110 2 211 12 612 4 54 3 3 7 27 1 1 Q4 Vamos provar cada uma das propriedades Reflexividade Veja pela comutatividade da soma que a b b a abab R ab Simetria Veja que se abcd R então a d b c b c a d c b d a cdab R Transitividade Se abcd R e cdef R então a d b c c f d e a d c f b c d e a f b e abef R Q5 a Não é uma relação de ordem pois não é antisimétrica já que 55 logo 55 R e 55 logo 55 R mas 5 5 e assim não é antisimétrica b Primeiro neste caso é de ordem pois é reflexiva já que xx x ℤ então em particular x B logo xx R É transitiva pois se xy e yz então xz xyz ℤ logo vale que xyyz R xz R E é antissimétrica pois B só tem inteiros positivos daí se xy e yx xy logo R é antisimétrica Essa relação de ordem é parcial pois dados 15 e 38 B 1538 e 3815 logo 1538 R e 3815 R c diagram with numbers and lines connecting them 45 top connected to 15 and 38 15 connected to 5 38 connected to 9 5 and 9 connected to 1 d Basta tomarmos 2481632B assim a relação em B é de ordem total pois dados dois números sempre um deles divide o outro