Prova 1 com gabarito

Prévia do material em texto

FUNDAÇÃO UNIVERSIDADE FEDERAL DO VALE DO SÃO FRANCISCO 
COLEGIADO DE ENGENHARIA DE COMPUTAÇÃO 
DISCIPLINA: MATEMÁTICA DISCRETA 
Revisão da 1ª AVALIAÇÃO – 2013.1 
 
Questões 
 
1 - Usando regras de inferência e equivalências notáveis prove a validade do seguinte argumento: 
A colheita é boa mas não há água suficiente. Se houver muita chuva ou se não houver muito sol então 
haverá água suficiente. Portanto a colheita é boa e há muito sol. 
Usar as notações: C: A colheita é boa. A: Há água suficiente. V: Há muita chuva. S: Há muito sol. 
 
1. C ^ A’ hipótese 
2. (V v S’) →→→→ A hipótese 
3. A’ 1, sim 
4. A’ →→→→ (V v S’)’ 2, cont 
5. (V v S’)’ 3, 4, mp 
6. V’ ^ (S’)’ 5, De Morgan 
7. V’ ^ S 6, dn 
8. S 7, sim 
9. C 1, sim 
10. C ^ S 8, 9, con 
 
2 - Use a lógica proposicional para provar que o argumentos abaixo é válido. Deixe claro as regras 
utilizadas. 
[A →→→→ (B →→→→ C)] ^ (A v D’) ^ B →→→→ (D →→→→ C) 
1. A → (B → C) hipótese 
2. A v D’ hipótese 
3. B hipótese 
4. D hipótese 
5. D’ v A 2, com 
6. D → A 5, imp 
7. A 4, 6, mp 
8. B → C 1, 7, mp 
9. C 3, 8, mp 
 
3 – Usando os símbolos predicados indicados e quantificadores apropriados, escreva cada declaração 
 em português como uma fbf predicada: 
U = mundo inteiro. 
A(x): x é abelha. 
F(x): x é flor. 
G(x,y): x gosta de y. 
a) Todas as abelhas gostam de todas as flores. (∀x)[A(x) → (∀y)(F(y) → G(x,y))] ou (∀x)(∀y)[(A(x) ^ F(y)) → G(x,y)] 
b) Algumas abelhas gostam de todas as flores. (Ǝx)[A(x) ^ (∀y)(F(y) → G(x,y))] 
c) Todas as abelhas gostam de algumas flores. (∀x)[A(x) → (Ǝy)(F(y)^G(x,y))] 
d) Algumas abelhas gostam de algumas flores. (Ǝx) [A(x) ^ (Ǝy)(F(y)^G(x,y))] ou (Ǝx)(Ǝy) [A(x)^(F(y)^G(x,y))] 
 
 
 
4 - Prove a seguinte proposição, usando alguma das técnicas de demonstração. 
Se dois inteiros são divisíveis por k, então sua soma é divisível por k. 
 
Sejam x e y divisíveis por n. 
Então x = k1.n e y = k2.n, onde k1 e k2 são inteiros. 
x + y = k1.n + k2.n = (k1 + k2).n, onde k1 + k2 são inteiros. 
Portanto x + y são divisíveis por n. 
 
5 - Use a indução matemática para provar que 1+ + + + 5+ + + + 9+ + + + ...+ + + + (4n − − − − 3) = = = = n(2n −−−−1) 
 
 P(1): 1 = 1(2(1) – 1) verdade 
 Assuma P(k): 1 + 5 + 9 + ... + (4k – 3) = k(2k -1 ) 
 Mostre P(k +1): 1 + 5 + 9 + ... + [4(k + 1) – 3] = (k + 1)[2(k + 1) – 1] 
 
 1 + 5 + 9 + ... + [4(k + 1) – 3] lado esquerdo de P(k + 1) 
 = 1 + 5 + 9 + ... + (4k – 3) + [4(k + 1) – 3] 
 = k(2k -1) + 4(k + 1) – 3 usando P(k) 
 = 2k² - k + 4k + 1 
 = 2k² + 3k + 1 
 = (k + 1)(2k + 1) 
 = (k + 1)[2(k + 1) – 1] lado direito de P(k + 1) 
 
 
6 - Prove a propriedade dada dos números de Fibonacci diretamente da definição. 
 
[F(n+1)]2=[F(n)]2+F(n-1)F(n+2) para n ≥ 2≥ 2≥ 2≥ 2 
 
 
 
[F(n +1)]² = [F(n – 1) + F(n)]² 
 
 
 
 
 
 
 
 
 = [F(n-1)]² + 2F(n – 1)F(n) + [F(n)]² 
 = F(n – 1)[ F(n – 1) + F(n) + F(n) + [F(n)]² 
 = F(n – 1)[ F(n + 1) + F(n) + [F(n)]² 
 = F(n – 1)[ F(n + 2) + [F(n)]²