PDF

3.4 Natural Deduction

In the previous section, we symbolize the argument (3.3n)

If we continue the acceleration of production and consumption, we will deplete natural resources within one hundred years. If natural resources are depleted within one hundred years, life on earth will not be sustainable. We continue to accelerate production and consumption. As a result, life on earth will not be sustainable. 3.3n

as


   C ⊃ D

  D ⊃ ∼S

  C

  ∼S

We then show that it is valid because it is formed by combining


   C ⊃ D
and
  C ⊃ ∼S

  D ⊃ ∼S
 
  C

  C ⊃ ∼S
 
  ∼S
  Hypothetical Syllogism
 
Modus Ponens

The whole process of showing that the argument (3.3n) is valid can be simplified and written as a list of steps:

  1. C ⊃ D
  2. D ⊃ ∼S
  3. C/ ∼S
  4. C ⊃ ∼S1, 2 HS
  5. ∼S
    3, 4 MP

Notice a forward slash “/” is used in line 3 to separate the third premise C from the conclusion ∼S. Step 4 shows that the conditional C ⊃ ∼S is derived from the first and the second premise using the basic form hypothetic syllogism (HS). Step 5 shows that the conclusion ∼S is derived from the third premise and the fourth statement using the basic form modus ponens (MP). This way of showing how the conclusion of an argument is derived step by step from its premises using rules of inference is called natural deduction. It is a formal way of proving that an argument form is valid. The rules of inference used in natural deduction include the basic valid forms as well as equivalence rules.

3.4.1 Additional Valid Forms

In addition to the six valid forms introduced in the previous section, there are three more basic forms that are commonly used in natural deduction:

  1. Simplification (Simp.)
  2. Addition (Add.)
  3. Conjunction (Conj.)

Simplification (Simp.)

The basic form simplification encapsulates the reasoning that if a conjunction is true, then one of the conjunct must be true.

    p • q  

  p

Some instances of simplification are:

  S • C
  S
  ∼B • ∼H
  ∼B
  (A ∨ D) • ∼G
  A ∨ D

Here is an example that illustrates how simplification is used in natural deduction. By using simplification, we can get R from the second premise R • ∼E. Then from the first premise R ⊃ M, together with R, we can draw the conclusion M based on modus ponens (MP).

  1. R ⊃ M
  2. R • ∼E/ M
  3. R2 Simp.
  4. M1, 3 MP

Addition (Add.)

The form addition basically enables us to construct a disjunction out of any statement. If p is true, then the disjunction p ∨ q must also be true.


   p

  p ∨ q

The following are all instances of addition:

  G
  G ∨ N
  M
  M ∨ ∼A
  ∼D
  ∼D ∨ (H ⊃ S)

In the next example, from the second premise B addition is used to obtain B ∨ A, which is then used together with the first premise to derive the conclusion H by modus ponens (MP).

  1. (B ∨ A) ⊃ H
  2. B/ H
  3. B ∨ A2 Add.
  4. H1, 3 MP

Conjunction (Conj.)

The form conjunction simply captures the basic logic that if two statements are true, then their conjunction must also be true.


   p

  q

  p • q

Some examples of conjunction are:

  B
  E
  B • E
  ∼R
  A
  ∼R • A
  C
  N ≡ L
  C • (N ≡ L)

In the following proof, we use conjunction to derive S • R from the first two premises. Afterwards, addition is used to form the conclusion (S • R) ∨ G from S • R.

  1. S
  2. R/ (S • R) ∨ G
  3. S • R1, 2 Conj.
  4. (S • R) ∨ G3 Add.

3.4.2 Equivalence Rules

There are ten equivalence rules, also called rules of replacement used in natural deduction. They allow us to substitute a statement or its component with a logically equivalent statement or component. In the following blue boxes, the symbol “=” is used to mean “is logically equivalent to”. As we learned in section 3.2, we can use truth tables to prove that the two formulas are logically equivalent.

