Natural Deduction System in Propositional Logic: Inference Rules and Proof Strategies

Study Notes

Natural Deduction System: A Deep Dive into Propositional Logic, Inference Rules, and More

Natural deduction is a powerful and intuitive system for proving statements in logic, with a focus on clearly displaying the reasoning behind each conclusion. In this article, we'll explore the beauty of natural deduction as it applies to propositional logic and some of its essential components: inference rules, proof strategies, and assumptions.

Propositional Logic

Propositional logic is the foundation of natural deduction, where we reason with atomic propositions, connectives (like AND, OR, NOT, and IMPLIES), and logical operators. Propositions are statements that can be true or false, and connectives help us build more complex propositions from simpler ones.

For example, let's look at the proposition A AND B:

If A is true, and B is true, then A AND B is true.
If A is false, or B is false, then A AND B is false.

In natural deduction, we use symbols like p, q, r, etc., to represent propositions, and we'll refer to these as atomic propositions.

Inference Rules

Inference rules are the fundamental building blocks of natural deduction. They dictate how we can construct valid arguments and determine the truth of propositions. Natural deduction employs a subset of inference rules, which includes:

Assumption (⊦ A): This rule allows us to temporarily assume that a statement is true for the purpose of a derivation.
Conjunction Elimination (A ∧ B ⊦ A, A ∧ B ⊦ B): This rule allows us to derive either A or B from A ∧ B.
Disjunction Elimination (A ∨ B, NOT A ⊦ B): This rule allows us to derive B from A ∨ B and NOT A.
Conditional Elimination (A ⇒ B, A ⊦ B): This rule allows us to derive B from A ⇒ B and A.
Negation Elimination (NOT A ⊦ A ⇒ B, A ⊦ NOT(NOT B ∧ A)): This rule allows us to derive A ⇒ B from NOT A ⊦ B or NOT(NOT B ∧ A) (the absurdity form).

Proof Strategies

Natural deduction is both direct and indirect, following a collection of strategies to construct proofs.

Direct Proof: This strategy involves using inference rules to derive the conclusion from the given assumptions.

For example, let's prove the proposition (A ∧ NOT B) ⇒ NOT (A ∨ B) using direct proof:

1. A ∧ NOT B (Assumption)
2. A (1, ∧-Elimination)
3. NOT A ⇒ NOT (A ∨ B) (Assumption)
4. A ∨ B (Assumption)
5. A (4, ∨-Elimination) (Subproof)
6. NOT A (1, ∧-Elimination)
7. NOT (A ∨ B) (5, 6, 3, ⇒-Elimination)
8. NOT (A ∨ B) (2-7, Disjunction-Tautology Elimination)

Proof:
1. A ∧ NOT B (Assumption)
2. A (1, ∧-Elimination)
3. A ∨ B (Assumption)
4. A (3-4, ∨-Elimination)
5. NOT A (2, ∧-Elimination)
6. NOT (A ∨ B) (4, 5, 3, ⇒-Elimination)
7. NOT (A ∨ B) (2-6, Disjunction-Tautology Elimination)

QED: (A ∧ NOT B) ⇒ NOT (A ∨ B)

Indirect Proof (Proof by Contradiction): This strategy involves assuming the negation of the conclusion and then deriving a contradiction to conclude that the original statement is true.

For example, let's prove the proposition ∀x (A(x) ∨ B(x)) ⇒ ∃x A(x) ∧ ∃x B(x) using indirect proof:

1. ∀x (A(x) ∨ B(x)) (Assumption)
2. ¬(∃x A(x) ∧ ∃x B(x)) (Assumption)
3. ¬∃x A(x) ∧ ¬∃x B(x) (2, ∃-Elimination)
4. ¬∃x A(x) (3, ∧-Elimination)
5. ∀x A(x) ⇒ NOT A(t) (Assumption) for arbitrary t
6. ∃x (A(x) ∧ NOT A(t)) (4, ¬∃-Elimination)
7. A(s) ∧ NOT A(t) (6, ∃-Elimination)
8. A(s) (7, ∧-Elimination)
9. A(s) ∨ B(s) (1, Universal-Instantiation)
10. B(s) (8, 9, ⇒-Elimination)
11. ∃x B(x) (10, ∃-Introduction)
12. A(t) (5, 4, ∀-Elimination)
13. NOT A(t) (7, ∧-Elimination)
14. ¬A(t) (5, 12, ⇒-Elimination)
15. ∀x A

Description

Explore the fundamentals of natural deduction in propositional logic, including inference rules like Assumption, Conjunction Elimination, Disjunction Elimination, Conditional Elimination, and Negation Elimination. Delve into proof strategies such as Direct Proof and Indirect Proof (Proof by Contradiction) to construct valid arguments and derive conclusions.