DEDUCAO NATURAL

Exercícios de Dedução Natural

2.6 Usando Dedução Natural, apresentar demonstrações para as seguintes fórmulas:

(a) C = (A  (B  C))  (B  (A  C))

├ (A  (B  C))  (B  (A  C)) sse A  (B  C) ├ B  (A  C)

1. A  (B  C) P
2. A H
3. B  C 1,2 MP
4. B H
5. C 3,4 MP
6. A  C 2-5 RPC
7. B  (A  C) 4-6 RPC

(b) W = (A  (A  B))  (A  B)

├ (A  (A  B))  (A  B) sse A  (A  B) ├ A  B

1. A  (A  B) P
2. | A H
3. A  B 1, 2 MP

2.7 Deduzir os seguintes resultados pelo método da dedução natural.

(a) (¬p  q) ├ ((¬p  ¬q)  p)

(¬p  q) ├ ((¬p  ¬q)  p) sse ¬p  q, ¬p  ¬q ├ p

1. ¬p  q P
2. ¬p  ¬q P
3. ¬p H
4. q 1,3 MP
5. ¬q 2, 3 MP
6. q  ¬q 4, 5 C
7. ¬¬p RAA
8. p DN

(b) p  q, ¬q├ ¬p

1. p  q P
2. ¬q P
3. ¬p 1, 2 MT

(c) ¬q  ¬p├ p  q

1.¬q  ¬p P
2. | p H
3. p  q 1, 2 CT

(d) ¬(p  q)├ ¬p  ¬q

1. ¬(p  q) P
2. ¬p  ¬q 1 DM

(e) ¬p  ¬q├ ¬(p  q)

1. ¬p  ¬q P
2. ¬(p  q) 1 DM

(f) ¬(p  q)├ ¬p  ¬q

1. ¬(p  q) P
2. ¬p  ¬q 1 DM

(g) ¬p  ¬q├ ¬(p  q)

1. ¬p  ¬q P
2. ¬(p  q) 1 DM

(h) p  (q  r) ├ (p  q)  (p  r)

1. p  (q  r) P
2. q  r H
3. q 2S
4. r 2S
5. p  q 1, 3 C
6. p  r 1, 4 C
7. (p  q)  (p  r) 5, 6 C

(i) (p  q)  (p  r) ├ p  (q  r)

1. (p  q)  (p  r) P
2. (p  r) H
3. (p  q) 2 S
4. ¬p H
5. r 2, 4 SD
6. q 3, 4 SD
7. q  r 5, 6 C
8. p  (q  r) 7 E

(j) p  (q  r) ├ (p  q)  (p  r)

1. p  (q  r) P
2. p 1 S
3. q  r 1 S
4. ¬q H
5. r 3, 4 SD
6. p  r 2, 5 C
7. (p  q)  (p  r) 6 E

(k) (p  q)  (p  r) ├ p  (q  r)

1. (p  q)  (p  r) P
2. (p  r) H
3. p 2S
4. r 2S
5. (q  r) 4 E
6. p  (q  r)