Rules of inference

A truth table certifies that no counterexample exists and gives no account of why the conclusion follows, which is the difference between a verdict and a proof.

There is a second reason to want something better, and it is arithmetic: the previous lessons' method doubles in size with every atom, so an argument with thirty atoms is a billion rows. This lesson replaces enumeration with derivation. A derivation is a numbered list of formulas, each one either a premise or the result of applying a stated rule to earlier lines, ending at the conclusion. Nobody has to trust the writer, because every line names what it came from, and checking a derivation is mechanical even when finding it was not.

The system built here is natural deduction, designed by Gerhard Gentzen in 1934 with the explicit aim of matching how mathematicians actually argue. Its organising idea is that each connective gets exactly two rules: one to introduce it and one to eliminate it.

The shape of a derivation

A derivation is written in three columns: the line number, the formula, and the justification, which names the earlier lines used and the rule applied. Premises are justified by the word "premise" and by nothing else.

Here is the smallest interesting one, the chain from the first lesson. From $P \to Q$ , $Q \to R$ and $P$ , derive $R$ .

#	Formula	Justification
1	$P \to Q$	premise
2	$Q \to R$	premise
3	$P$	premise
4	$Q$	1, 3, $\to$ E
5	$R$	2, 4, $\to$ E

Two things are worth noticing before any rule is stated. Each new line is a formula that must be true whenever the lines it cites are true, which is the only property a rule needs. And the derivation is checkable line by line without ever considering the argument as a whole, which is exactly what a table cannot offer.

When the premises $Γ$ yield $φ$ by such a derivation, write $Γ ⊢ φ$ , read " $Γ$ proves $φ$ ". Keep it firmly apart from $Γ ⊨ φ$ from the third lesson, which was about rows of a table. One is a claim about what can be written down with these rules, the other about what is true in every valuation, and the relation between them is the subject of the end of the next lesson.

Rules for conjunction

Conjunction is the easiest connective and shows the pattern.

Conjunction introduction ( $\land$ I): from $φ$ and $ψ$ on any two earlier lines, write $φ \land ψ$ . Conjunction elimination ( $\land$ E): from $φ \land ψ$ , write either $φ$ or $ψ$ .

Both are justified by the table. The introduction rule is sound because the only row where a conjunction is false is one where a conjunct is false, so if both conjuncts are true on their lines, the conjunction cannot be false. The elimination rule is sound because a true conjunction has both parts true.

That justification is the pattern for every rule below, and it is why the system is not a set of conventions. A rule is admitted only if it can never take you from true lines to a false one, and the truth tables are the court of appeal.

Rules for the conditional

Conditional elimination ( $\to$ E) is modus ponens: from $φ \to ψ$ and $φ$ , write $ψ$ . It is sound because the only row where a conditional is true with its antecedent true has the consequent true as well, which is a restatement of the single false row of the conditional table.

There is no introduction rule here yet. To write a conditional you must be able to suppose its antecedent, and supposing needs machinery that the next lesson supplies. Until then the system can take conditionals apart and cannot build them, which is a real gap and worth feeling rather than patching.

Three further rules about conditionals are derived: each can be reconstructed from the basic ones, and each is used often enough to be worth naming. Modus tollens (MT): from $φ \to ψ$ and $\neg ψ$ , write $\neg φ$ . Hypothetical syllogism (HS): from $φ \to ψ$ and $ψ \to χ$ , write $φ \to χ$ . Disjunctive syllogism (DS): from $φ \lor ψ$ and $\neg φ$ , write $ψ$ .

Calling them derived matters for a reason that will return in the next lesson. A small set of basic rules is easier to prove things about, and a large set is easier to work with, so systems keep the basic set minimal and then license the convenient ones once. Nothing is lost either way.

Example. Derive $R$ from the premises $(P \land Q) \to R$ , $P$ , $S \to Q$ and $S$ .

The conclusion is the consequent of the first premise, so the target is its antecedent, $P \land Q$ . $P$ is already given, and $Q$ is one step from the last two premises.

#	Formula	Justification
1	$(P \land Q) \to R$	premise
2	$P$	premise
3	$S \to Q$	premise
4	$S$	premise
5	$Q$	3, 4, $\to$ E
6	$P \land Q$	2, 5, $\land$ I
7	$R$	1, 6, $\to$ E

The strategy generalises: look at what the conclusion is a part of, and work backwards to what would deliver it. Derivations are found from both ends and written forwards.

Now you. Derive $D$ from $A \to B$ , $B \to C$ , $\neg C$ and $A \lor D$ .

Answer

#	Formula	Justification
1	$A \to B$	premise
2	$B \to C$	premise
3	$\neg C$	premise
4	$A \lor D$	premise
5	$A \to C$	1, 2, HS
6	$\neg A$	5, 3, MT
7	$D$	4, 6, DS

Rules for disjunction

Disjunction introduction ( $\lor$ I): from $φ$ , write $φ \lor ψ$ for any $ψ$ at all. This looks like cheating. From "the sample is copper" it licenses "the sample is copper or the moon is hollow", which no sensible person would say.

It is nevertheless sound, and the table shows why immediately: a disjunction is true whenever either side is true, so a true line cannot yield a false disjunction. What offends is not the truth of the conclusion but its uselessness, and logic guarantees only truth preservation. The rule earns its place because a disjunction is the input to disjunctive syllogism and to argument by cases, so manufacturing one deliberately is often the step that makes a proof go through.

