lista-DN

Prévia do material em texto

Exerc´ıcios de Deduc¸a˜o Natural
SIN015 – Lo´gica para Computac¸a˜o
Davi Romero de Vasconcelos
1. ` (ϕ→ (ψ → σ))→ (ψ → (ϕ→ σ))
2. ` (ϕ→ (ϕ→ ψ))→ (ϕ→ ψ)
3. ` (¬ϕ→ ψ)→ ((¬ϕ→ ¬ψ)→ ϕ)
4. ` ϕ ∨ ¬ϕ
5. ` (ϕ→ ψ) ∨ (ψ → ϕ)
6. ` ϕ→ ϕ
7. ` (ϕ→ ψ)→ ((σ → ϕ)→ (σ → ϕ))
8. ` (ϕ→ (ψ → σ))→ (ψ → (ϕ→ σ))
9. ` (ϕ→ (ϕ→ ψ))→ (ϕ→ ψ)
10. ` (ϕ→ (ψ → σ))→ ((ϕ→ ψ)→ (ϕ→ σ))
11. ` (ϕ→ (ψ → ϕ))
12. ` ((ϕ→ ψ)→ ϕ)→ ϕ
13. ϕ ∨ ψ,ϕ→ σ, ψ → σ ` σ
14. ϕ ` ¬¬ϕ
15. ¬¬ϕ ` ϕ
16. ϕ→ ψ,¬ψ ` ¬ϕ
17. ¬ψ → ¬ϕ ` ϕ→ ψ
18. ϕ→ ψ ` ¬ψ → ¬ϕ
19. ¬(ϕ ∨ ψ) ` ¬ϕ ∧ ¬ψ
20. ¬ϕ ∧ ¬ψ ` ¬(ϕ ∨ ψ)
21. ¬(ϕ ∧ ψ) ` ¬ϕ ∨ ¬ψ
22. ¬ϕ ∨ ¬ψ ` ¬(ϕ ∧ ψ)
23. ϕ ∨ (ψ ∧ σ) ` (ϕ ∨ ψ) ∧ (ϕ ∨ σ)
24. (ϕ ∨ ψ) ∧ (ϕ ∨ σ) ` ϕ ∨ (ψ ∧ σ)
25. ϕ ∧ (ψ ∨ σ) ` (ϕ ∧ ψ) ∨ (ϕ ∧ σ)
26. (ϕ ∧ ψ) ∨ (ϕ ∧ σ) ` ϕ ∧ (ψ ∨ σ)
27. ϕ ∨ ψ,¬ψ ` ϕ
28. ϕ ∨ ψ ` ¬ϕ→ ψ
29. ¬ϕ→ ψ ` ϕ ∨ ψ
30. ϕ ∧ ψ ` ¬(ϕ→ ¬ψ)
31. ¬(ϕ→ ¬ψ) ` ϕ ∧ ψ
1
32. ϕ ∨ ψ ` ¬(¬ϕ ∧ ¬ψ)
33. ¬(¬ϕ ∧ ¬ψ) ` ϕ ∨ ψ
34. ϕ→ ψ ` ¬(ϕ ∧ ¬ψ)
35. ¬(ϕ ∧ ¬ψ) ` ϕ→ ψ
36. ϕ ∧ ψ ` ¬(¬ϕ ∨ ¬ψ)
37. ¬(¬ϕ ∨ ¬ψ) ` ϕ ∧ ψ
38. ϕ→ ψ ` ¬ϕ ∨ ψ
39. ¬ϕ ∨ ψ ` ϕ→ ψ
40. ` ∀xϕ(x)→ ¬∃x¬ϕ(x)
41. ` ¬∃x¬ϕ(x)→ ∀xϕ(x)
42. ` ∃xϕ(x)→ ¬∀x¬ϕ(x)
43. ` ¬∀x¬ϕ(x)→ ∃xϕ(x)
44. ` ∀x(ϕ(x) ∧ ψ(x))→ (∀xϕ(x) ∧ ∀xψ(x))
45. ` ∀x∀yϕ(x, y)→ ∀y∀xϕ(x, y)
46. ` ∀x(ϕ→ ψ(x))→ (ϕ→ ∀xψ(x)), onde x 6∈ V L(ϕ)
47. ` ∃x(ϕ(x) ∨ ψ(x))→ (∃xϕ(x) ∨ ∃xψ(x))
48. ` ¬∀xϕ(x)→ ∃x¬ϕ(x)
49. ` ∃x¬ϕ(x)→ ¬∀xϕ(x)
50. ` ¬∃xϕ(x)→ ∀x¬ϕ(x)
51. ` ∀x¬ϕ(x)→ ¬∃xϕ(x)
52. ` ∃x(ϕ(x) ∧ ψ)→ (∃xϕ(x) ∧ ψ), onde x 6∈ V L(ψ)
53. ` (∃xϕ(x) ∧ ψ)→ ∃x(ϕ(x) ∧ ψ), onde x 6∈ V L(ψ)
54. ` ∀x(ϕ(x) ∨ ψ)→ (∀xϕ(x) ∨ ψ), onde x 6∈ V L(ψ)
55. ` (∀xϕ(x) ∨ ψ)→ ∀x(ϕ(x) ∨ ψ), onde x 6∈ V L(ψ)
56. ` ∃x(ϕ(x)→ ψ)→ (∀xϕ(x)→ ψ), onde x 6∈ V L(ψ)
57. ` (∀xϕ(x)→ ψ)→ ∃x(ϕ(x)→ ψ), onde x 6∈ V L(ψ)
58. ` ∃x(ϕ→ ψ(x))→ (ϕ→ ∃xψ(x)), onde x 6∈ V L(ϕ)
59. ` (ϕ→ ∃xψ(x))→ ∃x(ϕ→ ψ(x)), onde x 6∈ V L(ϕ)
60. ` ∃x(ϕ(x)→ ∀xϕ(x))
2