Inference Rules

Unit 6: Knowledge-Based Agents and Inference — Section 6.2

How does an inference engine actually derive conclusions? It uses inference rules — patterns that let it take one or more known sentences and produce a new, guaranteed-true sentence. Think of inference rules as the gears inside the reasoning machine: given valid inputs, they always produce valid outputs.

Learn the fundamental inference rules that power logical reasoning systems.

Rules of Inference

What Is an Inference Rule?

An inference rule is a schema that says: given sentences of a certain form, you may write down a new sentence. We write inference rules using the notation:

Premise 1
Premise 2
──────────
Conclusion

The horizontal line means "therefore." If the premises are in your knowledge base, you are entitled to add the conclusion.

Inference Rule: A pattern-matching rule that allows an agent to derive a new sentence from one or more existing sentences. A sound inference rule guarantees that whenever the premises are true, the conclusion is also true.

Sound inference rules preserve truth: you can never use a sound rule to derive a false conclusion from true premises. This property is what makes logical reasoning reliable. In the real world, we trust a diagnosis system precisely because its inference rules are logically valid.

Rule 1: Modus Ponens

Modus Ponens (Latin: "mode of affirming") is the cornerstone of forward reasoning. If you know an implication is true and you know the antecedent is true, you can conclude the consequent.

Modus Ponens

α → β      (if α then β)
α           (α is true)
──────────
β           (therefore, β is true)

The intuition is simple: if the rule "rain implies wet ground" is true, and you know it is raining, then you know the ground is wet. You don’t need to look outside — logic tells you.

Applying Modus Ponens

Scenario 1 — Everyday reasoning:

Rule:   IF raining THEN ground_wet
Fact:   raining = TRUE
────────────────────────────────
Result: ground_wet = TRUE  ✓

Scenario 2 — Access control:

Rule:   user_logged_in ∧ has_permission → allow_access
Fact:   user_logged_in = TRUE
Fact:   has_permission = TRUE
────────────────────────────────
Result: allow_access = TRUE  ✓

Scenario 3 — Chained reasoning:

R1: study_hard → good_grades
R2: good_grades → scholarship
R3: scholarship → happy

Fact: study_hard = TRUE

Step 1: Apply MP to R1 → good_grades = TRUE
Step 2: Apply MP to R2 → scholarship = TRUE
Step 3: Apply MP to R3 → happy = TRUE

Each step of the chain is a valid application of Modus Ponens.

Modus Ponens with conjunctive conditions (multiple conditions joined with AND) works the same way: every condition must be true before you can conclude the consequent. This is the form most commonly used in expert system rules:

fever ∧ cough ∧ fatigue → influenza
fever = TRUE
cough = TRUE
fatigue = TRUE
──────────────────────────────────
influenza = TRUE

Rule 2: And-Elimination

And-Elimination is the simplest inference rule. If you know a conjunction (an AND sentence) is true, then each individual conjunct must be true.

And-Elimination

α ∧ β      (α and β are both true)
──────────
α           (therefore, α is true)
──────────
β           (therefore, β is true)

And-Elimination in Use

Suppose the KB contains the sentence:

fever = HIGH ∧ cough = PRESENT ∧ fatigue = SEVERE

By And-Elimination, the inference engine may separately assert:

fever = HIGH       ✓
cough = PRESENT    ✓
fatigue = SEVERE   ✓

This matters when a compound fact has been added to the KB as a single sentence (perhaps obtained from a database record) and rules need to match individual components.

Rule 3: Resolution

Resolution is more general than Modus Ponens. It works with clauses — disjunctions (OR sentences) of literals — and can be applied even when no implication is present. Resolution is the basis of automated theorem provers and the inference algorithm used in Prolog.

Resolution

P ∨ Q      (P or Q)
¬P ∨ R     (not-P or R)
──────────
Q ∨ R      (therefore, Q or R)

The key step: find two clauses that contain complementary literals (P in one, ¬P in the other). Cancel them out and combine the remaining literals with OR.

