Avaliação 3-2021 2

UNIVERSIDADE FEDERAL DO CEARÁ - CAMPUS DE CRATEÚS CURSO: CIÊNCIA DA COMPUTAÇÃO e SISTEMAS DE INFORMAÇÃO DISCIPLINA: MATEMÁTICA DISCRETA PROFESSORA: LÍLIAN DE OLIVEIRA CARNEIRO AVALIAÇÃO 03 Orientações: ♣ Faça o download da avaliação. Caso algum imprevisto aconteça você terá acesso ao documento sem precisar de Internet; ♣ Resolva a avaliação em uma folha de seu caderno ou em papel A4 ou em papel almaço. Não aceitarei respostas digitadas; ♣ As questões devem ser resolvidas com caneta para que as fotos ou a digitalização saiam com uma boa qualidade (existem alguns aplicativos que fazem digitalização, como o Google Drive). Caso faça à lápis, garanta que as questões fiquem legíveis; ♣ Indique a qual questão cada resposta está associada; ♣ Vocês devem escrever a demonstração em detalhe, destacando as definições empregadas, as propriedades, quando as hipóteses estão sendo usadas e até mesmo o uso de artifícios matemáticos, se for o caso. Não apresente apenas o rascunho; ♣ Digitalize ou tire foto de cada uma das resposta, nomeando o arquivo. Exemplo: Q1.a-b-c-d (indicando que o arquivo possui os itens a), b) c) e d) da Questão 1). Após concluir a sua avaliação envie-a pelo Portfolio do Solar; ♣ Durante a correção da avaliação o aluno pode ser solicitado a explicar as suas resoluções. QUESTÕES 1. Determine se as seguintes afirmações são verdadeiras (V) ou falsas (F). Se a afirmação for verdadeira, demonstre-a; se for falsa, apresente um contra-exemplo. (1,5) a) A relação R = {(x, y) ∈ Z2|x < y} é simétrica. ( ) b) Sejam R e S são relações sobre um conjunto A. Se R e S são transitivas, então R ∩ S também é transitiva. ( ) c) A matriz   1 0 1 0 1 1 1 0 1   representa uma relação de equivalência. ( ) d) O grafo orientado abaixo representa uma relação de ordem parcial. ( ) e) A sequência de vértices 1 − 3 − 6 − 2 − 7 − 3 − 6 − 4 do grafo abaixo representa um caminho nesse grafo. ( ) 2. Seja R uma relação definida por R = {(x, y) ∈ R2 : x − y é racional}. Considere também as relações S = {(1, 3), (1, 4), (2, 3), (2, 4), (3, 1), (3, 4)} e T = {(1, 3), (1, 4), (2, 1), (3, 2)} em A = {1, 2, 3, 4}. (4,3) a) Represente as relações T e S por meio de um grafo; (0,2) b) Represente as relações T e S por meio de uma matriz; (0,2) c) Para cada uma das relações, determine se a relação é reflexiva, simétrica, antissimétrica ou transitiva. Caso a relação satisfaça uma dada propriedade, demonstre-a; em caso contrário, apresente um contraexemplo. (2,4) d) Para cada uma das relações, classifique-a em relação de equivalência ou relação de ordem. Justifique a sua classificação. (0,3) e) Determine o fecho reflexivo, simétrico e transitivo de T e de S. (1,2) 3. Seja A = {2, 3, 4, 6, 18, 24} um conjunto parcialmente ordenado pela relação de divide, |. Faça o que se pede, justificando a sua resposta: (1,2) a) Desenhe o diagrama de Hasse para o poset ({2, 3, 4, 6, 18, 24}, |); (0,2) b) Determine os elementos maximais do poset; (0,4) c) Determine os elementos minimais do poset; (0,4) d) O poset possui um elemento máximo? E mínimo? Justifique. (0,2) 4. Considere o grafo abaixo, onde vi, com i = 1, 2, · · · , 6, são os vértices e ei, com i = 1, 2, · · · , 10, são as arestas. (1,0) Com base em tais informações faça o que se pede, justificando a sua resposta: a) Qual é a ordem desse grafo? (0,2) b) Qual é o grau dos vértices v3? (0,2) c) Este grafo possui vértices isolados? Se sim, indique tais vértices. (0,2) d) O grafo é completo? Por quê? (0,2) e) Apresente um subgrafo do grafo dado. (0,2)