Rules of Inference

# CHAPTER 6

Rules of Inference #

1. Introduction #

If you have 5 variables ($p, q, r, s, t$), generating a Truth Table to prove a compound logic statement requires $2^5 = 32$ rows. If you have 10 variables, you need 1,024 rows! Truth Tables rapidly become mathematically impossible to calculate by hand. To bypass the explosion of Truth Tables, mathematicians and computer scientists use Rules of Inference. These are universally proven logical "shortcuts." By chaining these verified shortcuts together, we can construct formal Proofs—deducing absolute new truths purely from existing data without ever drawing a table.

2. Learning Objectives #

By the end of this chapter, you will be able to:

• Define what constitutes a valid Logical Argument and a Proof.

• Master the fundamental Rules of Inference (Modus Ponens, Modus Tollens, etc.).

• Construct a step-by-step mathematical proof.

• Identify common logical fallacies that destroy algorithmic integrity.

3. Arguments and Validity #

An Argument is a sequence of propositions ending with a conclusion.

• Premises: The facts we assume to be absolutely True (e.g., $p \rightarrow q$).

• Conclusion: The final statement we are trying to prove is True (indicated by the symbol $\therefore$, meaning "therefore").

An argument is Valid if, whenever all the premises are True, the conclusion is mathematically guaranteed to be True.

4. Modus Ponens (The Law of Detachment) #

The most famous and fundamental rule of logic. If we know that an implication is true, and we know the hypothesis actually happened, the conclusion must be true.

The Rule:

1. 1. $p \rightarrow q$ (If you study, you pass)

1. 2. $p$ (You studied)

$\therefore q$ (Therefore, you pass)

*Code Application:* This is the exact definition of a standard if block. If the condition triggers, the block executes.

5. Modus Tollens (The Law of Contraposition) #

Based on the Contrapositive (Chapter 4). If an implication is true, but the conclusion NEVER happened, the hypothesis could not have happened either.

The Rule:

1. 1. $p \rightarrow q$ (If you study, you pass)

1. 2. $\neg q$ (You DID NOT pass)

$\therefore \neg p$ (Therefore, you DID NOT study)

*Code Application:* Reverse debugging. If the final database entry is missing ($\neg q$), we logically prove that the initial API call must have failed ($\neg p$).

6. Hypothetical Syllogism (The Chain Rule) #

If Cause A triggers Effect B, and Effect B triggers Effect C, then Cause A mathematically guarantees Effect C.

The Rule:

1. 1. $p \rightarrow q$ (If it rains, the grass is wet)

1. 2. $q \rightarrow r$ (If the grass is wet, I will slip)

$\therefore p \rightarrow r$ (Therefore, if it rains, I will slip)

*Code Application:* Transitive routing in networks. If Server A connects to Server B, and B connects to C, Server A can route packets to C.

7. Other Core Rules #

• Disjunctive Syllogism:

1. 1. $p \lor q$ (I will eat pizza OR tacos)

1. 2. $\neg p$ (I did NOT eat pizza)

$\therefore q$ (Therefore, I must have eaten tacos!)

• Addition:

1. 1. $p$ (I have an Apple)

$\therefore p \lor q$ (Therefore, I have an Apple OR a million dollars. *This is technically mathematically True because OR only requires one side to be True!*)

• Simplification:

1. 1. $p \land q$ (I have an Apple AND a Banana)

$\therefore p$ (Therefore, I have an Apple)

8. Constructing a Formal Proof #

Let's prove a conclusion using a chain of rules. Premises Given:

1. 1. $p \rightarrow q$

1. 2. $\neg q$

1. 3. $p \lor r$

Goal: Prove that $r$ is True.

The Proof: Step 1: $p \rightarrow q$ (Given Premise 1) Step 2: $\neg q$ (Given Premise 2) Step 3: $\therefore \neg p$ (Applying Modus Tollens to Steps 1 and 2). Step 4: $p \lor r$ (Given Premise 3) Step 5: $\therefore r$ (Applying Disjunctive Syllogism to Steps 3 and 4: We know it must be $p$ or $r$, but Step 3 proved it is NOT $p$. Therefore, it MUST be $r$!). *Proof Complete!*

9. Common Mistakes (Fallacies) #

• Fallacy of Affirming the Consequent:

1. 1. $p \rightarrow q$ (If you study, you pass)

1. 2. $q$ (You passed)

$\therefore p$ (Therefore you studied. *FALSE! You could have cheated! Never assume the Converse is True!*)

10. Exercises #

1. 1. State the Rule of Inference used here: "If $x > 10$, then $x > 5$. We know $x > 10$. Therefore, $x > 5$."

1. 2. Write a formal 3-step proof. Premises: $A \rightarrow B$, $B \rightarrow C$, $A$. Prove: $C$.

11. MCQs with Answers #

Q10. True or False: Constructing a formal logical Proof is entirely dependent on guessing the correct combinations of variables. a) True. Proofs are fundamentally random. b) False. Formal Proofs are rigorous, step-by-step mathematical algorithms. Each sequential line must be unequivocally justified by citing a specific, universally approved Rule of Inference targeting the localized premises of previous lines. Answer: b) False. Formal Proofs are rigorous, step-by-step mathematical algorithms. Each sequential line...

12. Interview Preparation #

Top Interview Questions:

• *Logical Deduction:* "You are debugging a server. Rule 1: If the Cache fails, the Database handles the load. Rule 2: If the Database handles the load, latency spikes. You observe that latency did NOT spike. Did the Cache fail?" *(Answer: No! Apply Modus Tollens to Rule 2 to prove the DB did NOT handle the load. Then apply Modus Tollens to Rule 1 to prove the Cache did NOT fail!)*

13. Summary #

Rules of Inference elevate discrete mathematics from brute-force calculation into elegant deductive reasoning. By memorizing the geometric behavior of Modus Ponens, Tollens, and Syllogisms, architects can systematically trace complex software bugs backward, prove algorithmic efficiency, and guarantee the absolute security of conditional routing matrices.

14. Next Chapter Recommendation #

We have mastered the mathematics of Logic. We now pivot to the mathematics of Data. How do we formally organize 10 Million user records into searchable groupings? In Chapter 7: Set Theory Fundamentals, we transition from evaluating booleans to architecting the foundational blueprint of all relational databases and arrays.