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 draw 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 • p or p ∨ p 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. C3 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 from q ⊃ r and q we can infer that r is true with modus ponens.

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 Deriving the Conclusion from the Premises

Natural deduction shows how the conclusion of a valid argument can be derived step by step from its premises. If we know that an argument is valid, then we can draw its conclusion from its premises using common argument forms and equivalence rules. However, if an argument is invalid to begin with, then we would not be able to do so. In practice, this means that if after a concerted effort you cannot complete the process of natural deduction, then you should use the truth table method to verify that the argument is indeed valid in the first place. This way we can avoid wasting time trying to complete natural deduction for an invalid argument. Despite the drawback that if we do not know the validity of an argument, then we cannot be sure whether we can complete its natural deduction, the process is more in line with our reasoning steps and far less tedious than the truth table method.

There is no fixed way to construct natural deduction. Like playing chess, it takes a lot of practice to master how to apply the rules of inference to derive the conclusion from the premises. But the following guidelines or strategies can help you figure out how to go about it:

  1. If possible, identify a common argument form from two or three premises and derive its conclusion;
  2. If no common form can be found, apply an equivalence rule to a premise and then see if the resulting sentence together with one or two premises would constitute a common argument form;
  3. See what additional sentence is needed to derive the conclusion from one of the premises, and then use equivalence rules to obtain the needed sentence from a premise or a sentence in a previous step.

Let’s see how these three guidelines may help. In the next example, we first go over the premises to see if we can find a common form.

  1. (M ∨ D) ⊃ R
  2. D ∨ ∼A
  3. ∼R/ ∼A

We notice that we can have the common form modus tollens from the first and the third premise and draw the conclusion ∼(M ∨ D).

  1. (M ∨ D) ⊃ R
  2. D ∨ ∼A
  3. ∼R/ ∼A
  4. ∼(M ∨ D)1, 3 MT

Next, we observe that ∼D is needed to get the conclusion ∼A from the second premise D ∨ ∼A using disjunctive syllogism. This gives us a clue that we should try to get ∼D from step 4. To do so, we apply DeMorgan’s rule to ∼(M ∨ D) to get ∼M • ∼D.

  1. (M ∨ D) ⊃ R
  2. D ∨ ∼A
  3. ∼R/ ∼A
  4. ∼(M ∨ D)1, 3 MT
  5. ∼M • ∼D4 DM

We then apply commutativity to ∼M • ∼D to get ∼D • ∼M, and then use simplification to obtain ∼D from ∼D • ∼M. Finally we derive the conclusion ∼A with disjunctive syllogism.

  1. (M ∨ D) ⊃ R
  2. D ∨ ∼A
  3. ∼R/ ∼A
  4. ∼(M ∨ D)1, 3 MT
  5. ∼M • ∼D4 DM
  6. ∼D • ∼M5 Com.
  7. ∼D6 Simp.
  8. ∼A2, 7 DS

In cases where no common argument form is recognizable from the premises, it is a good idea to apply equivalence rules to one or more premises and see if this results in a common argument form. In the next example

  1. ∼(H • G)
  2. G/ H ⊃ B

the two premises do not constitute a common form. To see if we can get a common form, we first apply DeMorgan’s rule to the first premise and get ∼H ∨ ∼G.

  1. ∼(H • G)
  2. G/ H ⊃ B
  3. ∼H ∨ ∼G1 DM

Then by applying commutativity to step 3 and double negation to step 2, we have the common form disjunctive syllogism with ∼H as its conclusion.

  1. ∼(H • G)
  2. G/ H ⊃ B
  3. ∼H ∨ ∼G1 DM
  4. ∼G ∨ ∼H3 Com.
  5. ∼∼G2 DN
  6. ∼H4, 5 DS

To get the conclusion H ⊃ B, we obtain ∼H ∨ B from step 6 with the form addition. Then by material implication we arrived at the conclusion.

  1. ∼(H • G)
  2. G/ H ⊃ B
  3. ∼H ∨ ∼G1 DM
  4. ∼G ∨ ∼H3 Com.
  5. ∼∼G2 DN
  6. ∼H4, 5 DS
  7. ∼H ∨ B6 Add.
  8. H ⊃ B7 Impl.

Sometimes it can be hard to see which equivalence rules we should use to obtain a common argument form from the premises. As illustrated in the next example,

  1. ∼C ⊃ (E • P)
  2. (C ∨ E) ⊃ S/ S

it is not obvious which equivalence rule we should apply to one of the two premises. However, we do notice that if we obtain C ∨ E, then we can get the conclusion S from the second premise (C ∨ E) ⊃ S by modus ponens. This gives us an idea of how to proceed with natural deduction. To get C ∨ E, we first apply material implication and then double negation to the first premise and get C ∨ (E • P).

  1. ∼C ⊃ (E • P)
  2. (C ∨ E) ⊃ S/ S
  3. ∼∼C ∨ (E • P)1 Impl.
  4. C ∨ (E • P)3 DN