Double Negation (DN)

p  =  ∼∼p

We learned to use the rule of double negation in section 3.3 to identify the basic argument forms. This example shows how to use it to formally draw the conclusion ∼M from M ⊃ ∼(D ∨ L) and D ∨ L using modus tollens (MT):

  1. M ⊃ ∼(D ∨ L)
  2. D/ ∼M
  3. D ∨ L2 Add.
  4. ∼∼(D ∨ L)3 DN
  5. ∼M1, 4 MT

Tautology (Taut.)

p  =  p • p
p  =  p ∨ p

This rule is quite self-explanatory and is typically used to contract p • q or p ∨ q to p, as illustrated in this example:

  1. G ⊃ K
  2. N ⊃ K
  3. G ∨ N/ K
  4. K ∨ K1, 2, 3 CD
  5. K4 Taut.

Commutativity (Com.)

p • q  =  q • p
p ∨ q  =  q ∨ p

Commutativity allows us to switch the order of two conjuncts or disjuncts. The first example below shows the application of commutativity to a conjunction:

  1. J • C
  2. C ⊃ E/ E
  3. C • J1 Com.
  4. C4 Simp.
  5. E2, 4 MP

In the second example, commutativity is applied to a disjunction that is part of a conditional:

  1. (W ∨ ∼A) ⊃ D
  2. D ⊃ S/ (∼A ∨ W) ⊃ S
  3. (∼A ∨ W) ⊃ D1 Com.
  4. (∼A ∨ W) ⊃ S2, 3 HS

Transportation (Trans.)

p ⊃ q  =  ∼q ⊃ ∼p

In the conditional p ⊃ q, q is a necessary condition for p. This means that if q is not true, then p cannot be true.

In the next proof, in order to get the conclusion H ⊃ J using hypothetical syllogism (HS), we first apply transportation to get O ⊃ J from ∼J ⊃ ∼O:

  1. H ⊃ O
  2. ∼J ⊃ ∼O/ H ⊃ J
  3. O ⊃ J2 Trans.
  4. H ⊃ J1, 3 HS

Material Implication (Impl.)

p ⊃ q  =  ∼p ∨ q

Material implication allows us to replace a conditional with a disjunction, and vice versa. In the following example, to use hypothetical syllogism (HS) to derive I ⊃ U, we first use material implication to replace ∼R ∨ U with R ⊃ U:

  1. I ⊃ R
  2. ∼R ∨ U/ I ⊃ U
  3. R ⊃ U2 Impl.
  4. I ⊃ U1, 3 HS

In the example below, we apply material implication to the first conjunct of the conjunction in order to use constructive dilemma to derive the conclusion:

  1. (∼M ∨ L) • (H ⊃ G)
  2. M ∨ H/ L ∨ G
  3. (M ⊃ L) • (H ⊃ G)1 Impl.
  4. L ∨ G2, 3 CD

DeMorgan’s Rule (DM)

∼(p • q)  =  ∼p ∨ ∼q
∼(p ∨ q)  =  ∼p • ∼q

DeMorgan’s rule was introduced at the end of section 3.1. The rule enables us to turn the negation of a conjunction into a disjunction of two negations, and turn the negation of a disjunction into a conjunction of two negations:

In the following natural deduction, we apply DeMorgan’s rule to ∼(B ∨ S) to get ∼B • ∼S. We then use simplification to get ∼B, which, together with B ∨ E, allows us to derive the conclusion E using disjunctive syllogism (DS):

  1. ∼(B ∨ S)
  2. B ∨ E/ E
  3. ∼B • ∼S1 DM
  4. ∼B 3 Simp.
  5. E2, 4 DS

We can also apply DeMorgan’s rule to part of a statement:

  1. (∼N ∨ ∼A) ∨ K
  2. K ⊃ P/ (N • A) ⊃ P
  3. ∼(N • A) ∨ K1 DM
  4. (N • A) ⊃ K3 Impl.
  5. (N • A) ⊃ P2, 4 HS

