Rules of Inference

13 min read

Quick Reference

Before You Start: Prerequisite Check

Try This First

A Sentence That Must Follow

Mathematical reasoning is a sequence of small forced steps. At each step you already hold some true statements, and you ask one question: which new statement is forced to be true by what you already have?

A rule of inference is one such forced step, written as a template. The template has a short list of statements above a line (the things you already hold) and one statement below the line (the thing that is forced). Reading from the warm-up argument:

$$ \begin{array}{l} p \rightarrow q \\ p \\ \hline \therefore\ q \end{array} $$

The horizontal line reads “therefore.” The two statements above the line are the premises; the statement below is the conclusion. The claim of the rule is that any time the premises are all true, the conclusion cannot be false.

Each rule earns its place for one reason: the conditional that says “if all the premises are true then the conclusion is true” is a tautology, a statement true in every row of its truth table. So the validity of a rule is checked once, in advance, by a truth table, and then the rule is reused without rechecking. Tautologies are what make the rules trustworthy.

Prerequisite Hub

graph LR
    subgraph Builds_On["Builds On"]
        A["Propositional<br/>Equivalences"]
        B["Predicates and<br/>Quantifiers"]
        G["Nested<br/>Quantifiers"]
    end

    subgraph ThisSkill["This Skill"]
        C["Rules of<br/>Inference"]
    end

    subgraph Unlocks
        D["Introduction<br/>to Proofs"]
    end

    A --> C
    B --> C
    G --> C
    C --> D

    style C fill:#d1fae5,stroke:#a565f0,stroke-width:3px

    click C "rules-of-inference.html"
    click D "../ch1-sec7/introduction-to-proofs.html"

Builds on:

Leads into:

Cross-course prerequisites: none.

Official Definitions

Each definition below is quoted from Rosen, 8th edition, Section 1.6, with the page citation. These are the canonical statements to put on the board and on a study sheet.

Argument, premises, conclusion, and validity

By an argument, we mean a sequence of statements that end with a conclusion. By valid, we mean that the conclusion, or final statement of the argument, must follow from the truth of the preceding statements, or premises, of the argument. That is, an argument is valid if and only if it is impossible for all the premises to be true and the conclusion to be false.

Rosen 8e, Section 1.6, subsection 1.6.1 Introduction, p. 73.

Two cautions sit inside this definition. First, validity is about the form of the argument, not about whether the premises happen to be true. An argument can be valid while resting on a false premise; in that case validity guarantees nothing about the conclusion in the real world. Second, “must follow” is the strong word: there is to be no row of the combined truth table in which every premise is true and the conclusion is false.

Rule of inference

Rules of inference are templates for constructing valid arguments; they are the basic tools for establishing the truth of statements. Each rule of inference can be established using a tautology.

Rosen 8e, Section 1.6, p. 73-74 (verbatim discussion).

The phrase “established using a tautology” is the working definition for a study sheet. To show that a proposed rule is legitimate, form the conditional whose hypothesis is the conjunction of the premises and whose conclusion is the rule’s conclusion, then confirm by truth table that this conditional is a tautology.

Modus ponens (law of detachment)

The rule of inference modus ponens, or the law of detachment, is based on the tautology $((p \rightarrow q) \wedge p) \rightarrow q$. It is written: premise $p \rightarrow q$, premise $p$, therefore conclusion $q$.

Rosen 8e, Section 1.6, p. 74-75 and Table 1 Rules of Inference.

The name translates as “mode that affirms”: the second premise affirms the hypothesis $p$, which detaches the conclusion $q$ from the conditional.

Table 1: Rules of Inference for Propositional Logic

These are the eight rules of Section 1.6 for propositional logic, each with the tautology that establishes it.

Rosen 8e, Section 1.6, Table 1 Rules of Inference, p. 74-77.

One way to read each rule: the conclusion is forced. Another way: the rule throws away information. Simplification, for instance, takes the strong premise $p \wedge q$ and keeps only $p$; the rule is safe precisely because it concludes something weaker than what it was given. Asking, for each rule, “is the conclusion stronger or weaker than the premises” is a quick check on whether a step is legitimate.

