Part 1  Part 2  Part 3  Part 4
This is part 5 in a series. There are links to the other parts of the series above.
Natural deduction is used to give proofs of validity by showing all the steps in reasoning required. In this case natural deduction uses rules of inference to allow us to reach conclusions from statements of propositional logic.
Rules of inference
Rules of inference include rules of implication (valid argument forms) and rules of replacement (statements with equivalent logical form).
The rules are the following:
Rules of implication
Modus ponens (MP)  Modus tollens (MT)  Hypothetical syllogism (HS)  Disjunctive syllogism (DS) 
p → q  p → q  p → q  p ∨ q 
p 
¬q 
q → r 
¬p 
∴q 
∴¬p 
∴r → s  ∴q 
Constructive Dilemma (CD)  Simplification (Simp)  Conjunction (Conj)  Addition (Add) 
p → q  p ∧ q  p  p 
r → s  ∴p  q  ∴p ∨ q 
p ∨ r  ∴p ∧ q  
∴q ∨ s 
Each of these rules states a valid argument form. For example, modus ponens states that the following argument form is valid:

p → q

p

∴q
“∴” merely states that the final statement is a conclusion. Whenever we know “p → q” and “p” are true, we can conclude “q.” Each of these lowercase letters can stand for any statement, no matter how complex. Each letter must stand for the same statement when concerning the same argument. For example, “p” can stand for “all humans are mammals” and “q” can stand for “all humans are living organisms” for an entire argument. In that case we can develop the following valid argument in the English language using modus ponens:
 If all humans are mammals, then all humans are living organisms.
 All humans are mammals.
 Therefore, all humans are living organisms.
Rules of replacement
DeMorgan’s Rule (DM)  Commutativity (Com)  Associativity (Assoc)  Distribution (Dist)  Double negation (DN) 
¬(p ∧ q) :: (¬p ∨ ¬q) 
(p ∧ q) :: (q ∧ p)  [p ∨ (q ∨ r)] :: [(p ∨ q) ∨ r]  [p ∧ (q ∨ r)] :: [(p ∧ q) ∨ (p ∧ r)]  p :: ¬¬p 
¬(p ∨ q) :: (¬p ∧ ¬q) 
(p ∨ q) :: (q ∨ p)  [p ∧ (q ∧ r)] :: [(p ∧ q) ∧ r]  [p ∨ (q ∧ r)] :: [(p ∨ q) ∧ (p ∨ r)] 
Transposition (Trans)  Material implication (Impl)  Material equivalence (Equiv)  Exportation (Exp)  Tautology (Taut) 
(p → q) :: (¬q → ¬p)  (p → q) :: (¬p ∨ q)  (p ↔ q) ::(p → q) ∧ (q → p)  [(p ∧ q) → r] ::[p → (q → r)]  p :: (p ∨ p) 
(p ↔ q) :: (p ∧ q) ∨ (¬p ∧ ¬q) 
p :: (p ∧ p) 
Each of the rules of replacement state that certain statements are logically equivalent. You can validly conclude either part of a rule of replacement from the other part—the first part of the “::” symbol can be concluded from the second part, and vise versa.
For example, double negation states that “p” and “¬¬p” are logically equivalent. If you know “p,” then you can conclude “¬¬p” and vice versa. “p” can stand for “all humans are mammals.” In that case we can conclude that “it’s not the case that ‘all humans are mammals’ is false.”
Some rules of replacement actually have more than one type of equivalence. For example, DeMorgan’s rule has two different ways it can be used.
How to construct a proof
Proving validity using natural deduction requires the following steps:

Find the logical form of an argument.

Write the logical form of the premises.

Write the conclusion on the same line as the last premise after the “/” symbol.

Use those premises and the rules of inference to reach the logical form of the argument’s conclusion.
I will present two examples of proofs.
Example 1
Consider the following argument:
All humans are lizards. If all humans are lizards, then all humans are reptiles. If all humans are reptiles, then they are coldblooded. Therefore, all humans are coldblooded.
The logical form of this argument is the following:
 P
 P → Q
 Q → R
 ∴R
Each letter is capitalized and represents a specific statement in English:
P: All humans are lizards.
Q: All humans are reptiles.
R: All humans are coldblooded.
The proof that the argument is valid looks like the following:





/ R 

1, 2, MP 

3, 4, MP 
The premises are written on lines 1, 2, and 3. The conclusion is written after the final premise on line 3.
Line 4 concludes “Q” from lines 1 and 2 using modus ponens. “1, 2, MP” is written on the righthand side to make that clear. “P; P → Q; ∴Q” is valid because it uses modus ponens. (It has the same form as “p; p → q; ∴q.”)
Line 5 concludes “R” from lines 3 and 4 using modus ponens. “3, 4, MP” is written on the righthand side to make that clear. “Q → R; Q. ∴R” is valid because it uses modus ponens. (It has the same form as “p; p → q; ∴q.”)
Line 5 has the conclusion of the original argument, so we have proven that the argument is valid. We can derive the conclusion from the premises and rules of inference.
Example 2
Consider the following argument:
All humans are mammals, and if all dogs are warmblooded and have thoughts, then it is not the case that all dogs are reptiles or insects. If all humans are coldblooded, then it is not the case that all humans are mammals. If it is not the case that all humans are coldblooded, then no humans are lizards. Therefore, no humans are lizards.
The logical form of this argument is the following:
 A ∧ [(B ∧ C) → ¬(D ∨ E)]
 F → ¬A
 ¬F → G
 ∴G
the letters stand for the following:
A: All humans are mammals.
B: All dogs are warmblooded.
C: All dogs have thoughts.
D: All dogs are reptiles.
E: All dogs are insects.
F: All humans are coldblooded.
G: No humans are lizards.
The proof that this argument is valid is the following:





/ G 

1, Simp 

4, DN 

2, 5, MT 

3, 6, MP 
Lines 1, 2, and 3 contain the premises. The conclusion is also written on line 3.
Line 4 concludes “A” by simplification using line 1. “A ∧ [(B ∧ C) → ¬(D ∨ E)]; ∴A” is a valid argument because of simplification. “A ∧ [(B ∧ C) → ¬(D ∨ E)]; ∴A” has the same form as “p ∧ q; ∴p.”
Line 5 concludes “¬¬A” by using line 4 and double negation. “A; ∴¬¬A” is a valid argument because they are equivalent. “A :: ¬¬A” has the same form as “p :: ¬¬p.”
Line 6 concludes “¬F” by using lines 2 and 5, and modus tollens. “F → ¬A; ¬¬A. ∴¬F” is a valid argument because of modus tollens. “F → ¬A; ¬¬A; ∴¬F” has the same form as “p → q; ¬q.; ∴¬p.”
Line 7 concludes “G” by using lines 3 and 6, and modus ponens. “¬F → G; ¬F; ∴G” is a valid argument because of modus ponens. “¬F → G; ¬F; ∴G” has the same form as “p → q; p; ∴q.”
“G” is the conclusion of the argument, so the argument is valid. We were able to deduce the conclusion from the premises and rules of inference.
I’m relatively new here: Could you run through the symbols’ meanings and how you were able to use them on WordPress? Did you import the piece from Word?
Comment by Just a Pedestrian — February 19, 2013 @ 12:59 pm 
This is part 5 in a series. There are links to the other parts of the series at the top.
Comment by JW Gray — February 19, 2013 @ 10:48 pm 