Replacement Rules
(Pt. I)

 

 

Important Concepts

 

SD+

By now you should be comfortable with the general notion of natural deduction, even if you are still working out some kinks. Today we introduce another logical system: SD+. As you learned in the Important Concepts above, SD+ has more inference rules and some handy replacement rules. These new tools will you grant you the capacity to make your derivations radically shorter in some cases. A complete list of the rules that are found in SD+ but not in SD can be found here. Let's make sure you understand some of the most important rules.

DeMorgan's Rule (DM)

I find DeMorgan's to be one of the most handy tools of SD+. The general idea is that if you have a negated conjunction, you can turn it into a disjunction where both disjuncts are negated. It's important to not shy away from double negations when using this rule. For example, "~(A & ~B)" should be replaced by "~A ∨ ~~B".

DM also applies to negated disjunctions, which you can replace with a conjunction where both conjuncts are negated. For example, "~(A ∨ ~B)" can be replaced by "~A & ~~B".

Double Negation (DN) and Disjunctive Syllogism (DS)

Let's continue with the sentence from the preceding example: "~A ∨ ~~B". Let's suppose that you are trying to derive "B" and you have "A" as one of your assumptions. You want to do a disjunctive syllogism using "~A ∨ ~~B" and "A". The ingredients are right, but they need a little preparation. Recall that DS requires a disjunction and a negation of one of the disjuncts. In "~A ∨ ~~B", "~A" is the left disjunct and "~~B" is the right disjunct. In order to truly have a negation of the left disjunct, you need "~~A". Luckily, with DN, you can do just that. First, using DN, replace "A" with "~~A". Now you can use "~~A" and "~A ∨ ~~B" to infer "~~B", using DS. Lastly, recall that you are looking to derive "B". Simply apply DN to "~~B" and obtain "B". See the derivation below.

 

Sample of proof in SD+

 

Hypothetical Syllogism (HS) and Implication (Imp)

HS is a valuable tool for working with conditionals. The idea is simple. If you have two conditionals and there is a "middle man", where some sentence of TL is both the consequent of one conditional and the antecedent of another, you can get rid of the middle man and form just one conditional. For example, if you have "A ⊃ B" and "B ⊃ C", then you can infer "A ⊃ C". Similarly, if you have "(M ∨ (N ≡ O)) ⊃ ~(R & S)" and "~(R & S) ⊃ ((T & U) & V)", then you can infer "(M ∨ (N ≡ O)) ⊃ ((T & U) & V)".

Equally useful for working with conditionals is Imp. All you need is a disjunction where the left disjunct is negated, and you can eliminate the tilde and replace the wedge with a horseshoe. For example, "~A ∨ B" can be replaced with "A ⊃ B". Similarly, "~(R & S) ∨ ((T & U) & V)" can be replaced with "(R & S) ⊃ ((T & U) & V)".

These, in combination with association, commutation, and distribution, should go a long way towards making your proofs shorter and more elegant.

 

Remember!!!

Replacement rules work both ways!

 

Tablet Time!

 

Final comments

As mentioned in Tablet Time!, you can use the replacement rules in subsentential components, i.e., smaller parts of the larger sentence. For example, take a look at the following sentence:

(A & B) ∨ (C ⊃ D)

As we know by taking a look at our reference sheet for the rules of replacement, the rule known as commutation allows us to shift about the elements of a conjunction and/or a disjunction. The sentence above contains a conjunction as a subsentential component, namely the left disjunct. As such, we can apply commutation on it like this:

(B & A) ∨ (C ⊃ D)

With that step completed, we can also apply commutation to the whole thing:

(C ⊃ D) ∨ (B & A)

Now look at the following sentence:

~~~~~[(~B & ~C) ≡ (D ∨ E)]

We can apply a replacement rule just to the left part of the bracketed biconditional:

~~~~~[~(B ∨ C) ≡ (D ∨ E)]

Can you tell which rule it was? (Hint: It was DM.)

 

 

FYI

Homework— The Logic Book (6e), Chapter 5