6.3 Rules of Inference, Validity Proofs & Resolution Refutation

Back to Discrete Mathematics Notes

📚Module 06: Propositional Logic & Inference RulesTopic 6.3: Rules of Inference, Validity Proofs & Resolution Refutation⏱️5 min read

🎯High-Yield For:Semester Exams • GATE CSE • Technical Interviews

💡 Core Intuition: The 3-Second Mental Model

🍳 The Everyday Analogy: Legal Courtrooms & Mathematical Chain Reactions

Think of logical inference like a criminal court trial:

1. Valid Argument (Airtight Case): The prosecutor presents evidence premises ($P_1, P_2, \dots, P_k$). If the evidence is accepted as true, the conclusion ($Q$) is inescapably locked in. It is impossible for all premises to be true without the conclusion also being true!
2. Modus Ponens (Forward Drive): "If you speed ($p$), you get a ticket ($q$). You were caught speeding ($p$). Conclusion: You get a ticket ($q$)." Clean, direct forward deduction.
3. Modus Tollens (Backward Denial): "If you speed ($p$), you get a ticket ($q$). You did NOT get a ticket ($\neg q$). Conclusion: You were NOT speeding ($\neg p$)."
4. Resolution Refutation (Proof by Self-Destruction): To prove that a suspect is guilty, assume the opposite (assume they are innocent: $\neg Q$). Feed that assumption into the evidence machine. If the assumption collides with the facts to produce an impossible physical contradiction (the empty clause $\square$), the assumption is blown to pieces, leaving the suspect's guilt as the only mathematical reality!

💻 Bridging to Computer Science: Prolog, Type Checkers & Automated Verifiers

In computer systems:

• Prolog & Logic Programming: Execution in Prolog is literally Robinson's Resolution: the interpreter resolves Horn clauses backwards from queries until deriving the empty clause yes.
• Compiler Type Systems: Type inference engines (e.g., Haskell or Rust trait solvers) use inference rules to deduce the principal type of expressions.
• Formal Verification (Model Checkers): Safety properties in aircraft control software and cryptographic protocols are proven by showing that unsafe error states are unreachable via resolution refutation.

📑Table of Contents

• 🏛️ Formal Arguments & The Definition of Validity
• 💥 Vacuous Arguments & The Principle of Explosion
• 📐 The Master Catalog of Rules of Inference
  • Master 12-Case Argument Validity Diagnostic Matrix
• 💥 Robinson's Resolution Refutation: Automated Theorem Proving
• 📝 Step-by-Step Worked Examples
  • Example 1: Formal Deductive Proof using Inference Rules
  • Example 2: Proof by Resolution Refutation
  • Example 3: Disproving an Argument via the Critical Row Method
• 🎯 Exam & Interview Pitfall Check

---

🏛️ Formal Arguments & The Definition of Validity

📖Definition 6.5: Formal Argument, Validity & Soundnessdefinition

An argument in propositional logic is a sequence of propositions ending with a conclusion. The initial propositions $P_1, P_2, \dots, P_k$ are called premises (or hypotheses), and the final proposition $Q$ is the conclusion:

$$P_1, \; P_2, \; \dots, \; P_k \vdash Q$$

Written in classical vertical deduction notation:

$$\begin{array}{c} P_1 \\ P_2 \\ \vdots \\ P_k \\ \hline \therefore Q \end{array}$$

1. Validity: An argument is valid if and only if the conclusion $Q$ is True whenever all premises $P_1, P_2, \dots, P_k$ are simultaneously True. $$\text{Argument is Valid} \iff (P_1 \land P_2 \land \dots \land P_k) \to Q \text{ is a Tautology}$$
2. Invalidity (Fallacy): An argument is invalid if there is at least one truth assignment where all premises are True, but the conclusion $Q$ is False (a counterexample row in the truth table).
3. Soundness: An argument is sound if and only if:
   • It is structurally valid, AND
   • All of its premises $P_1, \dots, P_k$ are factually True in reality.

📐Method 6.1: The Critical Row Method for Validity Checkingmethod

To verify whether an argument $P_1, P_2, \dots, P_k \vdash Q$ is valid using a truth table:

1. Construct the truth table for all propositional variables, listing columns for each premise $P_1, \dots, P_k$ and the conclusion $Q$.
2. Identify Critical Rows: A row is a critical row if and only if every premise evaluates to True ($P_1 = T, P_2 = T, \dots, P_k = T$).
3. Ignore Non-Critical Rows: Any row where even a single premise is False ($F$) can be ignored (since $F \to Q$ is trivially True by vacuous implication).
4. Evaluate Conclusion $Q$:
   • If $Q$ is True in every single critical row, the argument is Valid.
   • If there exists even one critical row where $Q$ is False, the argument is Invalid!

