Back to the on-screen lesson ·
Deciding the last line from the shape of the conclusion, turning what that rule demands into new goals, and recognising a legitimate step that leads nowhere.
Paper packet. Every task here also exists on screen, where it is checked automatically; answers written on paper are not assessed by Nydus. When you are back at a device, enter your answers there.
By the end of this lesson you will be able to choose the last rule of a proof from the shape of its conclusion, turn that rule's demands into goals and work backwards to the premises, write the finished proof forwards in the right order, count the lines a derivation needs, recognise a legitimate step that no later line can use, and read the conclusion's vocabulary as a planning clue.
You know the rules and can check a proof line by line. What is left is finding one: deciding which rule the last line will use before writing the first.
Working forwards is applying rules to the premises to see what comes out. Working backwards is asking what rule could produce the goal, and making what that rule demands into a new goal. A dead end is a legitimate line that no later line can use.
Proofs are written forwards and found backwards. Start from the conclusion and ask which rule could produce a line of that shape: a conjunction comes from conjunction introduction, a disjunction from disjunction introduction, a conditional from the chain rule, a bare letter from detaching a conditional or opening a disjunction. That rule's demands become the new goals, and the process repeats until every remaining goal is a premise or something obviously reachable from one. Then work forwards and write the proof down in the opposite order. Two shortcuts save most of the effort. Look at where the conclusion occurs among the premises: if it is a disjunct, the last step is probably disjunctive syllogism, and the real goal is the denial of the other disjunct. And look at the vocabulary: a letter in the conclusion that no premise mentions can only have got there by disjunction introduction.
Another way: steps
Another way: example
Goal $S$, premises including $P \vee S$. $S$ is a disjunct, so plan disjunctive syllogism as the last line; the goal becomes $\neg P$, and the other premises exist to supply it.
The commonest failure is working forwards only: applying every rule that fits and hoping the conclusion appears. It sometimes does, and on a longer problem it produces pages of legitimate, useless lines. The second is treating a legitimate step as progress; the test is whether a later line can cite it. The third is stopping when the conclusion becomes available rather than written — a proof ends on its conclusion, as a line.
Goal $P \to R$, premises $P \to Q$ and $Q \to R$. The goal is a conditional.
Main connective first.
Nothing can be detached — no premise is an atom — so modus ponens is out, and the chain rule is the only rule producing conditionals.
Which rule has this output?
It demands two conditionals sharing a letter, and those are the premises. One line finishes the proof.
The demands are already met.
Goal $S$; premises $P \to Q$, $Q \to R$, $\neg R$ and $P \vee S$.
Find the conclusion among the premises.
$S$ is a disjunct of the last premise, so plan disjunctive syllogism; the goal becomes $\neg P$.
The last step fixes the next goal.
Two applications of modus tollens along the chain give $\neg P$, and the plan closes.
Now write it forwards.
The goal is a conjunction, so plan conjunction introduction last; the goals become $Q$ and $R$.
$R$ is a premise and $Q$ comes by modus ponens, so the proof is four lines of premises and two steps.
These are the six lines of a proof, shuffled. Put them in order.
Number the steps in order (write the number in the box):
Your premises are $P \to Q$ and $Q \to R$, and the conclusion you have been asked for is $P \to R$. Which rule should the last line of your proof use?
From the premises P -> R, R -> Q, ~Q and P | T, derive T. Give one line at a time, with the rule and the lines it uses.
P -> R
R -> Q
~Q
P | T
∴ T
| # | Formula | Rule | Lines |
|---|---|---|---|
| 1 | |||
| 2 | |||
| 3 | |||
| 4 | |||
| 5 | |||
| 6 |
For each shape of conclusion, match the rule that would naturally produce it as the last line.
| Conjunction introduction, from both halves | Disjunction introduction, from either half alone | The chain rule, from two conditionals that share a letter | Biconditional introduction, from the two conditionals | |
|---|---|---|---|---|
| The conclusion is $\phi \wedge \psi$ | ||||
| The conclusion is $\phi \vee \psi$ | ||||
| The conclusion is $\phi \to \chi$ | ||||
| The conclusion is $\phi \leftrightarrow \psi$ |
The goal is $R$. Every line below follows the rule it names. Mark the line that is nevertheless of no use in reaching the goal.
This task has no paper form; do it on a device.
From the premises P -> Q and P, derive Q | R. Give one line at a time, with the rule and the lines it uses.
P -> Q
P
∴ Q | R
| # | Formula | Rule | Lines |
|---|---|---|---|
| 1 | |||
| 2 | |||
| 3 | |||
| 4 | |||
| 5 | |||
| 6 |
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
From $P \to Q$ and $P$, derive $Q$. Using the rules of this course, how many lines does the shortest derivation have, counting the premises as lines?
Answer:
You can plan a derivation backwards from its conclusion and then write it forwards. Say in your own words why a letter occurring only in the conclusion tells you which rule the last line must use.
8. Your turn: goal $Q \wedge R$, premises $P$, $P \to Q$ and $R$, step 2