Table 2: Rules of Inference for Quantified Statements

When arguments involve $\forall$ and $\exists$, four further rules move between a quantified statement and a statement about a particular element. Here $c$ denotes an element of the domain.

Rosen 8e, Section 1.6, Table 2 Rules of Inference for Quantified Statements, subsection 1.6.6, p. 81-83.

The two conditions in the right column are where most errors occur. Universal generalization is legitimate only when $c$ was chosen with no special assumptions, so that whatever is proved about $c$ holds for every element. Existential instantiation must introduce a fresh name, because $\exists x\, P(x)$ promises that some element works without telling you which one.

Worked Examples

Example 1: A single step of modus tollens

Premises: “If the autograder passes, then the build compiled” and “the build did not compile.” What follows?

Predict first. The second premise denies the conclusion of the conditional. Predict whether you can deny its hypothesis.

Set up the symbols. Let $p$ be “the autograder passes” and $q$ be “the build compiled.” The premises are $p \rightarrow q$ and $\neg q$.

Apply the rule. This matches modus tollens:

$$ \begin{array}{l} p \rightarrow q \\ \neg q \\ \hline \therefore\ \neg p \end{array} $$

Conclusion. $\neg p$: “the autograder did not pass.” The prediction is confirmed; denying the conclusion of a conditional lets you deny its hypothesis.

Example 2: A chain of rules

Show that the conclusion $r$ follows from the premises $p \vee q$, $\neg p$, and $q \rightarrow r$.

Each line is forced by lines already established, so the argument is valid and the conclusion $r$ holds.

Why might this be valid as a whole? Each individual step rests on a tautology, and a chain of forced steps is itself forced: if there were a truth assignment making every premise true and $r$ false, it would have to break one of the five lines, but no line can break. Convince a classmate by asking them to find a single row of the truth table for $p$, $q$, $r$ in which all three premises are true and $r$ is false; there is none.

Example 3: An argument with quantifiers

Domain: all students in the section. Premises: “Every student who submitted the lab earned points” and “Avery submitted the lab.” Conclude that Avery earned points.

Let $S(x)$ be “$x$ submitted the lab” and $E(x)$ be “$x$ earned points.”

Universal instantiation brings the general rule down to the one element named in the second premise, and then modus ponens finishes the step. This pattern, universal instantiation followed by modus ponens, is so common that it has its own name, universal modus ponens.

Common Misconceptions

Practice Problems

Mastery Checklist

Novice (Level 1-2):

• I can state the definition of a valid argument (no row with all premises true and conclusion false).
• I can name modus ponens, modus tollens, and disjunctive syllogism from their premise and conclusion forms.
• I can identify affirming the consequent and denying the antecedent as errors, not rules.

Competent (Level 3-4):

• I can chain two or three rules into a multi-step argument and justify every line.
• I can show a proposed rule is valid by confirming its conditional is a tautology.
• I can combine disjunctive syllogism, hypothetical syllogism, and modus ponens in one argument.

Proficient (Level 5):

• I can apply universal and existential instantiation and generalization, respecting the condition on $c$.
• I can recognize and use universal modus ponens.
• I can explain why a valid argument with a false premise tells you nothing about the conclusion.

Connections

Looking back:

• Propositional Equivalences supplies the tautologies that establish each rule.
• Predicates and Quantifiers supplies the $\forall$ and $\exists$ statements that the quantified rules act on.
• Nested Quantifiers gives the reading order for premises that combine several quantifiers.

Looking ahead:

• Introduction to Proofs (Section 1.7): direct proof, proof by contraposition, and proof by contradiction are these rules chained into arguments about specific mathematical objects.

Real-world connections:

• Resolution, the last rule in Table 1, is the single inference rule behind automated theorem provers and logic-programming languages.
• Compiler and type-checker reasoning applies modus ponens and modus tollens to program facts.
• Digital-circuit verification searches for a truth assignment that makes a specification true and an implementation false, which is the same “no bad row” test that defines a valid argument.

Resources

Last updated: 2026-06-16