Baixe o app para aproveitar ainda mais
Prévia do material em texto
UNIVERSIDADE TECNOLÓGICA FEDERAL DO PARANÁ Campus Pato Branco ENGENHARIA DE COMPUTAÇÃO Prova Parcial 1: Matemática Discreta para Computação – 2016-2 Aluno(a):__________________________________________________________ Data: 14/09/2016 1. (1p) Para determinar a validade de um argumento são usadas tabelas verdade. Para simplificar a análise são identificadas as linhas críticas da tabela verdade: a. O que é uma linha crítica? b. Porque as linhas críticas permitem determinar a validade de um argumento? 2. (1p) Expresse as especificações a seguir usando as proposições “p: O usuário entra com uma senha válida”, “q: O acesso é liberado” e “r: O usuário pagou a taxa de assinatura”, juntamente com conetivos lógicos. a. “O usuário pagou a taxa de assinatura, mas não entra com uma senha válida.” b. “O acesso é liberado sempre que o usuário pagar a taxa de assinatura e entrar com uma senha válida.” c. “O acesso é negado se o usuário não pagou a taxa de assinatura.” 3. (1,5p) Encontre um contraexemplo, se possível, para estas proposições quantificadas universalmente, em que o domínio para todas as varáveis são todos os números inteiros. a. ( ) b. ( ) c. ( ) 4. (2p) Considere ( ) como a proposição “x pode enganar y”, em que o domínio são todas as pessoas no mundo. Use quantificadores para expressar cada uma das proposições: Exemplo: Todos podem enganar Fred: ( ) a. Evelyn pode enganar a todos b. Todos podem enganar alguém c. Não há ninguém que possa enganar a todos d. Todos podem ser enganados por alguém 5. (2p) Dadas estas duas suposições: i: “Lógica é difícil ou não muitos estudantes gostam de lógica” ii: “Se matemática é fácil, então lógica não é difícil” Transcreva as suposições em proposições que envolvam variáveis proposicionais e conectivos lógicos. Determine se cada uma das seguintes conclusões é válida para as suposições (Use regras de inferência e equivalência. Dica: transcreva também as conclusões): a. Matemática não é fácil, se muitos estudantes gostam de lógica. b. Poucos estudantes gostam de lógica, se matemática não é fácil. c. Matemática não é fácil ou lógica é difícil. d. Lógica não é difícil ou matemática não é fácil. 6. (2,5p) Mostre que (indique o tipo de método utilizado): a. Se é um número inteiro e é ímpar então é par b. Se e são números inteiros pares, em que m, n e p são números inteiros, então é par. UNIVERSIDADE TECNOLÓGICA FEDERAL DO PARANÁ Campus Pato Branco ENGENHARIA DE COMPUTAÇÃO Prova Parcial 2: Matemática Discreta para Computação – 2016-2 Aluno(a):_______________________________________________________________ Data: 19/10/2016 1. (1p) Considere os seguintes subconjuntos de ℤ 𝐴 = {𝑥|(∃𝑦)(𝑦 ∈ ℤ e 𝑦 ≥ 4 e 𝑥 = 3𝑦)} 𝐵 = {𝑥|(∃𝑦)(𝑦 ∈ ℤ e 𝑥 = 2𝑦)} 𝐶 = {𝑥|𝑥 ∈ ℤ e |𝑥| ≤ 10} Usando as operações de conjuntos, descreva cada um dos seguintes conjuntos em termos de A, B e C: a. { - 9, - 7, - 5 , - 3, - 1 , 0 , 1, 3, 5, 7, 9} b. {𝑥|(∃𝑦)(𝑦 ∈ ℤ e 𝑦 ≥ 2 e 𝑥 = 6𝑦)} 2. (1p) Sejam: 𝐴 = {𝑥|𝑥 ∈ ℕ e 𝑥 ≥ 5} 𝐵 = {10, 12, 16, 20} 𝐶 = {𝑥|(∃𝑦)(𝑦 ∈ ℕ e 𝑥 = 2𝑦)} Quais das seguintes sentenças são verdadeiras a. 𝐵 ⊆ 𝐶 b. 𝐴 ⊆ 𝐶 c. {11, 12, 13} ⊆ 𝐴 d. {12} ∈ 𝐵 e. {𝑥|𝑥 ∈ ℕ e 𝑥 < 20} ⊈ 𝐵 f. {∅} ⊆ 𝐵 g. 𝐵 ⊂ 𝐴 h. 26 ∈ 𝐶 i. {11, 12, 13} ⊂ 𝐶 j. {12} ⊆ 𝐵 k. 5 ⊆ 𝐴 l. ∅ ∉ 𝐴 3. (0,5p) Determine se cada um dos conjuntos abaixo é contável ou incontável. Para aqueles que forem contáveis, exiba uma bijeção entre o conjunto dos números naturais e o conjunto: a. O conjunto de todos os números racionais positivos que não podem ser escritos com denominadores menores que 4. b. O conjunto dos números reais que não tenha o 0 em sua representação decimal. 4. (1p) De um exemplo de uma função 𝑓: ℕ → ℕ (dos naturais para os naturais) que seja: a. Injetora, mas não Sobrejetora. b. Nem Injetora nem Sobrejetora. 5. (0,5p) Qual é a condição com respeito ao Domínio e a Imagem que devem cumprir duas funções para poder encontrar a função composta 𝑓𝑜𝑔 e 𝑔𝑜𝑓? Coloque um exemplo. 6. (1,5p) Quantas soluções inteiras não negativas distintas existem para a equação: 𝑥1 + 𝑥2 + 𝑥3 + 𝑥4 = 10 Onde as soluções: 𝑥1 = 3, 𝑥2 = 1, 𝑥3 = 4, 𝑥4 = 2 e 𝑥1 = 4, 𝑥2 = 2, 𝑥3 = 3, 𝑥4 = 1 são consideradas distintas. 7. (1p) Qual é o número de estudantes necessário em uma sala de matemática discreta para se ter certeza de que pelo menos seis receberão a mesma nota, se são possíveis cinco notas A, B, C, D e F? 8. (1,5p) Use indução matemática e demonstre que 5 divide 𝑛5 − 𝑛 sempre que 𝑛 for um número inteiro não negativo. 9. (2p) Use a definição de coeficientes binomiais e mostre que se n e k são inteiros positivos com nk 1 , então 12 k kn k n UNIVERSIDADE TECNOLÓGICA FEDERAL DO PARANÁ Campus Pato Branco ENGENHARIA DE COMPUTAÇÃO Prova Parcial 3: Matemática Discreta para Computação – 2016-2 Aluno(a):_______________________________________________________________ Data: 06/12/2016 1. (1p) Definição: Uma relação de equivalência sobre um conjunto A é uma relação R sobre A que é reflexiva sobre A, simétrica e transitiva. Determine se a relação R no conjunto de todos os números reais é uma relação de equivalência se (x,y) ϵ R se e somente se: a) x + y = 0 b) x = ± y 2. (1,5p) Teorema: A relação R em um conjunto A é transitiva se e somente se para n = 1, 2, 3, .... Seja R a relação no conjunto {1, 2, 3, 4, 5} com os pares ordenados (1, 1), (1, 2), (1, 3), (2, 3), (2, 4), (3, 1), (3, 4), (3, 5), (4, 2), (4, 5), (5, 1), (5, 2) e (5, 4). Determine: a) Determine R 2 b) Baseado na resposta de a. A relação R é transitiva? 3. Seja a Relação R representada pelo dígrafo da Figura 1. Represente com uma matriz e: a) (0,5p) Explane como se determina se R é reflexiva ou simétrica usando a representação de matriz. b) (1,5p) R é Transitiva? Se não for utilize o algoritmo de Warshall e encontre o fecho transitivo. Apresente todos os passos. Figura 1 4. (0,5p) Utilize a forma da definição da questão 1 e defina Relação de Ordem Parcial e Relação de Ordem Total. 5. (1p) Para a relação {(a, b)| a divide b} definida no conjunto {1, 2, 3, 4, 6, 8, 12}. Desenhe o dígrafo e o Diagrama de Hasse. 6. (1,5p) Determine se os grafos U e da Figura 2 são isomorfos. Justifique apresentando a função de vértice e de aresta: ( ) ( ) ( ) ( ) Ou forneça um argumento rigoroso para provar que não existe isomorfismo. Figura 2 7. (1p) Teorema de Kuratowski disse que “Um grafo é planar se e somente se não contém nenhum subgrafo homeomorfo a K3,3 ou K5 O que é homeomorfismo? Coloque um exemplo. 8. (1p) Na figura 3 apresenta-se um grafo dirigido. Quais os critérios para determinar se um grafo tem: a) Circuito Euleriano ou Trajeto Euleriano? b) Use os critérios elencados no item (a) e verifique se o grafo tem circuito ou trajeto Euleriano. Figura 3 9. (0,5p) Qual a diferença entre circuito Euleriano e Circuito Hamiltoniano? U V UNIVERSIDADE TECNOLÓGICA FEDERAL DO PARANÁ Campus Pato Branco ENGENHARIA DE COMPUTAÇÃO Prova Substitutiva Matemática Discreta para Computação – 2016-2 Aluno(a):_______________________________________________________________ Data: 13/12/2016 1. (1p) Porque f não é uma função de ℤ para ℝ . Justifique sua resposta baseando-se na definição de função. a. 𝑓(𝑛) = ±𝑛 b. 𝑓(𝑛) = 1/(𝑛2 − 4) 2. (1p) Encontre fog e gof , em que 𝑓(𝑥) = 𝑥2 + 1 e 𝑔(𝑥) = 𝑥 + 2. O que pode dizer respeito da comutatividade da composição de funções? 3. (2p) Determine se as funções a seguir são bijetoras de ℝ para ℝ. Justifique sua resposta baseando-se nas propriedades que devem cumprir as funções para serem bijetoras. a. 𝑓(𝑥) = −3𝑥 +4 b. 𝑓(𝑥) = −3𝑥2 + 7 4. (1p) Determine se a relação 𝑅 no conjunto de todos os números reais é reflexiva, simétrica, anti-simétrica e transitiva, em que (𝑥, 𝑦) 𝜖 𝑅 se e somente se 𝑥𝑦 ≥0. Justifique sua resposta baseando-se na definição de cada propriedade solicitada das relações. 5. (2p) Quais das relações a seguir é um POSET? Justifique sua resposta baseando-se nas propriedades que deve ter um Poset: Seja S é o conjunto de todas as pessoas mundo e R uma relação sobre S, onde (𝑎, 𝑏) ∈ 𝑅 se: a. 𝑎 é mais alto que 𝑏. b. 𝑎 = 𝑏 ou 𝑎 é uma ancestral de 𝑏. 6. (1p) Determine se os grafos da Figura 1 e 2 são bipartidos, caso sejam apresente os dois conjuntos de vértices que verificam a partição. Figura 1 Figura 2 7. (1p) Para os grafos das Figuras 3, 4 e 5: indique para cada um se há trajeto ou circuito euleriano e explane porque existe ou porque não existe. Figura 3 Figura 4 Figura 5 8. (1p) Defina conectividade em grafos não orientados. Baseado em sua definição determine se os grafos da Figura 6, 7 e 8 são conexos. Se não forem, encontre as componentes conexas. Figura 6 Figura 7 Figura 8
Compartilhar