Master the art of formal proof. This module introduces the 19 rules of inference and replacement, allowing you to systematically prove the validity of complex deductive arguments step-by-step.
1. Beyond Truth Tables: The Need for Proofs
In the previous modules, you learned how truth tables can be used to determine the validity of any deductive argument. However, for an argument with five or more simple statements, a truth table would require 32 rows or more. This is not only tedious but impractical.
Instead, we can prove an argument's validity by deducing its conclusion from its premises in a series of short, simple steps. This is the method of deduction. It relies on a set of elementary argument forms that are already known to be valid. These are our tools for building proofs.
2. Understanding the Symbols
Before diving into the rules, let's quickly review the symbols used in formal logic. These symbols allow us to translate complex sentences into precise, unambiguous statements. We use capital letters (A, B, C...) to represent simple statements.
Negation: ~ (the "tilde")
This means "not". It simply reverses the truth value of a statement. If 'R' stands for "It is raining," then ~R means "It is not raining."
Conjunction: • (the "dot")
This means "and". A conjunction is only true if both statements it joins are true. If 'R' is "It is raining" and 'C' is "It is cold," then R • C means "It is raining and it is cold."
Disjunction: v (the "wedge")
This means "or". A disjunction is true if at least one of the statements it joins is true. R v C means "It is raining or it is cold (or both)." This is an inclusive "or".
Implication: ⊃ (the "horseshoe")
This means "if... then...". It connects an antecedent (the "if" part) to a consequent (the "then" part). For example, if 'R' is "It is raining" and 'G' is "The ground is wet," then R ⊃ G means "If it is raining, then the ground is wet."
Equivalence: ≡ (the "triple bar")
This means "if and only if". It states that two statements have the same truth value—they are either both true or both false. p ≡ q is the same as saying (p ⊃ q) • (q ⊃ p).
Proof Format:
The standard format lists premises first, followed by a forward slash (/∴) and the conclusion you are trying to reach. Each new line you add must be justified by citing the previous line number(s) and the rule used.
3. The First 9 Tools: Rules of Inference
The first set of tools are the Rules of Inference. Think of these as the fundamental, valid moves you are allowed to make. A crucial point: these rules must be applied to entire lines of a proof, not to parts of lines.
1. Modus Ponens (M.P.)
p ⊃ q p /∴ q
2. Modus Tollens (M.T.)
p ⊃ q ~q /∴ ~p
3. Hypothetical Syllogism (H.S.)
p ⊃ q q ⊃ r /∴ p ⊃ r
4. Disjunctive Syllogism (D.S.)
p v q ~p /∴ q
5. Constructive Dilemma (C.D.)
(p⊃q)•(r⊃s) p v r /∴ q v s
6. Destructive Dilemma (D.D.)
(p⊃q)•(r⊃s) ~q v ~s /∴ ~p v ~r
7. Simplification (Simp.)
p • q /∴ p
8. Conjunction (Conj.)
p q /∴ p • q
9. Addition (Add.)
p /∴ p v q
Why are these rules valid?
Each of these rules can be proven valid with a truth table. An argument form is valid if and only if there is no possible instance where all premises are true and the conclusion is false. Let's look at Modus Ponens (M.P.).
The premises are p ⊃ q and p. The conclusion is q.
| p | q | Premise 1 (p ⊃ q) | Premise 2 (p) | Conclusion (q) |
|---|---|---|---|---|
| T | T | T | T | T |
| T | F | F | T | F |
| F | T | T | F | T |
| F | F | T | F | F |
Notice the first row: it is the only row where both premises are true. In that row, the conclusion is also true. There is no row with all true premises and a false conclusion, so the rule is valid.
4. Formal Proofs in Action
A formal proof of validity is a sequence of statements where each step is either a premise or follows from the preceding steps by one of the valid rules. The final step is the conclusion of the argument.
Example Proof
Let's formally prove the argument: "If it is a tree, it has roots. If it has roots, it absorbs minerals. It is a tree. Therefore, it absorbs minerals."
Symbolized as: T ⊃ R, R ⊃ M, T /∴ M
| Line | Statement | Justification |
|---|---|---|
| 1. | T ⊃ R | Premise |
| 2. | R ⊃ M | Premise |
| 3. | T | Premise /∴ M |
| 4. | T ⊃ M | 1, 2, H.S. |
| 5. | M | 4, 3, M.P. |
In step 4, we use Hypothetical Syllogism on lines 1 and 2 to create a new conditional. In step 5, we use Modus Ponens on our new line 4 and our premise on line 3 to derive the conclusion.
5. Expanding the Toolkit: Rules of Replacement
The nine rules of inference are powerful, but they aren't sufficient to prove every valid argument. For example, how would you prove the simple argument `A • B /∴ B`? Simplification only lets you infer `A`! To solve this, we would first need to use Commutation to change `A • B` to `B • A`, and then use Simplification. This requires a second set of tools: the Rules of Replacement.
These rules are based on logical equivalence. Each pair of expressions is logically identical, meaning you can replace one with the other anywhere it appears—even inside a larger statement. This is a key difference from the Rules of Inference, which must apply to an entire line.
Key Distinction: Replacement vs. Substitution
This is a subtle but important point from the original source. Replacement (our new rules) lets you swap logically equivalent statements (e.g., `(p ⊃ q)` for `(~p v q)`). Substitution involves replacing a simple variable (like `p`) with a complex statement (like `(A v B)`) consistently throughout an argument form. The 19 rules we use in proofs are rules of inference and replacement, not substitution.
1. De Morgan's Theorems (De M.)
~(p • q) ≡ (~p v ~q) ~(p v q) ≡ (~p • ~q)
To negate a conjunction or disjunction, you "distribute" the negation to each term and flip the operator. "Not (p and q)" is the same as "Not p or not q". Likewise, "Not (p or q)" is the same as "Not p and not q".
2. Commutation (Com.)
(p v q) ≡ (q v p) (p • q) ≡ (q • p)
The order of terms in a conjunction or disjunction doesn't affect the truth value. "p and q" is the same as "q and p". This is one of the most simple and intuitive rules.
3. Association (Assoc.)
[p v (q v r)] ≡ [(p v q) v r] [p • (q • r)] ≡ [(p • q) • r]
When you have a chain of only conjunctions or only disjunctions, it doesn't matter how you group them with parentheses. This rule lets you regroup them as needed.
4. Distribution (Dist.)
[p • (q v r)] ≡ [(p • q) v (p • r)] [p v (q • r)] ≡ [(p v q) • (p v r)]
This rule lets you "distribute" one logical operator across another. It's similar to distribution in algebra, like a(b+c) = ab+ac. This is powerful for rearranging complex statements.
5. Double Negation (D.N.)
p ≡ ~~p
A statement is logically equivalent to its double negation. Two "nots" cancel each other out, allowing you to add or remove two tilde symbols (`~~`) from any statement.
6. Transposition (Trans.)
(p ⊃ q) ≡ (~q ⊃ ~p)
This allows you to flip a conditional statement by negating both terms. For example, "If it is a dog, then it is an animal" is equivalent to "If it is not an animal, then it is not a dog."
7. Material Implication (Impl.)
(p ⊃ q) ≡ (~p v q)
This rule states that a conditional "If p then q" is logically the same as saying "Either p is false, or q is true." It's a key rule for converting between conditional and disjunctive forms.
8. Material Equivalence (Equiv.)
(p ≡ q) ≡ [(p ⊃ q) • (q ⊃ p)] (p ≡ q) ≡ [(p • q) v (~p • ~q)]
A biconditional ("p if and only if q") is equivalent to a two-way conditional (p implies q AND q implies p). It's also equivalent to stating that p and q share the same truth value (they are both true OR they are both false).
9. Exportation (Exp.)
[(p • q) ⊃ r] ≡ [p ⊃ (q ⊃ r)]
This rule allows us to "export" part of a conjoined antecedent. It says that "If p and q are true, then r is true" is the same as "If p is true, then it follows that if q is true, r is true."
10. Tautology (Taut.)
p ≡ (p v p) p ≡ (p • p)
A statement is equivalent to itself joined with "and" or "or". "p" means the same thing as "p and p". This is useful for simplifying expressions like `(A • A)` to `A` or setting up other rules.
6. Strategy and Technique
Unlike truth tables, formal proofs require strategy. There's no single recipe for success, but here are some helpful hints:
- Start Simple: Always look for immediate sub-conclusions you can draw from the premises using the first nine Rules of Inference.
- Work Backwards: Look at your conclusion. What rule could produce it? What pieces would you need for that rule to work? This helps identify your penultimate goal.
- Eliminate Mismatches: If a letter appears in the premises but not the conclusion, you'll need a way to eliminate it. Hypothetical Syllogism (to remove a middle term) or Distribution are often useful here.
- Introduce What's Missing: If a letter is in the conclusion but not the premises, you'll almost certainly need to use Addition (`p /∴ p v q`) to introduce it.
A More Complex Proof
Let's prove an argument that requires both inference and replacement rules: (A • A) ⊃ (R • S), ~R v ~S /∴ ~A
| Line | Statement | Justification |
|---|---|---|
| 1. | (A • A) ⊃ (R • S) | Premise |
| 2. | ~R v ~S | Premise /∴ ~A |
| 3. | A ⊃ (R • S) | 1, Tautology |
| 4. | ~(R • S) | 2, De Morgan's |
| 5. | ~A | 3, 4, M.T. |
Strategy: Seeing ~A as the goal, Modus Tollens is a likely candidate. To use it on line 3, we need ~(R • S). We look at premise 2 and see that, thanks to De Morgan's theorem, ~R v ~S is equivalent to ~(R • S). The path becomes clear. We also simplify `(A • A)` to `A` using Tautology to set up the final Modus Tollens step.
7. Test Your Skills: Check Your Toolkit
Apply what you've learned about the rules of deduction. Analyze the following questions.
1. You are given the premises P ⊃ Q and ~Q. What can you immediately deduce, and by which rule?
2. In a proof, you have the line ~(P v Q). Which rule of replacement allows you to change this to ~P • ~Q?
3. What is the key difference between how Rules of Inference and Rules of Replacement are applied?
4. To prove the extremely simple argument "A /∴ A v B", which single, simple rule is required?