Material Equivalence (Equiv.)

p ≡ q  =  (p ⊃ q) • (q ⊃ p)
p ≡ q  =  (p • q) ∨ (∼p • ∼q)

In section 3.1, we learned that the biconditional p ≡ q is an abbreviation of (p ⊃ q) • (q ⊃ p). This understanding gives us the first material equivalence: p ≡ q is logically equivalent to (p ⊃ q) • (q ⊃ p).

The second material equivalence can be derived from the first one. The first conditional p ⊃ q says that p is a sufficient condition for q. This means that if p is true, then q must be true. The second conditional q ⊃ p tells us that p is a necessary condition for q. This means that if p is false, then q must be false. So the two conditionals together amount to either both p and q are true or both p and q are false, i.e., (p  • q) ∨ (∼p • ∼q).

The first material equivalence allows us replace a biconditional with a conjunction of two conditionals before we can use a basic argument form to derive other statements in natural deduction:

  1. ∼O ≡ M
  2. ∼M/ O
  3. (∼O ⊃ M) • (M ⊃ ∼O)1 Equiv.
  4. ∼O ⊃ M3 Simp.
  5. ∼∼O2, 4 MT
  6. O5 DN

In the next example, we use the second material equivalence to turn a biconditional into a disjunction of two conjuncts. This then enables us to use disjunctive syllogism in step 5:

  1. G ≡ H
  2. ∼G ∨ ∼H/ ∼G
  3. (G • H) ∨ (∼G • ∼H)1 Equiv.
  4. ∼(G • H)2 DM
  5. ∼G • ∼H3, 4 DS
  6. ∼G5 Simp.

Associativity (Assoc.)

(p • q) • r  =  p • (q • r)
(p ∨ q) ∨ r  =  p ∨ (q ∨ r)

The rule allows us to shift the position of parentheses. In the next proof, associativity is used with commutativity to get (C ∨ A) ∨ P, which enables us to use disjunctive syllogism (DS) to derive the conclusion P:

  1. (P ∨ C) ∨ A
  2. ∼(C ∨ A)/ P
  3. P ∨ (C ∨ A)1 Assoc.
  4. (C ∨ A) ∨ P3 Com.
  5. P2, 4 DS

Distribution (Dist.)

p • (q ∨ r)  =  (p • q) ∨ (p • r)
p ∨ (q • r)  =  (p ∨ q) • (p ∨ r)

If p • (q ∨ r) is true, then both p and q ∨ r are true. If q ∨ r is true, then either q is true or r is true. In the case that q is true, we would have both p and q true. On the other hand, in the case that r is true, we would have both p and r true. As a result, either p • q is true or p • r is true.

If (p ∨ q) • (p ∨ r) is true, then both p ∨ q and p ∨ r are true. Now suppose p is false, then based on disjunctive syllogism, we can conclude that q must be true and r must be true, and consequently q • r must be true. We thus have ∼p ⊃ (q • r), which is logically equivalent to p ∨ (q • r) according to material implication.

In the next example, distribution is used in step 3 to derive (W ∨ L) • (W ∨ R) from the first premise W ∨ (L • R):

  1. W ∨ (L • R)
  2. ∼L / W
  3. (W ∨ L) • (W ∨ R)1 Dist.
  4. W ∨ L3 Simp.
  5. L ∨ W4 Com.
  6. W2, 5 DS

Exportation (Exp.)

(p • q) ⊃ r  =  p ⊃ (q ⊃ r)

To see that (p • q) ⊃ r is logically equivalent to p ⊃ (q ⊃ r) without constructing truth tables, let us suppose that p • q is true and try to infer that r is true from both of them. First, from (p • q) ⊃ r and p • q, we can conclude that r is true according to modus ponens. Now applying simplification to the assumption that p • q is true, we can infer that p is true and q is also true. From p ⊃ (q ⊃ r) and p, we can derive q ⊃ r with modus ponens. Then again with modus ponens we can infer that r is true from q ⊃ r and q.

