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)