provas 2015_1

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 – 2015-1 
 
Aluno(a):_____________________________________________________________________ Data: 10/03/2015 
 
 
1. (1p) As linhas críticas permitem avaliar a validade de um argumento usando tabelas verdade. Explique o que são as 
linhas críticas e como é feita a avaliação, coloque um exemplo. 
 
2. (3p) Com o uso de letras para denotar as sentenças componentes, traduza as seguintes sentenças compostas para notação 
simbólica: 
Exemplo: 
Ou Janet irá vencer ou, se Janet perder, ficará cansada. 𝑝 (¬𝑝  𝑟) 
 p ¬p r 
 
a) Tanto ir para cama como nadar é condição suficiente para trocar de roupa; no entanto, trocar de roupa não significa 
que se vai nadar. 
b) Ou vai chover ou vai nevar, mas não ambos. 
c) Se Janet vencer ou perder, ela estará cansada. 
 
3. (3p) Usando as Regras de Inferência da lógica proposicional, prove que os argumentos são válidos. Use os símbolos 
proposicionais indicados. 
Exemplo: “Não está fazendo sol esta tarde e está mais frio do que ontem. Nós iremos nadar somente se fizer sol. Se nós 
não formos nadar, então nós vamos velejar. Se nós formos velejar, então estaremos em casa no final da tarde. Portanto, 
estaremos em casa no final da tarde” 
 
Representando o argumento de forma simbólica Prova usando regras de inferência 
 
p: “Está fazendo sol esta tarde” 
q: “Está mais frio do que ontem” 
r: “Nós iremos nadar” 
s: “Nós iremos velejar” 
t: “Estaremos em casa no final da tarde” 
¬𝑝 ∧ 𝑞, 𝑟 → 𝑝, ¬𝑟 → 𝑠, 𝑠 → 𝑡 ⊢ 𝑡 
 
1. ¬𝑝 ∧ 𝑞 
2. ¬𝑝 
3. 𝑟 → 𝑝 
4. ¬𝑟 
5. ¬𝑟 → 𝑠 
6. 𝑠 
7. 𝑠 → 𝑡 
8. 𝑡 
 
Hipótese 
1,Simplificação 
Hipótese 
2, 3Modus Tollens 
Hipótese 
4,5 Modus Ponens 
Hipótese 
6,7 Modus Ponens 
 
a) A colheita é boa, mas não há água suficiente. Se tivesse bastante água ou não tivesse bastante sol, então haveria 
água suficiente. Portanto, a colheita é boa e há bastante sol. (C, A, H, S) 
b) Não é verdade que se as taxas de eletricidade subirem, o consumo diminuirá, nem é verdade que novas usinas de 
energia serão construídas ou as contas não serão atrasadas. Portanto o consumo não diminuirá e as contas serão 
atrasadas. (T, C, U, Co) 
 
4. (3p) Provar (usar qualquer método de prova: direta ou contraposição ou contradição). 
Exemplo: “Se 𝑛 é par então 𝑚 = 𝑛 + 5 é ímpar”. Simbolicamente 𝑝: 𝑛 é 𝑝𝑎𝑟 e 𝑞: 𝑚 é í𝑚𝑝𝑎𝑟 
Prova direta Prova Contraposição Prova Contradição 
Afirmar 𝑝 e 
chegar a 𝑞. 
 
𝑝 
..... 
..... 
𝑞 
Negar 𝑞 e chegar a 
não 𝑝. 
 
¬𝑞 
..... 
..... 
¬𝑝 
Afirmar 𝑝, negar 𝑞 e 
chegar a um absurdo 
ou contradição. 
𝑝 
¬𝑞 
..... 
𝑟 ∧ ¬𝑟 
1. 𝑛 é par 
2. 𝑛 = 2𝑘, para 𝑘 ∈ ℤ 
3. 𝑚 = 2𝑘 + 5 
4. 𝑚 = 2(𝑘 + 2) + 1 
5. 𝑚 é ímpar. 
 
1. 𝑚 é par 
2. 𝑛 + 5 = 2𝑘, para 𝑘 ∈ ℤ 
3. 𝑛 = 2𝑘 − 5 
4. 𝑛 = 2(𝑘 − 3) + 1 
5. 𝑛 é ímpar. 
 
1. 𝑛 é par 
2. 𝑚 é par 
3. 𝑚 = 2𝑘 + 5, para 𝑘 ∈ ℤ 
4. 𝑚 = 2(𝑘 + 2) + 1 
5. 𝑚 é ímpar 
6. Contradição linhas 2 e 5!! 𝑞 ∧ ¬𝑞, 
não devia ter negado 𝑞! 
a) Se dois inteiros são ambos divisíveis por um inteiro n, então a sua soma é divisível por n. 
b) Prove que a soma de um inteiro e do seu quadrado é par. 
 
