Rules of Replacement

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.

Commutation

p  q (p ∨ q)(q ∨ p)
TTTTT
TFTTT
FTTTT
FFFTF

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)
TTTTT
TFFTF
FTFTF
FFFTF
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

Association (Assoc.) permits modification of the parenthetical grouping of certain statements.

p  q  r [p∨(q∨r)][(p∨q)∨r]
TTTTTT
TTFTTT
TFTTTT
TFFTTT
FTTTTT
FTFTTT
FFTTTT
FFFFTF
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]
TTTTTT
TTFFTF
TFTFTF
TFFFTF
FTTFTF
FTFFTF
FFTFTF
FFFFTF
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.

Distribution

p  q  r p•(q∨r)(p•q)∨(p•r)
TTTTTT
TTFTTT
TFTTTT
TFFFTF
FTTFTF
FTFFTF
FFTFTF
FFFFTF

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)
TTTTTT
TTFTTT
TFTTTT
TFFTTT
FTTTTT
FTFFTF
FFTFTF
FFFFTF
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.

Exportation

p  q  r (p•q)⊃rp⊃(q⊃r)
TTTTTT
TTFFTF
TFTTTT
TFFTTT
FTTTTT
FTFTTT
FFTTTT
FFFTTT

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.

Tautology

p (p ∨ p)
TTT
FTF

Finally, there are two forms of the rule called Tautology (Taut.):
the first involves disjunction,

p ≡ (p ∨ p)

p (p • p)
TTT
FTF
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.

Replacement in Proofs

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. 