Lista 1 Renato

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

Lista 1 – Álgebra de Boole/Indução e recursão 
1) Demonstre que o argumento a seguir é válido: 
 
A ∧ (B → C) ∧ [(A ∧ B)→(D ∨ C′)] ∧ B → D 
 
2) Usando lógica proposicional, prove a validade do argumento 
[(A ∨ B′) → C] ∧ (C→D) ∧ A → D 
 
DICAS 
Modus pones é a regra mais intuitiva, tente usá-la muitas vezes 
FBF’s do tipo (P ∨ Q)′ ou (P ∧ Q) ′ dificilmente são úteis, aplique as leis de 
Morgan 
FBF’s do tipo P ∨ Q podem ser melhor aproveitadas usando a dupla 
negação 
(P′) ′ ∨ Q para obtermos uma implicação P′ → Q 
 
3) Prove por indução matemática que ∀n ≥ 1, 3 n − 2 é ímpar. 
 
 
4) Prove que x + y’ = x + (x’. y + x . y)’ é válida para qualquer álgebra de Boole. 
Explicite a propriedade usada em cada passo da demonstração. 
 
5) Utilize a notação simbólica da lógica formal para representar as seguintes 
expressões. 
1. Tanto ir dormir como ir nadar é uma condição suficiente para a 
troca de roupa; além disso, mudar a roupa não significa que se vai 
nadar. 
2. Se Jane vencer ou perder, ela vai ficar cansada. 
3. Ou Jane irá vencer ou, se perder, ela ficará cansada. 
4. Vai chover ou nevar, mas não ambos. 
 
A: ir dormir 
B: ir nadar 
C: mudar a roupa 
 
6) Construa a tabela-verdade para a seguinte fórmula e verifique se é tautologia 
ou contradição: 
 (A → B) ↔ A′ ∨ B 
 
 
7) Prove que é verdadeira a seguinte Lei de Morgan 
(A ∨ B)′ ⇔ A′ ∧ B′ 
 
 
 
 
 
 
 
8) Prove que as equaçôes: 
 
a) –1 + 3 + 5 + … + (2n - 1) = n² 
b) 2 + 4 + 6 + ... + 2n = n(n+1) 
c) 2 + 6 + 10 + ... + (4n-2) = 2n² 
são verdadeiras para qualquer inteiro positivo n. 
 
 
 
9) Prove que qualquer quantia, para franquia postal, maior ou igual a 8 centavos 
pode ser conseguida usando-se apenas selos de 3 e 5 centavos. 
 
 
 
 
10) Prove por absurdo a proposição: 
“Se um número somado a ele mesmo é igual a ele mesmo, então esse número é 
0.”