Subsection 3.4.3 A List of Inference Rules
Modus Ponens : p
p → q
∴ q
From premises \(p\) and \(p \rightarrow q\) conclude \(q\)
From \(R \rightarrow W \) (rain implies wet sidewalks) and R (it’s raining), conclude W (wet sidewalks).
We’ll prove the soundness of this rule so that we can see how to construct such soundness proofs. What we need to prove is that the following statement is a tautology (it is true for all values of p and q ):
\(( ∧ → )) →\)
Here’s the truth table that does that:
p q p → q p ∧ (p → q ) ( p ∧ (p → q )) → q T T T T T T F F F T F T T F T F F T F T
The last column contains all T ’s. So we have a tautology.
We’ll omit the proofs of the rest of the rules presented here. You should prove them yourself. You can use the Truth Table app to do that.
Modus Tollens : p → q p → ¬ q
¬ q q
∴ ¬ p ∴ ¬ p
The first version says that, from premises p → q and ¬ q , conclude ¬ p . Since p guarantees q , we cannot have p true unless q is true too. Since q is false, p must also be false. We don’t actually need the second version, since, in the first one, q can be any logical expression, including a negated one. But the second version may help us avoid an extra application of the Double Negation rule.
From \(R \rightarrow W \) (rain implies wet sidewalks) and \(\neg W \) (the sidewalks aren’t wet), conclude \(\neg R\) (it’s not raining).
Recall the identity that we called Contrapositive: ( p → q ) ≡ (¬ q → ¬ p ). If we start with:
( p → q ) and apply the Contrapositive identity, we get:
(¬ q → ¬ p ).
If we’re given this, plus ¬ q , we can use Modus Ponens to get:
¬ p .
Modus Tollens lets us do the same thing in a single step.
Sometimes it is helpful to think of reasoning by Modus Tollens as reasoning backward.
Disjunctive Syllogism : p ∨ q p ∨ q ¬ p ∨ q p ∨ ¬ q
¬ q ¬ p p q
∴ p ∴ q ∴ q ∴ p
The first version says that, from premises p ∨ q and¬ p , conclude p. If at least one of p and q has to be true but we know that q isn’t, then p has to be. Again, we don’t need any other versions. But they may shorten our proofs. The second version is equivalent since or is commutative. The last two, again, may let us do in one step something that would take extra steps involving Double Negation.
\(J \vee M \) John or Mary has to drive me to the store.
\(\neg J\) “Not I,” says John.
\(M \) Mary has to drive.
Here’s a real example of Disjunctive Syllogism taken from a news story:
In commenting on the consistency of Zimmerman's story as well as Zimmerman's apparent relief when falsely told there was a video of the confrontation, Serino said Zimmerman had to be either a pathological liar or telling the truth.
"If we were to take pathological liar off the table…do you think he was telling the truth?" asked defense attorney Mark O'Mara.
Simplification : p ∧ q p ∧ q
∴ p ∴ q
From the single premise p ∧ q , conclude p . Or conclude q . If both p and q are true, then either of them alone must also be true.
\(C \wedge K \) Chris and Kate are coming to the party.
\(C \) Chris is coming to the party.
Addition : p p
∴ p ∨ q ∴ q ∨ p
From premise p , conclude that p or q (in either order) must be true for any q . Notice that q can be anything and can be either true or false because, if p is true, q is irrelevant to the truth value of its disjunction with p : p ∨ q and q ∨ p must also be true.
Conjunction : p
q
∴ p ∧ q
This seems to be embarrassingly trivial. What is actually happening, however, is that from two separate premises p and q we are allowed to conclude the conjunction of the two of them.
Hypothetical Syllogism : p → q
q → r
∴ p → r
From premises p → q and q → r , conclude p → r. This looks very similar to a double use of Modus Ponens. It says, given a chain of implications (where the conclusion of one is the premise of the next), the leading premise must imply the final conclusion.
Why is this useful? If we know p then we can use p → q to derive q . Then we can use q → r to derive r and we’re done. But suppose that we don’t (yet) know p . This rule lets us conclude that p (if it’s true) would imply r . Maybe this tells us, if we’re looking for a way to prove r , that we should spend some effort trying to prove p .
Too EarlySuppose that we want to prove that, if I’ve gotten up before 4:00 am, I’m cranky. (Seems obvious, but proofs are what we’re doing here.) Give names to the following statements:
Uby4: I got up before 4:00am.
Cranky: I’m cranky.
Tired: I’m tired.
Assume the following premises:
Uby4 Tired If I got up before 4:00 am, I’m tired.
Tired Cranky If I’m tired, I’m cranky.
Conclude:
Uby4 \(\rightarrow \) Cranky
Now we’re ready to spring into action with a conclusion whenever it happens that I got up ridiculously early.
Exercises Exercises
Exercise Group.
1.
1. Give names to the following statements:
C : Cody is late.
M : Mary is late.
P : Peter is late.
Assume the following premises:
[1] C ∨ M Cody or Mary is late.
[2] P ∨ C Peter or Cody is late.
[3] ¬ M Mary isn’t late.
[4] P Peter is late.
Using our inference rules, we can conclude:
[5] C Cody is late.
How did we derive that conclusion?
We applied Disjunctive Syllogism to [2] and [4].
We applied Modus Tollens to [2] and [4].
We applied Modus Ponens to [1] and [4].
We applied Disjunctive Syllogism to [1] and [3].
We applied Modus Tollens to [1] and [3].
2.
2. Give names to the following statements:
C : Chris likes apples.
M : Mary likes apples.
P : Peter likes apples.
Assume the following premises:
[1] C → M If Chris likes apples, so does Mary.
[2] P → M If Peter likes apples, so does Mary.
[3] C Chris likes apples.
[4] ¬ P Peter doesn’t like apples.
Using our inference rules, we can conclude:
[5] M Mary likes apples.
How did we derive that conclusion?
We applied Modus Ponens to [1] and [3].
We applied Modus Ponens to [2] and [4].
We applied Modus Tollens to [1] and [3].
We applied Modus Tollens to [1] and [4].
We applied Hypothetical Syllogism to [1] and [2].
3.
3. Give names to the following statements:
C : Chris likes math.
P : Pat likes math.
Y : Taylor likes math.
Assume the following premises:
[1] C → P If Chris likes math, so does Pat.
[2] C → Y If Chris likes math, so does Taylor.
[3] Y Taylor likes math.
[4] ¬ P Pat doesn’t like math.
Using our inference rules, we can conclude:
[5] ¬ C Chris doesn’t like math.
How did we derive that conclusion?
We applied Modus Ponens to [1] and [4].
We applied Modus Tollens to [1] and [4].
We applied Modus Ponens to [2] and [3].
We applied Modus Tollens to [2] and [3].
We applied Hypothetical Syllogism to [1] and [2].