Topic DS: How to prove things with Sentential logic

4 Strategies for making derivations

The
list of rules of our natural deduction system fits

on one page. The rules are not very complicated, and

there are not many rules.

Still, sometimes, it is not
obvious how to make

a certain derivation. And it is sometimes not

obvious whether it is even possible to make

a certain derivation.

How, for example, to show this?

~(P ∨
Q)
(~P & ~Q)

As a start, we might
write:

But now we are stuck. No obvious rule, like

&E or
→E, applies to line 1.
Line 1 is not a conjunction,

nor is line 1 a conditional. Line 1 is a negation.

What can we do?

In this section we will examine some strategies

for making derivations.

4.1 Don't make random assumptions

One rule that might apply to line 1 is ~E.

If we can derive an explicit contradiction,

then we can apply ~E to write down "(P ∨
Q)".

To use ~E we need to find an explicit contradiction,

but we only have line 1 so far. Now the Rule of

Assumption lets us write down any formula we like.

So you might try this:

Now we have an explicit contradiction,

and can apply Rule ~E:

We have now shown (P ∨
Q) (P
∨
Q).

That is no
progress.

A mistake we just made was to think that if

we need some formula, we should simply

use the Rule of Assumption to assume it.

This is a common beginner's mistake.

Assumptions can be useful in making a derivation.

But assuming things haphazardly is rarely an

effective strategy in making a derivation.

We need a new approach.

4.2 Think backwards

One approach is
to try to see what rule

to apply to line 1 in order to move a step

closer to the conclusion. We just tried that.

It didn't work.

Another approach is to think about things in

the opposite direction: start with the last line

and work backwards to the assumptions.

Let's try that.

We know that the last line of the derivation

should be "(~P
& ~Q)" depending only

on "~(P ∨
Q)":

What rule could have been used on that last step?

(Not knowing how many lines there will be when the

derivation is finished, I just wrote "20" for the last

line. I'll fix that later.)

Two possibilities are &I and ~E.

Exercise 4.2

Are there any other rules that could have

been used on the last line of that
derivation?

Let's try &I.

But now we seem to be stuck again. We need

to show "~P" and "~Q". It is not obvious how to

proceed.

4.3 If you don't know what to do, try ~E or ~I

When you do not
know what to do next, one of

the negation rules is worth trying. In this case,

since you want to show "~P", you can assume "P"

and try to show an explicit contradiction.

If you succeed, you can write down "~P".

(I just guessed that the assumption will be on line 10.

We can fix that later.) Now we are almost there.

We just need to see how, somehow, to put

"P" (on line 10) together with "~(P ∨
Q)" (on line 1)

to get an explicit contradiction. One explicit

contradiction is "(P & ~P)". However to get that we

would need "~P", and "~P" is what we are using ~I

to show. So that won't work. Another possibility is

to get something which explicitly contradicts

"~(P ∨
Q)" on line 1--- that is, to
reach "(P ∨
Q)".

And then we have the solution, once we realize

that "(P ∨
Q)" follows from "P" in one
step by rule ∨I:

We have now succeeded in deriving "~P"

from "~(P ∨
Q)".

That is, we
have shown ~(P ∨
Q) ~P.

This is what
line 18 says.

However, we are not finished yet.

4.4
Think about what you have proved before

We need to figure out
how to reach "~Q" on line 19.

We need to show ~(P ∨
Q) ~Q.

Sometimes in
making a derivation, what you are

trying to show is similar to something you have

derived before. What we need to show now,

~(P
∨
Q) ~Q,

is rather like
what we have just shown,

~(P
∨
Q) ~P.

Another useful
strategy is to adapt a previous

derivation to a new situation. In the previous

derivation we used ~I, after assuming P.

In this case, we can use ~I, after assuming Q:

Now let's put the whole proof together,

renumbering the lines appropriately.

Exercise 4.4

How can you show this?

~((A & B)
∨ C)
(~(A
& B) & ~C)

4.5 Problem solving

Here in Topic
DS04 you have seen several

strategies for making derivations. Given the

first few lines of the derivation, you can

search for a rule which directly applies.

It is also very
useful to think backwards, looking for a

rule which
could have been used to get the last line.

You can try to apply ~I or ~E. You can think about

whether the derivation you are working on is like a

derivation you have made already. And, as you have

seen, in working out a derivation you can try all of

these strategies.

But what you have not seen is a method that will

work in every situation. There is no "model answer"

to be memorized. Cases which appear similar may

require very different methods. To improve your

skills in solving problems, try the following

further examples.

Exercise
4.5a

Show the following:

(P → Q), (R → Q)
((P
∨
R) →
Q)

(A & B), (C & D)
(A & D)

(P & (Q & R)), S
(R & S)

(P → Q), (Q → R), P
R

(P → (Q → R)), (P & Q)
R

(P → (Q → R)), Q
(P → R)

((P & Q) → R)
(P → (Q → R))

(P → (Q → R))
((P → Q) → (P → R))

P
(Q → P)

(P → Q), (Q → R)
(P → R)

~(P
& ~Q)
(P → Q)

P, ~P
~Q

(~P
→ ~Q)
(Q → P)

((P
∨
Q)→ R)
(P → R)

~(P
→ Q)
~(~P
∨
Q)

(P
& (Q
∨
R))
((P & Q)
∨
(P & R))

(P
↔
~Q)
~(P
↔
Q)