Rules of Replacement
We complete our development of the proof procedure for the propositional calculus by making use of another useful way of validly moving from step to step.
Since two logically equivalent statements have the same truth-value on every possible combination of truth-values for their component parts,
no change in the truth-value of any statement occurs when we replace one of them with the other.
Thus, when constructing proofs of validity, we can safely use a statement containing either one of a pair of logical equivalents as the premise for a step whose conclusion is exactly the same, except that it contains the other one.
Although this would work for any pair of logically equivalent statement forms, remembering all of them would be cumbersome. Instead, we will once again rely upon a short list of ten
rules of replacement in our construction of proofs, and we have
already examined five of them:
D.N. p ≡ ~~p
DeM. ~(p • q) ≡ (~p ∨ ~q)
~(p ∨ q) ≡ (~p • ~q)
Impl. (p⊃q) ≡ (~p ∨ q)
Equiv. [p≡q] ≡ [(p⊃q) • (q⊃p)]
[p≡q] ≡ [(p • q) ∨ (~p • ~q)]
Trans. (p ⊃ q) ≡ (~q ⊃ ~p)
We'll add just five more, making a total of ten tautologous biconditionals to be used as rules of replacement.
| p | q | (p ∨ q) | ≡ | (q ∨ p)
|
|---|
| T | T | T | T | T
|
|---|
| T | F | T | T | T
|
|---|
| F | T | T | T | T
|
|---|
| F | F | F | T | F
|
|---|
The rule of replacement called Commutation (Comm.) shows that statements of certain forms can simply be reversed.
In one form, this applies to all disjuctions:
(p ∨ q) ≡ (q ∨ p)
| p | q | (p • q) | ≡ | (q • p)
|
|---|
| T | T | T | T | T
|
|---|
| T | F | F | T | F
|
|---|
| F | T | F | T | F
|
|---|
| F | F | F | T | F
|
|---|
In its second form, Commutation establishes the same logical equivalence with respect to conjunctions:
(p • q) ≡ (q • p)
The truth-tables for these two varieties of commutation show that we can safely replace any disjunction or conjunction with another in which the component elements of the original have been switched, since the truth values of the commuted compound statements do not change under any of the possible conditions.
Association (Assoc.) permits modification of the parenthetical grouping of certain statements.
| p | q | r | [p∨(q∨r)] | ≡ | [(p∨q)∨r]
|
|---|
| T | T | T | T | T | T
|
|---|
| T | T | F | T | T | T
|
|---|
| T | F | T | T | T | T
|
|---|
| T | F | F | T | T | T
|
|---|
| F | T | T | T | T | T
|
|---|
| F | T | F | T | T | T
|
|---|
| F | F | T | T | T | T
|
|---|
| F | F | F | F | T | F
|
|---|
Applied to disjunction, it has the form:
[p ∨ (q∨r)] ≡ [(p∨q) ∨ r]
This shows that the grouping of a string of disjuncts is irrelevant to the truth-value of the compound statement form.
| p | q | r | [p•(q•r)] | ≡ | [(p•q)•r]
|
|---|
| T | T | T | T | T | T
|
|---|
| T | T | F | F | T | F
|
|---|
| T | F | T | F | T | F
|
|---|
| T | F | F | F | T | F
|
|---|
| F | T | T | F | T | F
|
|---|
| F | T | F | F | T | F
|
|---|
| F | F | T | F | T | F
|
|---|
| F | F | F | F | T | F
|
|---|
Applied to conjunction, it has the form:
[p • (q•r)] ≡ [(p•q) • r]
Used in tandem, the Commutative and Associative replacement rules make it possible to rearrange any series of disjunctions or conjunctions—no matter how long and complicated—into any new order and arrangement we wish to have.
| p | q | r | p•(q∨r) | ≡ | (p•q)∨(p•r)
|
|---|
| T | T | T | T | T | T
|
|---|
| T | T | F | T | T | T
|
|---|
| T | F | T | T | T | T
|
|---|
| T | F | F | F | T | F
|
|---|
| F | T | T | F | T | F
|
|---|
| F | T | F | F | T | F
|
|---|
| F | F | T | F | T | F
|
|---|
| F | F | F | F | T | F
|
|---|
The rule called Distribution (Dist.) exhibits the systematic features of statements in which both disjunctions and conjunctions appear.
In one of its two forms, a conjunct is distributed over a disjunction:
[p • (q∨r)]≡[(p•q) ∨ (p•r)]
| p | q | r | p∨(q•r) | ≡ | (p∨q)•(p∨r)
|
|---|
| T | T | T | T | T | T
|
|---|
| T | T | F | T | T | T
|
|---|
| T | F | T | T | T | T
|
|---|
| T | F | F | T | T | T
|
|---|
| F | T | T | T | T | T
|
|---|
| F | T | F | F | T | F
|
|---|
| F | F | T | F | T | F
|
|---|
| F | F | F | F | T | F
|
|---|
In the other form, a disjunct is distributed over a conjunction:
[p ∨ (q•r)]≡[(p∨q) • (p∨r)]
The truth-tables should make it clear that both forms of distribution are reliable rules of replacement.
| p | q | r | (p•q)⊃r | ≡ | p⊃(q⊃r)
|
|---|
| T | T | T | T | T | T
|
|---|
| T | T | F | F | T | F
|
|---|
| T | F | T | T | T | T
|
|---|
| T | F | F | T | T | T
|
|---|
| F | T | T | T | T | T
|
|---|
| F | T | F | T | T | T
|
|---|
| F | F | T | T | T | T
|
|---|
| F | F | F | T | T | T
|
|---|
Exportation (Exp.) is a rule of replacement of the form:
[(p•q)⊃r)]≡[p⊃(q⊃r)]
The truth-table at the right demonstrates that statements of these two forms are logically equivalent.
Please take careful notice of the difference between Exportation as a rule of replacement and the rule of inference called
Absorption. Although they bear some similarity of structure, the rules are distinct and can be used differently in the construction of proofs.
Finally, there are two forms of the rule called Tautology (Taut.):
the first involves disjunction,
p ≡ (p ∨ p)
and the second involves conjunction:
p ≡ (p • p)
In each case, the rule permits replacement of any statement by (or with) another statement that is simply the disjunction or conjunction of the original statement with itself. Although such reasoning is rare in ordinary life, it will perform a significant formal role in our construction of proofs of validity.
Using the rules of replacement in the construction of proofs is a fairly straightforward procedure.
Since the rules are biconditionals, the replacement can work in either direction—right side for left, or left side for right.
What is more, since the statement forms on either side are logically equivalent, they can be used to replace each other wherever they occur, even as component parts of a line.
(When applying the nine rules of inference, on the other hand, we must always work with whole lines of a proof.)
Consider the following argument:
A ∨ (B • ~C)
A ⊃ D
~D ⊃ C
____________
D
As before, we begin by numbering each of the premises:
1. A ∨ (B • ~C) premise
2. A ⊃ D premise
3. ~D ⊃ C premise
Next, notice that we can use our rules of replacement and inference to derive some part of the information conveyed by the first premise:
1. A ∨ (B • ~C) premise
2. A ⊃ D premise
3. ~D ⊃ C premise
4. (A ∨ B) • (A ∨ ~C) 1 Dist.
5. (A ∨ ~C) • (A ∨ B) 4 Comm.
6. A ∨ ~C 5 Simp.
So long as each step is justified by reference to an earlier step (or steps) in the proof and to one of the nineteen rules, it must be a valid derivation.
Next, let's work with the third premise a bit:
1. A ∨ (B • ~C) premise
2. A ⊃ D premise
3. ~D ⊃ C premise
4. (A ∨ B) • (A ∨ ~C) 1 Dist.
5. (A ∨ ~C) • (A ∨ B) 4 Comm.
6. A ∨ ~C 5 Simp.
7. ~C ⊃ ~~D 3 Trans.
8. ~C ⊃ D 7 D.N.
Again, each step is justified by application of one of the rules of replacement to all or part of a preceding line in the proof.
Now conjoin the second premise with our eighth line, and we've set up a constructive dilemma:
1. A ∨ (B • ~C) premise
2. A ⊃ D premise
3. ~D ⊃ C premise
4. (A ∨ B) • (A ∨ ~C) 1 Dist.
5. (A ∨ ~C) • (A ∨ B) 4 Comm.
6. A ∨ ~C 5 Simp.
7. ~C ⊃ ~~D 3 Trans.
8. ~C ⊃ D 7 D.N.
9. (A ⊃ D) • (~C ⊃ D) 2, 8 Conj.
10. D ∨ D 9, 6 C.D.
All that remains is to apply Tautology in order to reach our intended conclusion, so the entire proof will look like this:
1. A ∨ (B • ~C) premise
2. A ⊃ D premise
3. ~D ⊃ C premise
4. (A ∨ B) • (A ∨ ~C) 1 Dist.
5. (A ∨ ~C) • (A ∨ B) 4 Comm.
6. A ∨ ~C 5 Simp.
7. ~C ⊃ ~~D 3 Trans.
8. ~C ⊃ D 7 D.N.
9. (A ⊃ D) • (~C ⊃ D) 2, 8 Conj.
10. D ∨ D 9, 6 C.D.
11. D 10 Taut.
Don't worry if the intermediate stages of this proof were a little puzzling as we went along; what matters for right now is that you understand the use of the rules of replacement along with the rules of inference.
The Philosophy Pages by Garth Kemerling are licensed under a Creative Commons Attribution-ShareAlike 3.0 Unported License.
Permissions beyond the scope of this license may be available at http://www.philosophypages.com/referral/contact.htm.
©1997, 2011 Garth Kemerling.
Last modified 12 November 2011.
Questions, comments, and suggestions may be sent to:
the Contact Page.