Applying Resolution

Example 1 — Basic:

Clause 1: raining ∨ snowing
Clause 2: ¬raining ∨ wet_ground
─────────────────────────────
Cancel "raining" and "¬raining":
Result: snowing ∨ wet_ground

Interpretation: Either it’s snowing, or the ground is wet — or both. Both original clauses must be true, and together they force at least one of these conclusions.

Example 2 — Deriving a unit clause (single literal):

Clause 1: flu ∨ cold
Clause 2: ¬flu
─────────────
Cancel "flu" and "¬flu":
Result: cold

When one clause is a single negated literal, resolution produces a "unit clause" — a single definite fact.

Example 3 — Proving by refutation: To prove "wet_ground is true," add ¬wet_ground to the KB and derive a contradiction (the empty clause). If you reach the empty clause, the assumption was inconsistent, proving wet_ground must be true.

Resolution Refutation: A proof strategy where you assume the negation of what you want to prove, then apply resolution repeatedly. If you derive the empty clause (a contradiction), the original assumption was false, which means your goal is provably true. This technique underlies all Prolog-style inference.

Valid Rules vs. Logical Fallacies

Not all intuitive-seeming reasoning patterns are logically valid. Two common fallacies look superficially like Modus Ponens but are not sound:

Affirming the Consequent — INVALID

P → Q
Q
──────
P    (WRONG!)

Example: "If it rains, the ground is wet. The ground is wet. Therefore, it rained." The ground could be wet because a sprinkler ran.

Denying the Antecedent — INVALID

P → Q
¬P
──────
¬Q   (WRONG!)

Example: "If it rains, the ground is wet. It did not rain. Therefore the ground is not wet." Again — the sprinkler could have run.

Remembering these two fallacies will save you from countless reasoning errors. The ground being wet is consistent with rain, but does not prove rain. Logic is strict: only Modus Ponens (affirming the antecedent) is valid.

Comparing the Three Rules

Feature Modus Ponens And-Elimination Resolution

Feature	Modus Ponens	And-Elimination	Resolution
Pattern	`P, P→Q ⊢ Q`	`P∧Q ⊢ P` and `P∧Q ⊢ Q`	`P∨Q, ¬P∨R ⊢ Q∨R`
Input form	Implication + fact	Conjunction	Any two clauses
Output form	Single fact	Individual conjuncts	Disjunction (or unit clause)
Best for	Forward/backward chaining	Decomposing compound facts	Theorem proving, Prolog
Completeness	Not complete alone	Not complete alone	Complete for propositional logic

Pattern

P, P→Q ⊢ Q

P∧Q ⊢ P and P∧Q ⊢ Q

P∨Q, ¬P∨R ⊢ Q∨R

Input form

Implication + fact

Conjunction

Any two clauses

Output form

Single fact

Individual conjuncts

Disjunction (or unit clause)

Best for

Forward/backward chaining

Decomposing compound facts

Theorem proving, Prolog

Completeness

Not complete alone

Complete for propositional logic

In practice, most expert systems use Modus Ponens almost exclusively because it matches the natural "if-then rule" format that domain experts think in. Resolution is used in formal theorem provers and logic programming systems like Prolog where more general reasoning is needed.

You have the following knowledge base:

R1: late_for_class → missed_lecture
R2: missed_lecture → fell_behind
R3: fell_behind ∧ no_tutoring → failed_exam
late_for_class = TRUE
no_tutoring = TRUE

Walk through each inference step. Which rule applies at each step? What conclusions can you reach? Could any of those conclusions be false in the real world even if the rules are followed correctly?

Practice applying inference rules to derive new facts from a knowledge base.

Next: 6.3 Forward Chaining →

Based on the UC Berkeley CS 188 Online Textbook by Nikhil Sharma, Josh Hug, Jacky Liang, and Henry Zhu, licensed under CC BY-SA 4.0.

This work is licensed under CC BY-SA 4.0.