UNIVERSIDADE TECNOLÓGICA FEDERAL DO PARANÁ 
Campus Pato Branco 
ENGENHARIA DE COMPUTAÇÃO 
 
Prova Parcial 2 
 Matemática Discreta para Computação – 2015-1 
 
Aluno(a):_____________________________________________________________________ Data: 26/03/2015 
 
 
1. (1,5p) Utilize diagramas de Venn para determinar se os argumentos são válidos: 
a) Nenhum abstêmio é médico, todos os traumatologistas são médicos; consequentemente, nenhum traumatologista 
é abstêmio. 
b) Nenhum politico é mártir; como mostrado pelo fato que, nenhum politico é idealista, e, todos os mártires são 
idealistas. 
c) Alguns pobres são ególatras; admitindo que, todos os artistas são ególatras, e, alguns pobres são artistas. 
 
2. (0,5) Para as seguintes proposições utilize a regra de instanciação universal, como também o Modus ponens ou o Modus 
tollens para preencher o que esta faltando e obter um argumento válido. 
a) Todos os retângulos são eqüiângulares, ................................................................................................; 
portanto, o quadrilátero MNPQ não é um retângulo. 
(O universo compreende todos os quadriláteros do plano) 
 
b) Nenhuma função polinomial tem assíntota horizontal; A função 𝑔(𝑧) tem assíntota horizontal; 
consequentemente, ........................................................................................................................... 
(O universo compreende todas as funções) 
 
3. (2p) Negar as seguintes expressões da lógica de predicados, 
a) ∃𝑥𝑀(𝑥) → ∃𝑦¬𝑇(𝑦) 
b) ∃𝑥𝐴(𝑥) ∧ ¬𝐵(𝑦) 
c) ∀𝑥(𝑈(𝑥) → 𝐽(𝑥)) 
d) ∀𝑥¬𝑃(𝑥) → ∃𝑦𝑄(𝑦) 
 
4. (2p) Expresse as seguintes sequências de inteiros com uma fórmula explícita 
a) 2, 3, 7, 25, 121, 721, 5041, 40321 ...... 
b) 1, 1/2, 1/4, 1/8, 1/16, .............. 
 
5. Prove usando indução matemática: 
a) (2p) 𝑎 + 𝑎𝑟 + 𝑎𝑟2 + ⋯ + 𝑎𝑟𝑛−1 =
𝑎(1−𝑟𝑛)
1−𝑟
 para 𝑟 ≠ 1, 𝑛 ≥ 1 
b) (2p) 2𝑛 > 𝑛 para qualquer inteiro positivo 𝑛 
 
 
Diagramas de Venn das proposições categóricas 
 
 
 
 
 
UNIVERSIDADE TECN OLÓGICA FEDERAL DO PARANÁ 
Campus Pato Branco 
ENGENHARIA DE COMPUTAÇÃO 
 
Prova Parcial 3 Matemática Discreta para Computação – 2015-1 
 
Aluno(a):_____________________________________________________ Data: 16/04/2015 
 
1. (3,5p) A enumeração, contagem de objetos com certas propriedades, é uma parte 
importante da análise combinatória. Dependo do que deve ser contado, pode-se usar, por 
exemplo: 
a) Permutação 
b) Combinação 
c) Principio de Pombal 
Defina cada um deles e apresente um exemplo para ilustrar o conceito. 
 
2. (1p) Quantos inteiros positivos entre 100 e 999 (inclusive): 
a) São divisíveis por 3 ou 4? 
b) São divisíveis por 3 e 4? 
c) Não são divisíveis nem por 3 nem por 4? 
 
3. (1,5p) Um palíndromo é uma sequência no qual o seu inverso é idêntico à sequência. 
Quantas cadeias de bits de extensão n são palíndromos? (Exemplo de palíndromo sobre o 
português: "Socorram-me, subi no ônibus em Marrocos". Exemplo de palíndromo de 
cadeia de bits de extensão 3: 000, 111, 010, 101) 
 
4. (1,25p) A figura a seguir representa algumas ruas dentro de uma cidade. Existem 
diferentes formas para ir do ângulo inferior (denominado Sudoeste) ao ângulo oposto 
superior (denominado Nordeste). Suponha que as únicas rotas permitidas de percurso são 
direção leste e direção norte. Quantos caminhos possíveis existem? (As linhas escuras 
representam um possível caminho). 
 
 
 
 
 
 
 
5. (1,5p) Quantas soluções inteiras não negativas distintas existem para a equação: 
 