Elimination for disjunction is the hard one, because knowing $φ \lor ψ$ tells you almost nothing on its own. The honest rule is argument by cases: show that the conclusion follows from $φ$ and also from $ψ$ . That needs suppositions again, so like conditional introduction it waits for the next lesson. Disjunctive syllogism is the poor relation available in the meantime, and it works only when one disjunct can be ruled out.

Rules for negation and the biconditional

Double negation elimination ( $\neg \neg$ E): from $\neg \neg φ$ , write $φ$ . Its converse, introducing a double negation, is equally sound, and both follow from the one-line table for $\neg \neg P$ .

Introducing a negation properly means proving that an assumption leads to disaster, which again waits for the next lesson. So negation, like the conditional and the disjunction, currently has an elimination rule and no introduction rule, and the pattern of what is missing is now unmistakable.

The biconditional is handled by trading it for two conditionals. Biconditional elimination ( $\leftrightarrow$ E): from $φ \leftrightarrow ψ$ , write $φ \to ψ$ , or write $ψ \to φ$ . Biconditional introduction ( $\leftrightarrow$ I): from $φ \to ψ$ and $ψ \to φ$ , write $φ \leftrightarrow ψ$ . This one is available now because it does not need a supposition, only two conditionals already in hand, though in practice those conditionals will have come from the next lesson's machinery.

Example. Derive $\neg B$ from $(A \land B) \to C$ , $A$ and $\neg C$ .

Modus tollens on the first and third premises gives the negation of the antecedent, and the rest is reading what that negation says.

#	Formula	Justification
1	$(A \land B) \to C$	premise
2	$A$	premise
3	$\neg C$	premise
4	$\neg (A \land B)$	1, 3, MT
5	$\neg A \lor \neg B$	4, De Morgan
6	$\neg \neg A$	2, double negation
7	$\neg B$	5, 6, DS

Lines 5 and 6 use equivalences from the previous lesson as rewriting steps, which is legitimate because equivalent formulas are interchangeable everywhere. Many textbooks list those equivalences among the rules for exactly this reason, and the derivation is shorter for it.

Now you. Derive $Q \land S$ from $P \to Q$ , $R \to S$ and $P \land R$ .

Answer

#	Formula	Justification
1	$P \to Q$	premise
2	$R \to S$	premise
3	$P \land R$	premise
4	$P$	3, $\land$ E
5	$R$	3, $\land$ E
6	$Q$	1, 4, $\to$ E
7	$S$	2, 5, $\to$ E
8	$Q \land S$	6, 7, $\land$ I

Finding a derivation

The rules say what may be written; they do not say what to write, and that is a genuine difficulty rather than a lack of practice. Three habits cover most cases.

Work backwards from the conclusion. If it is a conjunction, plan to get both halves and use $\land$ I. If it is an atom sitting as the consequent of a premise, plan to get that premise's antecedent. If it appears as a disjunct, plan to eliminate the other disjunct.

Take every premise apart as far as it goes. Conjunctions should be split immediately, biconditionals turned into their two conditionals, and double negations removed, because a formula buried inside a compound cannot be used.

Watch for a negation among the premises. It is almost always there to fire modus tollens or disjunctive syllogism, and spotting which premise it is aimed at usually unlocks the problem.

Example. Derive $S$ from $P \leftrightarrow Q$ , $P \lor R$ , $\neg R$ and $Q \to S$ .

$S$ is the consequent of the fourth premise, so the target is $Q$ . $Q$ is the right-hand side of the biconditional, so it will come from $P$ , and $P$ comes from the second and third premises.

#	Formula	Justification
1	$P \leftrightarrow Q$	premise
2	$P \lor R$	premise
3	$\neg R$	premise
4	$Q \to S$	premise
5	$P$	2, 3, DS
6	$P \to Q$	1, $\leftrightarrow$ E
7	$Q$	6, 5, $\to$ E
8	$S$	4, 7, $\to$ E

Disjunctive syllogism at line 5 works with the negated disjunct on the right, which is fine: the rule cares that one disjunct is denied, not which.

Now you. Derive $C$ from $A \lor B$ , $\neg A$ , $B \leftrightarrow D$ and $D \to C$ .

Answer

#	Formula	Justification
1	$A \lor B$	premise
2	$\neg A$	premise
3	$B \leftrightarrow D$	premise
4	$D \to C$	premise
5	$B$	1, 2, DS
6	$B \to D$	3, $\leftrightarrow$ E
7	$D$	6, 5, $\to$ E
8	$C$	4, 7, $\to$ E

What the system cannot yet do

Count the gaps. Conjunction has both rules. The biconditional has both. The conditional, the disjunction and the negation each have an elimination rule and no way to be introduced, apart from the disjunction's near-useless one.

The consequence is severe. This system cannot derive $P \to P$ , the most obvious tautology there is, because with no premises there is nothing to eliminate and no way to build an arrow. It cannot prove any tautology at all from no premises. It cannot use a disjunction except by killing one side. Whatever else it is, it is not complete.

Every one of those gaps has the same cause. Building a conditional requires reasoning under a supposition you do not believe; building a negation requires assuming something in order to wreck it; using a disjunction requires taking each case in turn as a temporary assumption. Suppositions are the missing machinery, and they need a bookkeeping discipline, since a formula proved under an assumption must not escape and be used as though it had been proved outright. That discipline, and the two most important proof techniques in mathematics that come out of it, are the next lesson.