We then apply distribution to step 4 and get (C ∨ E) • (C ∨ P).

  1. ∼C ⊃ (E • P)
  2. (C ∨ E) ⊃ S/ S
  3. ∼∼C ∨ (E • P)1 Impl.
  4. C ∨ (E • P)3 DN
  5. (C ∨ E) • (C ∨ P)4 Dist.

Afterwards, from step 5 by simplification we get C ∨ E, which together with the second premise lead to the conclusion by modus ponens.

  1. ∼C ⊃ (E • P)
  2. (C ∨ E) ⊃ S/ S
  3. ∼∼C ∨ (E • P)1 Impl.
  4. C ∨ (E • P)3 DN
  5. (C ∨ E) • (C ∨ P)4 Dist.
  6. C ∨ E5 Simp.
  7. S2, 6 MP

Exercise 3.4

  1. Use common argument forms to prove that the following arguments are valid.
    • Click on Check Answers at the end of the section to see if your answers are correct.
    • You can change the answers marked as incorrect and click on Check Answers again.
    • Reload the page to get rid of answers and correction marks.
  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. Derive the new sentence from the numbered sentence using the given equivalence rule.
    • Click on one of the connective buttons to type the connective.
    • Click on Check Answers at the end of the section to see if your answers are correct.
    • You can change the answers marked as incorrect and click on Check Answers again.
    • Reload the page to get rid of answers and correction marks.
  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 / A ⊃ ∼O
    3. 1 DM
    4. 3 Impl.
    5. 2 Equiv.
    6. 5 Com.
    7. ∼H ⊃ ∼O 6 Simp.
    8. A ⊃ ∼O 4, 7 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
  6.  
    1. ∼G ∨ (E ⊃ L)
    2. ∼L
    3. E / ∼G
    4. 1 Impl.
    5. 4 Exp.
    6. ∼(G • E) 2, 5 MT
    7. 6 DM
    8. 7 Com.
    9. 3 DN
    10. ∼G 8, 9 DS
  7.  
    1. (C • A) ∨ S
    2. C ⊃ N / ∼S ⊃ N
    3. 1 Com.
    4. 3 Dist.
    5. S ∨ C 4 Simp.
    6. 5 DN
    7. 6 Impl.
    8. ∼S ⊃ N 2, 7 HS
  8.  
    1. H ≡ B 
    2. ∼(H • B)
    3. R ⊃ (D ⊃ H) / ∼(R • D)
    4. 1 Equiv.
    5. ∼H • ∼B 2, 4 DS
    6. ∼H 5 Simp.
    7. 3 Exp.
    8. ∼(R • D) 6, 7 MT

 

  1. Use common argument forms and equivalence rules to derive the conclusion from the premises.
    • Click on one of the connective buttons to type the connective.
    • Click on Check Answers at the end of the section to see if your answers are correct.
    • You can change the answers marked as incorrect and click on Check Answers again.
    • Reload the page to get rid of answers and correction marks.
  1.  
    1. A ⊃ ∼M
    2. M ∨ G
    3. ∼G / ∼A
    4. 2 Com.
    7. ∼A
  2.  
    1. ∼H ⊃ ∼P
    2. ∼(H ∨ B)
    3. P ∨ ∼D / ∼D
    4. 2 DM
    7. ∼D
  3.  
    1. C ⊃ S
    2. O ⊃ R
    3. C ∨ O
    4. E ⊃ ∼R / ∼S ⊃ ∼E
    5. 1, 2, 3 CD
    6. 5 DN
    10. ∼S ⊃ ∼E
  4.  
    1. (J ⊃ K) ∨ N
    2. J
    3. ∼K / N
    4. J • ∼K
    5. 4 DN
    8. N
  5.  
    1. B ≡ D
    2. D ≡ G
    3. ∼G / ∼B
    5. 4 Simp.
    9. ∼B
  6.  
    1. (W • N) ⊃ S
    2. P ∨ ∼S
    3. W / N ⊃ P
    6. ∼S ∨ P 2 Com.
    8. N ⊃ P
  7.  
    1. R ∨ (H • M)
    2. ∼G ⊃ ∼R
    3. ∼H / G
    9. G
  8.  
    1. ∼(A • C) ∨ L
    2. ∼(C ⊃ L) / ∼A
    5. ∼A
  9.  
    1. ∼(A • C) ∨ L
    2. ∼(C ⊃ L) / ∼A
    7. ∼A

Question #8 and #9 illustrate that there can be more than one way to complete natural deduction.

 

This work is licensed under CC BY-NC-ND 4.0