Matching a Rule to Whole Lines

Each rule of inference is a pattern written with $p$, $q$, $r$ and $s$. In a real proof, those letters stand for whatever formulas fill their places. This lesson makes the matching exact, using the rules from Constructive Dilemma (CD).

Key idea

A rule of inference applies to whole lines whose main connectives fit the rule's pattern, with any formulas in place of $p$, $q$, $r$ and $s$ (the same formula wherever the same letter appears). It never applies to a part of a line.

Why it works

Validity depends only on form, so if MP is valid for letters, it is valid for any formulas put in place of those letters: the truth table for the bigger argument has the same pattern of T and F in the columns that matter. But a part of a line is not asserted on its own. In $(p \to q) \lor r$, the conditional $p \to q$ might be false (when $r$ is true), so using it as if it were a premise could take you from truths to a falsehood.

Modus tollens with compound formulas in place of the letters.

Worked examples

Worked example: Match the main connectives

Which rule takes $(p \land q) \to \neg r$ and $p \land q$ to $\neg r$?

Line 1's main connective is $\to$; line 2 is exactly its antecedent.
MP's $p$ is $p \land q$ and its $q$ is $\neg r$.

Answer: MP

Worked example: A part of a line

Can MP take $(p \to q) \lor r$ and $p$ to $q$?

Line 1's main connective is $\lor$, not $\to$.
The conditional is only a part.

Answer: No. No rule of inference applies to line 1 as it stands.

Worked example: Same letter, same formula

Does HS take $p \to q$ and $r \to s$ to $p \to s$?

HS needs the consequent of the first to be the antecedent of the second.
Here $q$ and $r$ differ.

Answer: No.

Common mistake

Applying MP inside a line: from $(p \to q) \lor r$ and $p$, inferring $q$. Check the main connective of each cited line before you name a rule. If the line is a disjunction, MP, MT and HS cannot use it; if it is a conditional, Simp cannot.

A useful habit is to draw an imaginary box around each big part. In $(p \lor q) \to (r \land \neg s)$ the antecedent $p \lor q$ is one box and the consequent $r \land \neg s$ another; the line is then just box $\to$ box, and MP or MT can see it plainly. The rules never look inside a box; they only check how the boxes are joined.

A quick guide.
Rule	Main connective of the cited lines
MP, MT	one conditional (and its antecedent, or the negation of its consequent)
HS	two conditionals
DS	one disjunction and one negation
CD	one conjunction of conditionals and one disjunction
Simp	one conjunction
Conj, Add	any lines

Matching a Rule to Whole Lines

Worked examples

Practice

Builds on

Leads to

Sources and further reading