GABARITO 2ª lista de exercícios

Prévia do material em texto

MINISTÉRIO DA EDUCAÇÃO 
UNIVERSIDADE FEDERAL DO PIAUÍ 
CENTRO DE EDUCAÇÃO ABERTA E A DISTÂNCIA 
CURSO DE SISTEMAS DE INFORMAÇÃO 
LÓGICA PARA COMPUTAÇÃO 
 
 
2ª LISTA DE EXERCÍCIOS 
 
 
1. Dadas as expressões da Lógica Proposicional a seguir, encontre: 
a) As expressões correspondentes na Lógica de Boole. 
b) As expressões correspondentes na Teoria dos Conjuntos. 
c) As representações em diagramas de Venn. 
 
(p  q  r) → (p  q ↔ r) 
a) (p  q  r)  (((p  q)  r)  ((p  q)  r))) = (p  q  r) = (p q  r) 
= p’.q’+ r’ 
b) (
p
  
q
  
r
) 
 
c) p q 
 
 
 r 
(p  q ↔ r)  (p→ q  r) 
a) (((p  q)  r)  ((p  q)  r))  (p  q  r) = (p  q  r) = p’+ q. r 
b) (
p
 q  r) 
 
c) 
 
 
 
2. Usando o Princípio de Indução Finita, mostre que as seguintes proposições são verdadeiras 
para todo número inteiro positivo n: 
a) 12 + 32 + . . . + (2n-1) 2 = n (2n – 1) (2n + 1)/ 3 
Condição básica A(1) ou seja, n = 1 temos 1² = 1(2.1 – 1)(2.1 + 1) /3  1 = 1 
Suponha verdadeiro para A(n) e provemos para A(n+1), ou seja, A(n): 12 + 32 + . . . + 
(2n-1)2 = n (2n – 1) (2n + 1)/ 3 então A(n+1) : 12 + 32 + . . . + (2n-1)2 + (2n+1)2 = 
n (2n – 1) (2n + 1)/ 3 + (2n+1)² = (n(2n – 1) (2n + 1) + 3(2n + 1) (2n + 1)) / 3 = 
((2n² – n) (2n + 1) + (6n + 3) (2n + 1))/3 = (2n² - n + 6n + 3) (2n +1) /3 = 
(2n² + 5n + 3) (2n +1) /3 = (n + 1) (2n + 1) (2n + 3)/3, Portanto é verdadeira. 
 
 
 
 
 
b) 2 + 6 + 10 + . . . + (4n – 2) = 2n2 
Condição básica A(1) ou seja, n = 1 temos 4.1- 2 = 2.1²  2 = 2 
Suponha verdadeiro para A(n) e provemos para A(n+1), ou seja, A(n): 2 + 6 + 10 + . . 
. + (4n – 2) = 2n2 então A(n+1): 2 + 6 + 10 + . . . + (4n – 2) + (4n + 2) = 2n2 + (4n + 
2) = 2n2 + 4n + 2 = 2 (n² + 2n + 1) = 2(n + 1)² Portanto é verdadeiro 
 
c) 4 + 10 + 16 + . . . + (6n – 2) = n(3n + 1) 
Condição básica A(1) ou seja, n = 1 temos 6.1- 2 = 1.(3.1 + 1)  4 = 4 
Suponha verdadeiro para A(n) e provemos para A(n+1), ou seja, A(n): 4 + 10 + 16 + . 
. . + (6n – 2) = n(3n + 1) então A(n+1): 4 + 10 + 16 + . . . + (6n – 2) + (6n + 4) = n(3n 
+ 1) + (6n + 4) = 3n2 + n + 6n + 4 = 3n² + 7n + 4 = (n + 1) (3(n + 1) + 1) Portanto é 
verdadeiro. 
 
3. Justifique cada passo na sequência de demonstração a seguir, para a fbf (x)p(x)(x)(p(x) 
→ q(x)) → (x)q(x) 
1 (x)p(x) Premissa 
2 (x)(p(x) → q(x)) Premissa 
3 p(a) Em 1 (x)p(x), logo podemos substituir por uma constante a em x. 
4 p(a) → q(a) Em 2 a implicação vale (x), podemos substituir x pela constante a 
5 q(a) Usando Modus Ponens entre 3 e 4 
6 (x)q(x) Valendo para uma constante a em 5, podemos dizer que (x) 
 
