Exercícios de Dedução Natural

...

7. (p ∨ q) ∧ (p ∨ r) 5, 6 C

- (p ∨ q) ∧ (p ∨ r) ├ p ∨ (q ∧ r)

1. (p ∨ q) ∧ (p ∨ r) P

2. (p ∨ r) H[pic 5]

3. (p ∨ q) 2 S

4. ¬p H [pic 6]

5. r 2, 4 SD

6. q 3, 4 SD

7. q ∧ r 5, 6 C

8. p ∨ (q ∧ r) 7 E

- p ∧ (q ∨ r) ├ (p ∧ q) ∨ (p ∧ r)

1. p ∧ (q ∨ r) P

2. p 1 S

3. q ∨ r 1 S

4. ¬q H[pic 7]

5. r 3, 4 SD

6. p ∧ r 2, 5 C

7. (p ∧ q) ∨ (p ∧ r) 6 E

- (p ∧ q) ∨ (p ∧ r) ├ p ∧ (q ∨ r)

1. (p ∧ q) ∨ (p ∧ r) P[pic 8]

2. (p ∧ r) H

3. p 2S

4. r 2S

5. (q ∨ r) 4 E

6. p ∧ (q ∨ r) 3, 5 C

2.8 Demonstrar o teorema da dedução, usando as regras da Dedução Natural. Ou seja, demonstrar que

Γ, A├ DN B sse Γ├ DN A → B.

Os exercícios (a) e (b) do item 2.6 demonstram o teorema acima.

2.9 Provar que toda dedução pelo sistema de axiomatização pode ser simulada pelo método da Dedução Natural.

O método de axiomatização utiliza apenas a regra Modus Ponens e a substituição, sendo que esses dois também fazem parte da Dedução Natural junto com mais várias regras de inferência. Então, qualquer dedução que pode ser feita através da axiomatização, pode ser feita por Dedução Natural.