As illustrated below, the use of exportation greatly simplifies the deduction and enables us to derive the conclusion in just two steps.

  1. (G • D) ⊃ M
  2. ∼(D ⊃ M)/ ∼G
  3. G ⊃ (D ⊃ M)1 Exp.
  4. ∼G2, 3 MT

3.4.3 Natural Deduction

Exercise 3.4

  1. Use common argument forms to prove that the following arguments are valid.
  1.  
    1. H ⊃ S
    2. H ∨ ∼I
    3. ∼I ⊃ R
    4. ∼S / R
    5. ∼H
    6. ∼I
    7. R
  2.  
    1. B ⊃ (S ≡ G)
    2. B ∨ K
    3. ∼(S ≡ G) / K
    4. ∼B
    5. K
  3.  
    1. (A ∨ ∼C) ⊃ E
    2. E ⊃ ∼N
    3. A ∨ ∼C / ∼N
    4. (A ∨ ∼C) ⊃ ∼N
    5. ∼N
  4.  
    1. G ⊃ P
    2. L ⊃ M
    3. G
    4. ∼P / M
    5. G ∨ L
    6. P ∨ M
    7. M
  5.  
    1. (D ⊃ H) • J
    2. ∼H
    3. ∼D ⊃ ∼C / ∼D • ∼C
    4. D ⊃ H
    5. ∼D
    6. ∼C
    7. ∼D • ∼C
  6.  
    1. (O ⊃ S) • (G ⊃ A)
    2. ∼S / ∼O ∨ ∼G
    3. ∼S ∨ ∼A
    4. ∼O ∨ ∼G
  7.  
    1. (K • ∼P) ∨ W
    2. W ⊃ ∼(X ≡ B)
    3. ∼(K • ∼P)
    4. R ⊃ (X ≡ B) / ∼R
    5. W
    6. ∼(X ≡ B)
    7. ∼R
  8.  
    1. (∼M • U) • C
    2. (∼M ∨ D) ⊃ L / ∼M • L
    3. ∼M • U
    4. ∼M
    5. ∼M ∨ D
    6. L
    7. ∼M • L

 

  1. Use equivalence rules to derive a new statement from the given statement.
  1.  
    1. N ∨ ∼E
    2. E
    3. N ⊃ ∼B / ∼B
    4. 1 Com.
    5. 2 DN
    6. N 4, 5 DS
    7. ∼B 3, 6 MP
  2.  
    1. V ⊃ (Q • K)
    2. ∼K ∨ ∼Q / ∼V
    3. 1 Com.
    4. 2 DM
    5. ∼V 3, 4 MT
  3.  
    1. ∼S ⊃ ∼R
    2. ∼P ∨ C
    3. ∼S ∨ ∼C / R ⊃ ∼P
    4. 1 Trans.
    5. 2 Impl.
    6. ∼R ∨ ∼P 3, 4, 5 DD
    7. 6 Impl.
  4.  
    1. ∼(A • H)
    2. ∼O ≡ ∼H
    3. ∼S ∨ ∼C / A ⊃ ∼O
    4. 1 DM
    5. 4 Impl.
    6. 2 Equiv.
    7. 6 Com.
    8. ∼H ⊃ ∼O 7 Simp.
    9. A ⊃ ∼O 5, 8 HS
  5.  
    1. (B • D) ⊃ J
    2. (D • ∼J) ∨ M
    3. B / M
    4. 1 Exp.
    5. D ⊃ J 3, 4 MP
    6. 5 Impl.
    7. 6 DN
    8. 7 DM
    9. M 2, 8 DS

 

Creative Commons License
This work is licensed under a Creative Commons Attribution-Noncommercial-No-Derivative Works 3.0 United States License.