---

💥 Vacuous Arguments & The Principle of Explosion

Competitive exams frequently test edge-case arguments involving vacuous truths and contradictory premises:

📐Theorem 6.4: Vacuous Premises & The Principle of Explosiontheorem

1. Vacuous Truth Argument: $$\neg P \vdash P \to Q \quad (\text{Strictly VALID!})$$ Proof: If premise $\neg P = T$, then $P = F$. By the Implication Law, $F \to Q$ is True regardless of $Q$.
2. Trivial Consequent Argument: $$Q \vdash P \to Q \quad (\text{Strictly VALID!})$$ Proof: If premise $Q = T$, then by the Implication Law, $P \to T$ is True regardless of $P$.
3. Negated Implication Arguments: $$\neg(P \to Q) \vdash P \quad (\text{VALID!})$$ $$\neg(P \to Q) \vdash \neg Q \quad (\text{VALID!})$$ Proof: $\neg(P \to Q) \equiv P \land \neg Q$. By Simplification, both $P$ and $\neg Q$ logically follow.
4. The Principle of Explosion (Ex Falso Quodlibet): $$P, \; \neg P \vdash Q \quad (\text{Strictly VALID for ANY statement } Q!)$$ Proof: The conjunction of contradictory premises is $(P \land \neg P) \equiv \mathbf{F}$. The implication formula for the argument is: $$(P \land \neg P) \to Q \equiv \mathbf{F} \to Q \equiv \neg\mathbf{F} \lor Q \equiv \mathbf{T} \lor Q \equiv \mathbf{T}$$ Because the formula is a Tautology, an argument with inconsistent/contradictory premises is always valid, even if $Q$ is "The moon is made of green cheese"! (Though such an argument can never be sound).

---

📐 The Master Catalog of Rules of Inference

Rather than constructing unwieldy $2^n$-row truth tables, formal proofs string together elementary, verified Rules of Inference:

The 8 Classical Rules of Propositional Inference

Fundamental deductive deduction steps proven by tautological implication

🎯

1. Modus Ponens

Affirming Antecedent

• Premises: p, p → q
• Conclusion: ∴ q
• Tautology: (p ∧ (p → q)) → q

🛡️

2. Modus Tollens

Denying Consequent

• Premises: ¬q, p → q
• Conclusion: ∴ ¬p
• Tautology: (¬q ∧ (p → q)) → ¬p

🔗

3. Hypothetical Syllogism

Chain Transitivity

• Premises: p → q, q → r
• Conclusion: ∴ p → r
• Tautology: ((p → q) ∧ (q → r)) → (p → r)

✂️

4. Disjunctive Syllogism

Elimination of Alternative

• Premises: p ∨ q, ¬p
• Conclusion: ∴ q
• Tautology: ((p ∨ q) ∧ ¬p) → q

➕

5. Addition

Disjunctive Weakening

• Premise: p
• Conclusion: ∴ p ∨ q
• Tautology: p → (p ∨ q)

🔍

6. Simplification

Conjunctive Extraction

• Premise: p ∧ q
• Conclusion: ∴ p
• Tautology: (p ∧ q) → p

🤝

7. Conjunction

Mutual Synthesis

• Premises: p, q
• Conclusion: ∴ p ∧ q
• Tautology: (p ∧ q) → (p ∧ q)

⚡

8. Resolution Principle

Clause Cancellation

• Premises: p ∨ q, ¬p ∨ r
• Conclusion: ∴ q ∨ r (The Resolvent)
• Tautology: ((p ∨ q) ∧ (¬p ∨ r)) → (q ∨ r)

Master 12-Case Argument Validity Diagnostic Matrix

