Die Logik ist keine Lehre, sondern ein Spiegelbild der Welt.
Logik ist transzendental.

- Ludwig Wittgenstein's (1921, 6.13) Tractatus Logico-Philosophicus in the original German

Logic is not a body of doctrine, but a mirror-reflection of the world.
Logic is transcendental.
- Pears/McGuinness translation

Proof by Natural Deduction

1. The proof theory of a logical system is concerned with manipulating logical formulae in accordance with certain rules of inference
2. Natural deduction is a proof theory in which logical reasoning is expressed by rules of inferences that closely relate to the natural way of reasoning

φ ⊦DNDψ

1. The mode of inference is deductive (represented by the superscript D)
2. The inferential mechanism is proof by natural deduction (represented by the subscript ND)

1. Here are some rules of inference:
2. RULE 1: p ∧ q ⊦ p, q
3. RULE 2: ∼(p ∨ q) ⊦ ∼p, ∼q
4. RULE 3: ∼∼p ⊦ p
5. RULE 4: ∼(p → q) ⊦ p, ∼q
6. RULE 5: p ⟷ q ⊦ p → q, q → p
7. RULE 6: ∼(p ∧ q), p ⊦ ∼q
8. RULE 7: p ∨ q, ∼q ⊦ p
9. RULE 8: p → q, p ⊦ q (modus ponens)
10. RULE 9: p → q, ∼q ⊦ ∼p (modus tollens)
11. RULE 10: p ⊦ p ∨ q
12. RULE 11: ((p ∧ q) → r) ⊦ p → (q → r)
13. RULE 12: p ∨ q, ∼p ∨ r ⊦ q ∨ r
14. RULE 13: ∼∀x(Fx) ⊦ ∃x(∼Fx)
15. RULE 14: ∼∃x(Fx) ⊦ ∀x(∼Fx)
16. RULE 15: ∼□p ⊦ ◇∼p
17. RULE 16: ∼◇p ⊦ □∼p
18.    ⋮

1. Harry Gensler's proof theory relies on the rules of inference (RULE 1, RULE 2, etc) and an additional RAA rule:
2. RAA rule (or reductio ad absurdum for reduction to absurdity):

4. STEP 1: Add all the premises of an argument to the opening lines of your proof
5. STEP 2: Block off the conclusion of the argument and assume the negation of the conclusion
6. STEP 3: Derive further lines in the proof using rules of inference and previous lines in the proof until you arrive at a contradiction
7. STEP 4: When you arrive at a contradiction, apply the RAA or reductio ad absurdum rule to prove the argument valid
8. STEP 5: When you get stuck, make another assumption
9. This assumption may lead to a contradiction, allowing you to apply the RAA rule and perhaps use this to complete the proof

1. EXAMPLE 1:
2. P1: p → q
3. C: ∴ ∼q → ∼p
4. Prove that this argument is valid.
1. Proof by natural deduction:
2. 1. p → q (see STEP 1)
3.    ∼q → ∼p
4. 2.      asm: ∼(∼q → ∼p)(see STEP 2)
5. 3.      ∴ ∼q (from 2, apply RULE 4) (see STEP 3)
6. 4.      ∴ p (from 2, apply RULE 4) (see STEP 3)
7. 5.      ∴ q (from 1 & 4, apply RULE 8 or modus ponens) (see STEP 3)
8. 6.    ∴ ∼q → ∼p (from 2, 3 contradicts 5, apply RAA rule) (see STEP 4)

9. We have a 6-line proof by natural deduction of the validity of the argument in EXAMPLE 1