4. Prove que as fbfs a seguir são argumentos válidos: 
a) (∀x)p(x) → (∀x)[p(x) ∨ q(x)] 
1. ((∀x)p(x) → (∀x)[p(x) ∨ q(x)]) negação da fórmula 
2. (∀x)p(x)  ((∀x)[p(x) ∨ q(x)]) negação da  em 1 
3. (∀x)p(x) regra da conjunção R1 em 2 
4. ((∀x)[p(x) ∨ q(x)]) regra da conjunção R1 em 2 
5. (x) (p(x) ∨ q(x)) negação do ∀ em 4 
6. p(a) substituição de x por uma constante a em 3 
7. (p(a) ∨ q(a)) substituição de x por uma constante a em 4 
8. (p(a)) Regra da negação da disjunção (De Morgan) em 7 
9. (q(a)) Regra da negação da disjunção (De Morgan) em 7 
Tableux fechado em 8, portanto o argumento é válido 
 
b) (∀x)p(x) ∧ (x)q(x) → (x)[p(x) ∧ q(x)] 
1. ((∀x)p(x) ∧ (x)q(x) → (x)[p(x) ∧ q(x)]) negação da fórmula 
2. (∀x)p(x) ∧ (x)q(x)  ((x)[p(x) ∧ q(x)]) negação da  em 1 
3. (∀x)p(x) regra da conjunção R1 em 2 
4. (x)q(x) regra da conjunção R1 em 2 
5. ((x)[p(x) ∧ q(x)]) regra da conjunção R1 em 2 
6. (x) [p(x) ∧ q(x)] negação da  em 5 
7. p(a) substituição de x por uma constante a em 3 
8. q(a) substituição de x por uma constante a em 4 
9. [p(a) ∧ q(a)] substituição de x por uma constante a em 5 
 
 
 
 
 
 
10. p(a) q(a) Regra da negação da conjunção (De Morgan) em 9 
 fechado fechado 
Tableux fechado, Portanto o argumento é válido 
 
c) (x)(y)p(x,y) → (y)(x)p(x,y) 
1. ((x)(y)p(x,y) → (y)(x)p(x,y)) negação da fórmula 
2. (x)(y)p(x,y)  ((y)(x)p(x,y)) negação da  em 1 
3. (x)(y)p(x,y) regra da conjunção R1 em 2 
4. ((y)(x)p(x,y)) regra da conjunção R1 em 2 
5. (y)(x) p(x,y) negação da  em 4 
6. p(a,b) substituição de x e y pelas constantes a e b em 3 
7. p(a,b) substituição de x e y pelas constantes a e b em 5 
 fechado 
 Tableux fechado, Portanto o argumento é válido 
 
d) (∀x)(∀y)q(x,y) → (∀y)(∀x)q(x,y) 
1. ((∀x)(∀y)q(x,y) → (∀y)(∀x)q(x,y)) negação da fórmula 
2. (∀x)(∀y)q(x,y)  ((∀y)(∀x)q(x,y)) negação da  em 1 
3. (∀x)(∀y)q(x,y) regra da conjunção R1 em 2 
4. ((∀y)(∀x)q(x,y)) regra da conjunção R1 em 2 
5. (x)(y)q(x,y) negação da  em 4 
6. q(a,b) substituição de x e y pelas constantes a e b em 3 
7. q(a,b) substituição de x e y pelas constantes a e b em 5 
 fechado 
 Tableux fechado, Portanto o argumento é válido 
e) (∀x)p(x) ∧ (x)¬[p(x) → (x)q(x)] 
1. ((∀x)p(x) ∧ (x)¬[p(x) → (x)q(x)]) negação da fórmula 
2.  (∀x)p(x)  ((x)¬[p(x) → (x)q(x)]) negação do  em 1 (De Morgan) 
3. (x)p(x)  (∀x) [p(x) → (x)q(x)]) negação da  e  em 2 
4. (x)p(x)  (∀x)[p(x) → (x)q(x)] dupla negação em 3 
 
5. (x)p(x) (∀x)[p(x) → (x)q(x)] regra da disjunção em 4 
6. p(a) [p(a) → q(a)] substituição de x pela constante a em 5 
 aberto 
7. p(a) q(a) regra da implicação (→) em 6 
 aberto aberto 
 Tableux aberto, Portanto o argumento não é válido