Index	Argument Schema	Classical Logical Name	Validity Status	Mathematical Justification / Counterexample Row
1	$p, \; p \to q \vdash q$	Modus Ponens	Valid	$(p \land (p \to q)) \to q \equiv \mathbf{T}$
2	$\neg q, \; p \to q \vdash \neg p$	Modus Tollens	Valid	Contrapositive of Modus Ponens
3	$p \to q, \; q \to r \vdash p \to r$	Hypothetical Syllogism	Valid	Transitivity of Implication
4	$p \lor q, \; \neg p \vdash q$	Disjunctive Syllogism	Valid	$((\neg p) \land (p \lor q)) \equiv (\neg p \land q) \implies q$
5	$p \lor q, \; p \to r, \; q \to r \vdash r$	Proof by Cases (Dilemma)	Valid	Eliminates both paths into shared consequence $r$
6	$p \lor q, \; p \to r, \; q \to s \vdash r \lor s$	Constructive Dilemma	Valid	Synthesizes disjunctive consequences
7	$p \to r, \; q \to s, \; \neg r \lor \neg s \vdash \neg p \lor \neg q$	Destructive Dilemma	Valid	Contrapositive generalization of Dilemma
8	$\neg(p \land q), \; p \vdash \neg q$	De Morgan Disjunctive Syllogism	Valid	$\neg p \lor \neg q$ with $p$ forces $\neg q$
9	$p, \; \neg p \vdash q$	Principle of Explosion	Valid	Contradictory premises make antecedent False ($\mathbf{F} \to q \equiv \mathbf{T}$)
10	$q, \; p \to q \vdash p$	Affirming the Consequent	INVALID	Counterexample row: $p = F, q = T$ (Premises $T$, Conclusion $F$)
11	$\neg p, \; p \to q \vdash \neg q$	Denying the Antecedent	INVALID	Counterexample row: $p = F, q = T$ (Premises $T$, Conclusion $F$)
12	$p \lor q, \; p \vdash \neg q$	Affirming a Disjunct	INVALID	Inclusive OR allows both to be True ($p = T, q = T$)

---

💥 Robinson's Resolution Refutation: Automated Theorem Proving

In automated deduction and modern SAT solvers, verifying validity using classical heuristic rules requires broad branching searches. J. Alan Robinson's Resolution Principle (1965) reduces all logical inference to a single mechanical rule.

⚡Rule 6.1: The Resolution Rulelaw

Given two disjunctive clauses containing complementary literals $p$ and $\neg p$:

$$C_1 = p \lor A \quad \text{and} \quad C_2 = \neg p \lor B$$

The Resolution Rule cancels the complementary pair to produce the Resolvent:

$$\text{Resolvent} = A \lor B$$

Special Case (The Empty Clause $\square$): When resolving a unit clause $p$ with its direct negation $\neg p$:

$$p, \; \neg p \vdash \square \quad (\text{Empty Clause} \equiv \mathbf{F})$$

Deriving $\square$ signifies that an irreconcilable logical contradiction has occurred.

★ Derivation of Empty Clause (□)

Mechanical refutation: Deriving the empty clause □ proves the theorem is valid.

The 4-Step Resolution Refutation Algorithm

How modern SAT solvers and automated verifiers prove theorem validity

1

Negate the Conclusion

Proof by Contradiction

To prove P₁, P₂, ..., Pₖ ⊢ Q, assume ¬Q is True. Add ¬Q to the set of premises.

2

Convert Everything to CNF Clauses

Clause Normalization

Convert all premises and the negated conclusion into a flat set of disjunctive clauses S.

3

Iteratively Resolve Complementary Literals

Resolution Loop

Select two clauses with complementary literals (l and ¬l), resolve them, and append the resolvent to S.

4

Derive the Empty Clause (□)

Refutation Achieved

When unit clauses l and ¬l resolve to produce □ (False), the set S is unsatisfiable. Therefore, Q is VALID!

---

📝 Step-by-Step Worked Examples

Example 1: Formal Deductive Proof using Inference Rules

Problem Statement: Prove that the following argument is valid:

1. $p \to (q \land r)$
2. $p$
3. $r \to s$
4. $\therefore s$

Step-by-Step Solution:

Step	Expression	Justification
1	$p$	Premise 2
2	$p \to (q \land r)$	Premise 1
3	$q \land r$	Modus Ponens (Steps 1 & 2)
4	$r$	Simplification (Step 3)
5	$r \to s$	Premise 3
6	$s$	Modus Ponens (Steps 4 & 5)

The conclusion $s$ is derived cleanly using valid inference rules at every step. Therefore, the argument is Valid.

Key Takeaway: Deductive step-by-step proofs avoid the exponential $2^4 = 16$ row truth table by stringing together standard inference rules.

---

Example 2: Proof by Resolution Refutation

Problem Statement: Using Resolution Refutation, prove that the following argument is valid:

• Premise 1: $p \lor q$
• Premise 2: $\neg p \lor r$
• Premise 3: $\neg r$
• Conclusion: $q$