𝑥1 + 𝑥2 + 𝑥3 + 𝑥4 = 10 
Onde a solução 
𝑥1 = 3, 𝑥2 = 1, 𝑥3 = 4, 𝑥4 = 2 e 
𝑥1 = 4, 𝑥2 = 2, 𝑥3 = 3, 𝑥4 = 1 são consideradas distintas. 
 
6. (1,25p) Qual é o número mínimo de estudantes, vindos dos 50 estados americanos, que 
devem ser inscritos em uma universidade para garantir que pelo menos 100 venham do 
mesmo estado? 
NE 
SO 
 
UNIVERSIDADE TECNOLÓGICA FEDERAL DO PARANÁ 
Campus Pato Branco 
ENGENHARIA DE COMPUTAÇÃO 
 
Prova Parcial 4 
 Matemática Discreta para Computação – 2015-1 
 
Aluno(a):________________________________________________________________________ Data: 21/05/2015 
 
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. O conjunto de todos os inteiros ímpares 
b. { - 9,- 7 , - 5 , - 4 , - 1 , 0, 1, 3, 5, 7, 9} 
c. {𝑥|(∃𝑦)(𝑦 ∈ ℤ e 𝑦 ≥ 2 e 𝑥 = 6𝑦)} 
 
2. (2p) Seja: 
𝐴 = {𝑥|𝑥 ∈ ℕ 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. (2p) Para a função 𝑓: ℝ2 → ℝ2 (reais para os reais), definida pela equação abaixo, VERIFIQUE se é Injetora; 
Sobrejetora; Bijetora. Encontre a inversa se possível: 
 
𝑓(𝑥, 𝑦) = (𝑦 + 1, 𝑥 + 1) 
4. (1,5p) Dê um exemplo de uma função 𝑓: ℕ → ℕ (dos naturais para os naturais) que seja injetora mas não sobrejetora. 
JUSTIFIQUE. 
 
5. (2p) Determine se a relação R a seguir, no conjunto S, é: Reflexiva, Simétrica e Transitiva. 
 
𝑆 = {𝑥/𝑥 é um aluno da sua sala} e 𝑎𝑅𝑏 ↔ 𝑎 senta na mesma fileira que 𝑏 
6. (1,5p) Para a relação representada pelo dígrafo abaixo: 
a. Represente em matriz 
b. Determine se a relação é uma Relação de Equivalência. 
c. Encontre 𝑅 ∘ 𝑅 
 
 
UNIVERSIDADE TECNOLÓGICA FEDERAL DO PARANÁ 
Campus Pato Branco 
ENGENHARIA DE COMPUTAÇÃO 
 
Prova Parcial 5 
 Matemática Discreta para Computação – 2015-1 
 
Aluno(a):_____________________________________________________________________ Data: 11/06/2015 
1. (2p) Para quais valores de n estes grafos serão bipartidos? JUSTIFIQUE. 
a. Kn b. Cn c. Wn 
 
2. (1,5p) Represente o grafo dirigido da Figura 1 por uma lista de adjacência. 
 
3. (2,5p) A Figura2 é a planta da residência do bilionário Van Diamond, que acaba de ser assassinado. Sherlock Gomes (um 
conhecido detetive que nas horas vagas é um estudioso da Teoria de Grafos) foi chamado para investigar o caso. O 
mordomo alega ter visto o jardineiro entrar na sala da piscina (lugar onde ocorreu o assassinato) e logo em seguida deixar 
aquela sala pela mesma porta que havia entrado. O jardineiro, contudo, afirma que ele não poderia ser a pessoa vista pelo 
mordomo, pois ele havia entrado na casa, passado por todas as portas uma única vez e, em seguida, deixado a casa. 
Sherlock Gomes avaliou a planta da residência (conforme figura) e em poucos minutos declarou solucionado o caso. 
a. Quem poderia ser o suspeito indicado por Sherlock Gomes? 
b. Faça o Grafo e utilize a teoria dos grafos para justificar a solução do problema. 
 
 
 
 
 
 
Figura 1 
 
 
 
Figura 2 
 
4. (2p) Determine se os grafos U e V da Figura 3 são isomorfos. Justifique apresentando as funções de vértice e de aresta: 
𝑓: 𝑉(𝑈) → 𝑉(𝑉) 𝑒 𝑔: 𝐸(𝑈) → 𝐸(𝑉) 
Ou forneça um argumento rigoroso para provar que não existe isomorfismo. 
 
5. (2p) Para o grafo dirigido da Figura 4 determine se existe um circuito euleriano, se ele existir construa o circuito 
euleriano. Determine se tem trajeto euleriano, se ele existir construa o trajeto euleriano. 
 
 
 
Figura 3 
 
 
 
Figura 4 
 
U 
V