Natural Deduction

Natural Deduction

Natural deduction is a method used in formal logic to derive conclusions from premises using a set of inference rules. It provides a systematic way to construct proofs. In this section, we will explore the syntax and rules of natural deduction, as well as how to apply them to create logical proofs.

Syntax of Natural Deduction

The syntax of natural deduction involves the use of symbols to represent logical statements. The basic symbols include:

• p, q, r: propositional variables that represent simple statements.
• ∧: conjunction, meaning 'and'.
• ∨: disjunction, meaning 'or'.
• →: implication, meaning 'if...then'.
• ¬: negation, meaning 'not'.

For example, if p represents the statement 'It is raining' and q represents 'I will take an umbrella', we can express the statement 'If it is raining, then I will take an umbrella' as p → q.

Inference Rules

Natural deduction uses a set of inference rules to derive conclusions. The most common rules include:

1. Modus Ponens: If you have p and p → q, you can conclude q.
2. Modus Tollens: If you have ¬q and p → q, you can conclude ¬p.
3. Conjunction Introduction: If you have p and q, you can conclude p ∧ q.
4. Conjunction Elimination: If you have p ∧ q, you can conclude p or q.
5. Disjunction Introduction: If you have p, you can conclude p ∨ q.
6. Implication Introduction: If assuming p leads to q, you can conclude p → q.
7. Negation Introduction: If assuming p leads to a contradiction, you can conclude ¬p.

Constructing a Proof

To construct a proof using natural deduction, follow these steps:

1. Identify your premises and what you want to prove.
2. Use the inference rules to derive new statements from the premises.
3. Continue deriving statements until you reach the conclusion.

Example Proof

Let us consider the following premises:

• Premise 1: p → q
• Premise 2: p

We want to prove q.

Step 1: Start with the premises:

1. p → q   (Premise 1)
2. p       (Premise 2)

Step 2: Apply Modus Ponens (if p is true and p → q is true, then q must be true):

3. q       (From 1 and 2 by Modus Ponens)

Thus, we have derived q from our premises.

Proof Strategies

When constructing proofs, there are several strategies you can employ:

• Direct Proof: Start from the premises and apply inference rules directly to reach the conclusion.
• Indirect Proof: Assume the negation of what you want to prove and show that this leads to a contradiction.
• Proof by Cases: Consider different cases based on the premises and prove the conclusion for each case.

Example of Indirect Proof

Let us consider the statement: If p is true, then q is true. We want to prove ¬q → ¬p.

Step 1: Assume ¬q.

1. p → q   (Assumption)
2. ¬q      (Assumption)

Step 2: By Modus Tollens, since ¬q is true, we can conclude ¬p must also be true.

3. ¬p      (From 1 and 2 by Modus Tollens)

Common Mistakes

Practice Problems

To strengthen your understanding of natural deduction, try the following practice problems:

1. Given the premises p → r and ¬r, prove ¬p.
2. Using the premises p, p → q, and ¬q, show that ¬p must be true.
3. Assuming p ∧ q, derive p and q separately.
4. Prove p → (q → p) using natural deduction.

Summary

• Natural deduction is a method for deriving conclusions from premises using rules of inference.
• Familiarise yourself with the syntax and symbols used in natural deduction.
• Practice constructing proofs using various strategies.
• Be aware of common mistakes when applying inference rules.

Check your understanding

1. What is the purpose of natural deduction in formal logic?
2. List three common inference rules used in natural deduction.
3. How would you prove p → q using the assumption of p?
4. What is a common mistake to avoid when using natural deduction?