Reasoning: An Introduction to Logic, Sets, and Functions

Subsection 3.4.4 More Inference Rules

Contradictory Premises : p

p

¬p

∴ q

From premises p and ¬p , conclude q for absolutely any q. This may seem the strangest of the lot. The statement q can come from thin air. It may be ridiculous. Nevertheless, for any p , the statement p ∧ ¬ p is always false and the definition of implies says that a false premise always guarantees a true conclusion (for any conclusion). So we have that, in the face of a contradiction p ∧ ¬ p , anything may be concluded.

Recall that we’ve already proven this. We saw that if we assert:

• The moon is made of green cheese.

• The moon is not made of green cheese.

then we can prove any of the following:

• Elephants can fly.

• Elephants cannot fly.

• The king of France is a unicorn.

Resolution : p ∨ q p ∨ q p ∨ q p ∨ q

¬ p ∨ r r ∨ ¬ p ¬ q ∨ r r ∨ ¬ q

∴ q ∨ r ∴ q ∨ r ∴ p ∨ r ∴ p ∨ r

The first version says that, from premises p ∨ q and ¬ p ∨ r , conclude q ∨ r . (The other three are equivalent since or is commutative.) This is interesting since we never assert any of p, q , or r to be true. But we do know that p must either be true or false. If p is true (and thus ¬ p is false) then, to make ¬ p ∨ r true, r must be true. Alternatively, if p is false (and thus ¬ p is true) then, to make p ∨ q true, q must be true. Hence either q or r (or both) must be true.

Nifty Aside

Besides being useful in the sorts of proofs that we’re going to do, this rule forms the basis for another proof technique called resolution.

Conditionalization : A, a set of premises

( A ∧ p ) entails q

∴ p → q

Suppose that some set A of premises, taken together with one additional premise p , entails q . In other words, q must be true whenever the premises, plus p , are all true. Then, continuing to assume A as our premises, we have that p implies q .

This rule works differently from the others that we have presented. In particular, it describes a derivation process that may require many steps and that may require appeal to any number of other premises.

Note that what we derive here is an implication. We show that, if p is true, then q must also be. We do that in the following steps:

1. Assume that p is true (i.e., add it as a new premise).

2. Reason with it (and with any other required premises or derived statements).

3. Derive q . Note that, at this point, we haven’t actually proven q . We’ve just shown that it must be true if p is.

4. Conclude that (in the context of the rest of our premises) p → q . When we make explicit the fact that our conclusion rests on the assumption of the extra premise p , we’ll say that we’ve discharged the premise p .

While Conditionalization doesn’t allow us to conclude q , it can be very useful. Once we’ve got p → q , there are two things we can do:

• Wait and, if we ever do find out that p is true, we can immediately conclude q .

• Use our new fact as a hint if we’re trying to figure out a way to prove q : What we know now is that we should try to prove p .

Slippery

Give names to the following statements:

P: There’s precipitation.

Z: It’s freezing.

S: It’s slippery.

Assume the following premises:

\((P \wedge Z) \rightarrow S\) If there’s precipitation and it’s freezing, it is slippery.

Z It’s freezing.

Given these two premises, we should be able to prove that, if there’s precipitation, it will be slippery. (Pretty reasonable in the winter in many places.) To do this, we introduce the conditional premise:

P There’s precipitation.

Now we can assert:

\((P \wedge Z) \)

(To get this formally, we use our second premise plus the Conjunction rule.) Using Modus Ponens, along with our first premise, we then have:

\(S\)

But we haven’t actually proved S. We must discharge the conditional premise P. When we do this, we get:

\(P \rightarrow S \) If there’s precipitation, it is slippery.

Note that, whenever we use the Conditionalization rule, we must do careful bookkeeping so that we guarantee that all conditional premises have been discharged before we assert a conclusion.

In the appendix, you’ll find a Boolean logic “cheat sheet”. You may want to keep it handy while working proofs.