Lecture Notes 12: Derivations Strategies and Review

Strategies and Steps

This chart suggests a kind of derivation to do depending on your SHOW line.

SHOW line	Form	Try	Assume	New SHOW
Atomic	Fa	ID	~Fa	✖
Negation	~𝒜	ID*	𝒜	✖
Disjunction	𝒜 ∨ ℬ	ID	~(𝒜 ∨ ℬ)	✖
Existential	∃x …x…	ID**	~∃x …x…	✖
Conditional	𝒜 → ℬ	CD	𝒜	ℬ
Universal	∀x …x…	UD	(none)	…n… (new)
Splat	✖	DD	(none)	(none)

* = This is my advice regardless of what is being negated: ~Fa, ~(𝒜 → ℬ), ~(𝒜 ∨ ℬ), ~(𝒜 & ℬ), ~(𝒜 ↔ ℬ), and even ~∃x …x… and ~∀x …x… should all be done by ID.

** = Most existentials can be done by DD, but IDs are often easier.

Prof. Hardegree even allows the abbreviations ~D, ∨D, and ∃D as “aliases” for ID when applied specifically to statements with these main operators. I usually don’t bother.

For “and” and “iff” statements, break 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 is the same as a chart I gave you for Sentential Logic, adding that universals should be proven by UD, and existentials by ID.

There is also a step-by-step procedure I recommend for completing the problems after they’ve been set up.

1. Look at SHOW line; consult the table above and set-up the derivation.
2. Look at the new SHOW line; if it is SHOW ✖, proceed to step 3. If it is anything else, repeat step 1 for the new SHOW line.
3. Do any ~∃O and ~∀O steps you can. (I.e., push any negations through the quantifiers.)
4. Do all the ∃O steps you can. Use a new letter every time.
5. For every universal statement, do a ∀O step to every name you already have in the derivation, however many there are.
6. Apply the DD rules. (∃I, DN, ∨O, →O, &O, ↔O, etc.)
7. Look at results from step 6. If you got a contradiction, you can finish the derivation with ✖I. If you don’t have one, you may need to repeat steps 3–6 until you get one. If you still can’t get one, you may need to try a “desperate measures” strategy. (Remember those?)

If you’re not having trouble with derivations, you needn’t make use of these instructions, but for many students they may provide valuable help.

(This is basically the procedure used to determine what to do next when you click the “Give hint” button.)

Here are some problems that make use of these strategies and directions.

Lines 1–5 are STEPS 1–2.
Line 6 is STEP 3.
Line 7 is STEP 4.
Lines 8–9 are STEP 5.
Lines 10–13 are STEP 6.
Line 14 is STEP 7.

Lines 1–4 are STEPS 1–2.
STEP 3 is skipped, since there are no negations before quantifiers.
Line 5 is STEP 4.
STEP 5 is skipped.
Lines 6–7 are STEP 6.
STEP 7 tells us to repeat steps 3–6.
Lines 8–9 are STEP 3 repeated.
Lines 10–12 are STEP 5 repeated.
Line 13 is a new STEP 6.
Line 14 is STEP 7.

We did an unnecessary step at line 10, but that’s OK.

Biconditionals can make problems quite long, but easily do-able.

Notice that for a biconditional, we have to cycle through the steps independently for the two halves of the problem.

“Desperate Measures” Revisited

This is review from something we learned when discussing Sentential Logic.

If you get stuck in a proof, look at your “if-then” and “or”-statements. What you need is a way to use →O or ∨O. To do this, you may need to introduce a new SHOW line to try to prove either that one half of an “or”-statement is false, or that the if-part of an if-then is true, or the then-part is false.

The problem is set up normally. We get stuck at line 7, so we introduce a SHOW line to give us what we would need to do ∨O on line 1.

Once SHOW is crossed off at line 8, we can use it.

Derivations Review

To review, we just do some practice problems.

And that’s all for the semester!

Time to dance!