The basic rules

A derivation is a numbered list of lines, each with a rule and the lines it cites; modus ponens, modus tollens and the two conjunction rules are enough to start.

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.

1. What you will learn

By the end of this lesson you will be able to write a derivation as numbered lines with rules and citations, apply modus ponens, modus tollens and the conjunction rules, say what each rule demands of the lines it cites, find the line of an attempted proof that its rule does not produce, and build a compound line that is not a premise.

2. What you already have

You can decide validity with a table and you know the named forms. A derivation is those forms used one at a time, written down in a way that can be checked line by line without any table at all.

3. The words this lesson uses

A derivation is a numbered list of lines. Each line carries a formula, a rule, and the citations — the numbers of the lines the rule is applied to. A line whose rule is premise must be one of the premises, written exactly. $\Gamma \vdash \phi$ says a derivation of $\phi$ from $\Gamma$ exists.

4. Deriving line by line

A derivation replaces the table with a list. Every line is a formula together with the rule that produced it and the numbers of the lines that rule was applied to; a line may cite only lines above it, and the last line is the conclusion. The basic rules are these. MP: from $\phi \to \psi$ and $\phi$, write $\psi$. MT: from $\phi \to \psi$ and $\neg \psi$, write $\neg \phi$. andI: from any two lines, write their conjunction. andE: from $\phi \wedge \psi$, write either half. Nothing is assumed about which lines are premises: a line built by a rule is a line like any other and may be cited afterwards. The gain over a table is not certainty — the table was already certain — but size: a derivation grows with the length of the argument, while a table doubles with every atom.

Another way: steps

Write every premise as its own line, copied exactly.
Look at the conclusion and ask which rule could produce it.
Ask what that rule would need, and whether those formulas are lines yet.
Work forwards from the premises until they are, then take the last step.

Another way: example

From $P \wedge Q$ and $Q \to R$, derive $R$. Line 3 is $Q$ by andE from 1; line 4 is $R$ by MP from 2 and 3. Two lines of work, and no table.

5. Where this goes wrong

The first error is citing a formula that is inside a line rather than a line: $P$ occurring as half of $P \wedge Q$ is not the line $P$ until andE has written it down. The second is naming a rule that the citations do not fit, usually because the new line is obviously true; being true is not a rule. The third is stopping one line early, when the conclusion has been made available but not written.

6. Reading a rule as a demand

Line 1: $P \to Q$. Line 2: $P \vee R$. Can modus ponens give $Q$?
State what the rule demands.
It demands the antecedent $P$ as a line. Line 2 is a disjunction, not $P$.
Compare demand with citation.
So no. The step would be illegitimate even if $P$ happened to be true.
Truth is not a rule.

7. Two steps backwards

From $P \to Q$, $Q \to R$ and $\neg R$, derive $\neg P$. Line 3 denies the consequent of line 2.
Find what the denial attacks.
Line 4: $\neg Q$ by MT from 2 and 3. That is itself a denial.
The output can be reused.
Line 5: $\neg P$ by MT from 1 and 4.
Same rule, one line later.

8. Your turn: from $P$ and $P \to (Q \wedge R)$, derive $R$

Line 3 is $Q \wedge R$, by modus ponens from lines 2 and 1.
Your turn: work this step out. Its working is at the end of the packet.
Line 4 is $R$, by conjunction elimination from line 3.

9. Guided practice

Match each rule to what it demands of the lines it cites and what it lets you write.

	Cite a conditional and its antecedent; write the consequent	Cite a conditional and the denial of its consequent; write the denial of its antecedent	Cite any two lines; write their conjunction	Cite a conjunction; write either half of it
Modus ponens
Modus tollens
Conjunction introduction
Conjunction elimination

10. Guided practice

From the premises R & Q and R -> P, derive P. Give one line at a time, with the rule and the lines it uses.

R & Q
R -> P
∴ P

#	Formula	Rule	Lines
1
2
3
4
5
6

11. Guided practice

Here is an attempted proof. Mark the line that the rule it names does not produce.

This task has no paper form; do it on a device.

12. Practice

These are the four lines of a proof, shuffled. Put them in order.

Number the steps in order (write the number in the box):

1. $P \to Q$, premise
2. $P$, premise
3. $Q$, from 1 and 2 by modus ponens
4. $P \wedge Q$, from 2 and 3 by conjunction introduction

13. Practice

A line reads $Q$, citing $P \vee Q$ and $\neg P$. Which rule is that?

Modus ponens
Modus tollens
Conjunction elimination
Disjunctive syllogism
Hypothetical syllogism

14. Somewhere new

From the premises P, Q and (P & Q) -> R, derive R. Give one line at a time, with the rule and the lines it uses.

P
Q
(P & Q) -> R
∴ R

#	Formula	Rule	Lines
1
2
3
4
5
6

15. Lesson test

Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.

16. Test question

From the premises Q -> R, R -> P and ~P, derive ~Q. Give one line at a time, with the rule and the lines it uses.

Q -> R
R -> P
~P
∴ ~Q

#	Formula	Rule	Lines
1
2
3
4
5
6

17. What you can do now

You can produce a short derivation and check somebody else's line by line. Say in your own words why a formula occurring inside a line is not yet available as a line.

Working for the steps left to you

8. Your turn: from $P$ and $P \to (Q \wedge R)$, derive $R$, step 2