Exercícios-Lógica_Proposicional-Dedução_Natural

Prévia do material em texto

MATA 47 - Lógica para Computação 
Exercícios de Lógica Proposicional 
Dedução Natural 
Prof. Sérgio Gorender 
 
Provar as fórmulas a seguir utilizando a dedução natural: 
1. (p ∧ q) → (p ∨ q) 
2. ((p → q) ∧ (q → m)) → (p → m) 
3. ((p → q) ∧ (q → m)) → (¬m → ¬p) 
4. ¬p → (p → q) 
5. ((p ∨ q) ∧ r) → ((p ∧ r) ∨ (q ∧ r)) 
6. (p ∨ (p ∧ ¬q)) → p 
7. (p ∧ q) → (p → q) 
8. (p → r) → ((q → r) → ((p ∨ q) → r)) 
9. ((p → q) ∧ (¬p → q)) → q 
 
 
Provar as fórmulas a seguir utilizando a dedução natural: 
1. | (A → B) → ((A → (B → C)) → (A → C)) 
2. | (A → (B → C)) → ((A → B) → (A → C)) 
3. | A → (B → (A ∧ B)) 
4. | (A ∧ B) → A 
5. | A → (A ∨ B) 
6. | (A → C) → ((B → C) → ((A ∨ B) → C)) – 
7. | (A →B) → ((A → ¬B) → ¬A) 
8. | (A → B) → ((B → A) → (A ↔ B)) –. 
9. | (A ↔ B) → (A → B)