Step-by-Step Solution:

1. Step 1: Negate the Conclusion

   • The conclusion is $q$.
   • Negated conclusion: $\neg q$.

2. Step 2: Convert all formulas to CNF Clauses

   • Clause 1: $p \lor q$
   • Clause 2: $\neg p \lor r$
   • Clause 3: $\neg r$
   • Clause 4: $\neg q$
   • Set of Clauses: $$S = \{ p \lor q, \; \neg p \lor r, \; \neg r, \; \neg q \}$$

3. Step 3: Systematic Clause Resolution

   • Resolution 1: Resolve Clause 1 ($p \lor q$) with Clause 2 ($\neg p \lor r$) on literal $p$: $$\text{Clause 5} = q \lor r$$
   • Resolution 2: Resolve Clause 5 ($q \lor r$) with Clause 3 ($\neg r$) on literal $r$: $$\text{Clause 6} = q$$
   • Resolution 3: Resolve Clause 6 ($q$) with Clause 4 ($\neg q$) on literal $q$: $$\text{Clause 7} = \square \quad (\text{Empty Clause!})$$

4. Step 4: Conclusion

   • Deriving the empty clause $\square$ demonstrates that the set $\{P_1, P_2, P_3, \neg Q\}$ is Unsatisfiable.
   • Therefore, the negated conclusion is impossible, proving that the original argument is Strictly Valid!

---

Example 3: Disproving an Argument via the Critical Row Method

Problem Statement: Determine whether the following argument is valid:

$$p \to q, \; q \to r, \; r \vdash p$$

Step-by-Step Solution:

1. Construct the Truth Table Row Inspection:
   • Consider the truth valuation: $p = F, q = T, r = T$.
2. Evaluate Premises:
   • Premise 1: $p \to q \equiv F \to T = T$ (True).
   • Premise 2: $q \to r \equiv T \to T = T$ (True).
   • Premise 3: $r = T$ (True).
   • All three premises are simultaneously True! Thus, this is a Critical Row.
3. Evaluate Conclusion:
   • The conclusion is $p = F$ (False).
4. Conclusion:
   • Because all premises are True while the conclusion is False, the valuation $(F, T, T)$ serves as a counterexample.
   • The argument is INVALID (This is a multi-step instance of the Fallacy of Affirming the Consequent).

---

🎯 Exam & Interview Pitfall Check

Core Conceptual Questions

Question 1: If an argument has contradictory premises (e.g., $P_1 = p$, $P_2 = \neg p$), is the argument valid for ANY conclusion $Q$? Key Focus Points: Yes! This is the Principle of Explosion (Ex Falso Quodlibet). The definition of validity states that $(P_1 \land P_2) \to Q$ must be a tautology. If the premises contradict, their conjunction is False ($p \land \neg p \equiv \mathbf{F}$). By the Implication Law, $\mathbf{F} \to Q$ is always True for any statement $Q$! Thus, an argument with inconsistent premises is always trivially valid (though unsound).

Question 2: Can a valid argument have all False premises and a True conclusion? Key Focus Points: Yes! Validity only guarantees that if the premises are True, the conclusion must be True. It imposes no restrictions when premises are False. For example:

• Premise 1: "All fish can fly" ($F$).
• Premise 2: "A crow is a fish" ($F$).
• Conclusion: "A crow can fly" ($T$). The logical form is 100% valid, even though both premises are false!

Common Interview Traps: Architectural Trade-Offs

Trap 1: Confusing Validity with Truth (Soundness) Why it fails: An argument can be completely valid while talking about flying elephants and impossible nonsense. Validity is purely a property of the structural form of the argument, not the factual truth of its propositions! An argument is only Sound if it is both structurally valid and factually true.

Trap 2: Resolving multiple pairs of literals simultaneously Why it fails: In resolution, you must resolve EXACTLY ONE complementary pair at a time! For example, resolving $(p \lor q)$ with $(\neg p \lor \neg q)$ by canceling both $p$ and $q$ simultaneously to produce $\square$ is an illegal move! The correct resolvents are $(q \lor \neg q) \equiv \mathbf{T}$ or $(p \lor \neg p) \equiv \mathbf{T}$. Never cancel two pairs in one step!

🗺️View Complete Discrete Mathematics Roadmap & Syllabus

← Previous Topic6.2 Implications: Converse, Inverse, Contrapositive & Normal Forms (CNF/DNF)Next Topic →7.1 Predicates, Quantifiers (∀, ∃) & Domain of Discourse Formalisms