Symbolic LogicRules of Replacement

Proofs with All Eighteen Rules

Combine rules of inference and replacement, often reshaping a line with replacement until an inference rule fits.

Not started Jump to practice

You now have all eighteen rules: eight of inference (Proof Strategy: Working Backward) and ten of replacement (Equivalence, Exportation and Tautology (Equiv, Exp, Taut)). Real proofs mix them, and the skill is knowing when to reshape a line and when to infer from it.

Key idea

Use rules of replacement to reshape a line until an inference rule fits; then infer. Before each step, ask what shape the next inference rule needs, and replace only toward that shape.

Why it works

Inference rules are picky about form: MT needs an exact negated consequent, DS an exact negated disjunct, MP an exact antecedent. Replacement rules are the adapters that make the shapes line up. Working backward tells you which shape you need, so you are not trying all ten rules at random.
A negated conditional gives its antecedent: Impl, DM, Simp, DN.

Worked examples

Worked example: Reshape, then infer

Premises $\neg p \lor q$ and $p$. Prove $q$.
  1. MP needs a conditional. Impl turns $\neg p \lor q$ into $p \to q$ (line 3).
  2. Line 4: $q$ by MP 3, 2.

Answer: Alternatively: DN on $p$ gives $\neg \neg p$, then DS. Either route works.

Worked example: A longer one

Premises $(p \lor q) \to r$ and $\neg r$. Prove $\neg p$.
  1. Line 3: $\neg (p \lor q)$ by MT 1, 2.
  2. Line 4: $\neg p \land \neg q$ by DM 3.
  3. Line 5: $\neg p$ by Simp 4.

Answer: MT, DM, Simp.

Worked example: Choose the shape

Premises $p \to q$ and $p \to r$. Prove $p \to (q \land r)$. Which rules?
  1. Getting there with only the eighteen rules takes several steps (Impl, Dist, and more).
  2. Conditional proof, the next lesson, does it in four lines.

Answer: A sign that a new method is coming.

Common mistake

Reaching for a long chain of replacements when a short inference would do. Five replacement steps that end where one MT would have taken you are not wrong, but they are easy to get wrong. Plan backward: name the inference rule that will finish the proof, then use the fewest replacements needed to give it the shape it wants.

Two habits help most. First, always look at the main connective of each premise and of the conclusion, since that is all the rules ever see. Second, remember the common adapters: DN for exact negations, DM for negations in front of parentheses, Impl to switch between conditionals and disjunctions, and Equiv to unpack a biconditional. With those four, most proofs fall into place.

  • What is the last rule likely to be?
  • What exact shape does it need?
  • Which replacement turns a line I have into that shape?
  • Check each replacement changes only one part.

Some conclusions are awkward with these rules alone, especially conditionals like the third example. The next unit adds conditional proof and indirect proof, which make such proofs short and natural.

Practice

Pass with 3 right answers, the last 2 in a row. Each right answer earns 3 XP.

Loading practice…

Builds on

Leads to

Sources and further reading

  • Patrick J. Hurley and Lori Watson, A Concise Introduction to Logic, 13th ed., section 7.4, strategy with all eighteen rules
  • forall x: Calgary, an open introduction to formal logic (P. D. Magnus, Tim Button and others; Open Logic Project), chapter on proof strategies
@teddyrookbook GitHub