Lecture Notes 7: Strategies for Derivations

Negation Rules

Just using the rules we have already learned, we can demonstrate the validity of any valid argument in sentential logic.

However, if we stick only to what we have so far, some problems require making moves that are rather strange and awkward.

Consider the following problem:

There is no obvious way to do this problem.

The conclusion is not a conditional statement, so it seems to make little sense to do CD.

We could try an ID.

If we assume ~(P ∨ R) and try to get a contradiction, however, we get stuck immediately.

It is possible to do this problem with our rules so far, but it requires some very unusual and creative moves:

To make our lives easier, we introduce some special rules dealing with negations of complex statements.

With these rules, the above proof simplifies to:

Some other derivations that use these rules.

Strategies and Rules of Thumb

When you begin a derivation, you might be unsure of the best way to go about it. Should you do a CD, ID or just try it by DD? Would you need to do some combination of these? When should you do one technique within another?

The simplest rule is: when in doubt, try an indirect derivation.

This is because all problems can be done with ID. Some problems are shorter if you don’t use ID, but if you can’t see that far ahead, it almost never hurts to try one.

To make things more specific, when in doubt, I recommend constructing a derivation using the following strategies, depending on what kind of statement in your SHOW line:

SHOW line	Form	Try	Assume	New SHOW
Atomic	P	ID	~P	✖
Negation	~𝒜	ID	𝒜	✖
Disjunction	𝒜 ∨ ℬ	ID	~(𝒜 ∨ ℬ)	✖
Conditional	𝒜 → ℬ	CD	𝒜	ℬ
Splat	✖	DD	(none)	(none)

For “and” and “iff” statements, use &D or ↔D, which involve breaking the problem into two parts.

SHOW line	Form	Try	Assume	New SHOW
Biconditional	SHOW: 𝒜 ↔ ℬ	↔D
first:	SHOW: 𝒜 → ℬ	CD	𝒜	ℬ
then:	SHOW: ℬ → 𝒜	CD	ℬ	𝒜
Conjunction	SHOW: 𝒜 & ℬ	&D
first:	SHOW: 𝒜	ID?	~𝒜	✖
then:	SHOW: ℬ	ID?	~ℬ	✖

Strictly speaking, the inner SHOW lines for ↔D don’t have to be done by CD, but this is usually the best way. Similarly, the inner SHOW lines for &D don’t have to be done by ID, but this is often a good way.

This chart should tell you how to set up any problem:

• Look at your SHOW line, figure out which kind of derivation works best and then make your assumption and write your new SHOW line.
• Look at your new SHOW line and repeat the procedure until you get SHOW ✖.
• Now, use the DD rules to get a contradiction.

This will work for almost all problems. Examples:

Remember you can use a SHOW line after SHOW has been crossed out.

---

What to Do when Stuck: “Desperate Measures”

Following the guidelines suggested above will get you through just about any problem. But there is a certain kind of problem where you still might get stuck in the middle, and you’ll have to try something desperate to get out of being stuck.

Here is an example of that kind of problem.

If you follow the guidelines, you’ll begin by starting an ID. A few steps can be done after that.

But, uh oh, now what? There doesn’t seem to be anywhere to go from here.

When you get stuck like this, you need to ask yourself: What would be helpful? What resources do you have that you would like to make use of, but can’t?

Usually this will lead you to one or more lines that are just begging to be used. In this case, it’s line 1, which hasn’t been used so far.

Line 1 is an ∨-statement, which means, if we were going to make use of it, we’d have to make use of the ∨O rule.

To make use of the ∨O rule, we’d have to have that one of the two sides of the or-statement is false. Let’s try to prove just that!

That is, let’s try to prove ~(P → R).

Let’s go ahead and write that in as a new SHOW line. Then we can do it by ID.

Lo and behold, it works! Once we have it, we can finish the rest of the derivation.

Basically, when you get stuck, look for a way you can set up either doing a ∨O step (like we did here at line 15), or a →O, by proving either the negation of half of an ∨-statement, or by proving the if-part of a →-statement, or the negation of a then-part of a →-statement.

Introduce a new SHOW line if necessary, so you can do an ID or CD for the thing that you need to set up the desired move.

Here are some more examples of such “desperate measures” strategies.

By using these strategies together with the strategy advice given earlier, you can finish any problem you come across!

Review Problems

Here’s a short, interesting problem that involves proving a conclusion without using any premises!

We’ll do some more derivations later in the semester, but for now, time to dance!