Logical Reasoning - Inference

Introduction

Logical reasoning gives AI systems the ability to derive new facts from known information using formal rules of inference. While machine learning excels at pattern recognition from data, logical reasoning excels at guaranteed correct deductions from established premises. AI systems use logical reasoning for theorem proving, knowledge base querying, planning, and verification. Understanding logic is fundamental because it provides the mathematical foundation upon which much of AI's reasoning capabilities are built.

Propositional Logic Basics

¬P (NOT P)	Negation
P ∧ Q (P AND Q)	Conjunction — true only if both true
P ∨ Q (P OR Q)	Disjunction — true if at least one true
P	Q (P IMPLIES Q): Implication — false only if P true and Q false
P ↔ Q (P IFF Q)	Biconditional — true if both same value
Truth Table for Implication (P	Q):
P \| Q \| P	Q
Key insight	"If it rains, the ground is wet" is only false when

Rules of Inference

Modus Ponens (most important rule)

Premise 1: P → Q (If P then Q)

Premise 2: P (P is true)

Conclusion: Q (Therefore Q is true)

Example: "If it rains, I carry umbrella. It is raining. Therefore, I carry umbrella."

Modus Tollens

Premise 1: P → Q (If P then Q)

Premise 2: ¬Q (Q is false)

Conclusion: ¬P (Therefore P is false)

Example: "If it rains, ground is wet. Ground is dry. Therefore, it's not raining."

Hypothetical Syllogism (chain rule)

Premise 1: P → Q

Premise 2: Q → R

Conclusion: P → R

Example: "If I study, I pass. If I pass, I graduate. Therefore, if I study, I graduate."

Resolution (used in automated provers)

Premise 1: P ∨ Q

Premise 2: ¬P ∨ R

Conclusion: Q ∨ R

(Eliminate complementary literals P and ¬P)

Predicate Logic (First-Order Logic)

Predicates	Properties or relations
Student(x)	x is a student
Teaches(x, y)	x teaches y
GreaterThan(x, y)	x > y
∀x P(x)	"For all x, P(x) is true" (universal)
∃x P(x)	"There exists an x such that P(x)" (existential)
"All students study": ∀x (Student(x)	Studies(x))
"Some students are brilliant"	∃x (Student(x) ∧ Brilliant(x))
"Every teacher has students": ∀x (Teacher(x)	∃y (Teaches(x,y) ∧ Student(y)))
Rule: ∀x (Human(x)	Mortal(x))
Fact	Human(Socrates)
Conclude	Mortal(Socrates)

Worked Example: Logic-Based Reasoning

Knowledge Base

1. ∀x (Dog(x) → Animal(x)) Dogs are animals

2. ∀x (Animal(x) → HasHeart(x)) Animals have hearts

3. ∀x (Dog(x) → Loyal(x)) Dogs are loyal

4. Dog(Rex) Rex is a dog

5. ∀x (Loyal(x) ∧ Animal(x) → GoodPet(x)) Loyal animals are good pets

Query: Is Rex a good pet?

Proof

Step 1: Dog(Rex) [Given, fact 4]

Step 2: Animal(Rex) [From 1 + 4, Modus Ponens with x=Rex]

Step 3: Loyal(Rex) [From 3 + 4, Modus Ponens with x=Rex]

Step 4: Loyal(Rex) ∧ Animal(Rex) [From 2 + 3, Conjunction]

Step 5: GoodPet(Rex) [From 5 + 4, Modus Ponens with x=Rex]

Answer: YES, Rex is a good pet. ✓

Reasoning Under Uncertainty

Fuzzy Logic	Truth values in [0, 1]
AND	min(A, B)
OR	max(A, B)
NOT	1 - A
Probabilistic Logic	Attach probabilities to statements
Default Reasoning	Assume typical unless told otherwise
"Tweety is a penguin"	Tweety doesn't fly (exception overrides default)

Logic in AI Applications

Planning (STRIPS)

Preconditions and effects expressed as logical formulas

Initial state: At(Robot, RoomA) ∧ ¬Holding(Robot, Box)

Goal: At(Box, RoomB)

Action: Pickup(x): Pre: At(Robot, loc) ∧ At(x, loc), Effect: Holding(Robot, x)

Databases (SQL is logic!):

SELECT * FROM students WHERE gpa > 3.5 AND major = 'CS'

≡ {x | Student(x) ∧ GPA(x) > 3.5 ∧ Major(x, CS)}

Prolog Programming

parent(tom, bob).

parent(bob, ann).

grandparent(X, Z) :- parent(X, Y), parent(Y, Z).

?- grandparent(tom, ann). → Yes

Verification: Proving software correctness

Pre: x > 0

Code: y = x * 2

Post: y > 0 ∧ y > x

Prove: If x > 0, then x*2 > 0 and x*2 > x ✓

Summary

Logical reasoning provides AI with the ability to make guaranteed correct deductions from given premises. From simple propositional logic to expressive first-order logic, these formal systems enable knowledge representation, automated theorem proving, planning, and program verification. While pure logic struggles with uncertainty and learning, it remains essential for domains requiring provably correct reasoning, and it complements statistical methods in modern AI systems that combine logical structure with probabilistic uncertainty.

Introduction

Propositional Logic Basics

¬P (NOT P)	Negation
P ∧ Q (P AND Q)	Conjunction — true only if both true
P ∨ Q (P OR Q)	Disjunction — true if at least one true
P	Q (P IMPLIES Q): Implication — false only if P true and Q false
P ↔ Q (P IFF Q)	Biconditional — true if both same value
Truth Table for Implication (P	Q):
P \| Q \| P	Q
Key insight	"If it rains, the ground is wet" is only false when

Rules of Inference

Modus Ponens (most important rule)

Premise 1: P → Q (If P then Q)

Premise 2: P (P is true)

Conclusion: Q (Therefore Q is true)

Example: "If it rains, I carry umbrella. It is raining. Therefore, I carry umbrella."

Modus Tollens

Premise 1: P → Q (If P then Q)

Premise 2: ¬Q (Q is false)

Conclusion: ¬P (Therefore P is false)

Example: "If it rains, ground is wet. Ground is dry. Therefore, it's not raining."

Hypothetical Syllogism (chain rule)

Premise 1: P → Q

Premise 2: Q → R

Conclusion: P → R

Example: "If I study, I pass. If I pass, I graduate. Therefore, if I study, I graduate."

Resolution (used in automated provers)

Premise 1: P ∨ Q

Premise 2: ¬P ∨ R

Conclusion: Q ∨ R

(Eliminate complementary literals P and ¬P)

Predicate Logic (First-Order Logic)

Predicates	Properties or relations
Student(x)	x is a student
Teaches(x, y)	x teaches y
GreaterThan(x, y)	x > y
∀x P(x)	"For all x, P(x) is true" (universal)
∃x P(x)	"There exists an x such that P(x)" (existential)
"All students study": ∀x (Student(x)	Studies(x))
"Some students are brilliant"	∃x (Student(x) ∧ Brilliant(x))
"Every teacher has students": ∀x (Teacher(x)	∃y (Teaches(x,y) ∧ Student(y)))
Rule: ∀x (Human(x)	Mortal(x))
Fact	Human(Socrates)
Conclude	Mortal(Socrates)

Worked Example: Logic-Based Reasoning

Knowledge Base

1. ∀x (Dog(x) → Animal(x)) Dogs are animals

2. ∀x (Animal(x) → HasHeart(x)) Animals have hearts

3. ∀x (Dog(x) → Loyal(x)) Dogs are loyal

4. Dog(Rex) Rex is a dog

5. ∀x (Loyal(x) ∧ Animal(x) → GoodPet(x)) Loyal animals are good pets

Query: Is Rex a good pet?

Proof

Step 1: Dog(Rex) [Given, fact 4]

Step 2: Animal(Rex) [From 1 + 4, Modus Ponens with x=Rex]

Step 3: Loyal(Rex) [From 3 + 4, Modus Ponens with x=Rex]

Step 4: Loyal(Rex) ∧ Animal(Rex) [From 2 + 3, Conjunction]

Step 5: GoodPet(Rex) [From 5 + 4, Modus Ponens with x=Rex]

Answer: YES, Rex is a good pet. ✓

Reasoning Under Uncertainty

Fuzzy Logic	Truth values in [0, 1]
AND	min(A, B)
OR	max(A, B)
NOT	1 - A
Probabilistic Logic	Attach probabilities to statements
Default Reasoning	Assume typical unless told otherwise
"Tweety is a penguin"	Tweety doesn't fly (exception overrides default)

Logic in AI Applications

Planning (STRIPS)

Preconditions and effects expressed as logical formulas

Initial state: At(Robot, RoomA) ∧ ¬Holding(Robot, Box)

Goal: At(Box, RoomB)

Action: Pickup(x): Pre: At(Robot, loc) ∧ At(x, loc), Effect: Holding(Robot, x)

Databases (SQL is logic!):

SELECT * FROM students WHERE gpa > 3.5 AND major = 'CS'

≡ {x | Student(x) ∧ GPA(x) > 3.5 ∧ Major(x, CS)}

Prolog Programming

parent(tom, bob).

parent(bob, ann).

grandparent(X, Z) :- parent(X, Y), parent(Y, Z).

?- grandparent(tom, ann). → Yes

Verification: Proving software correctness

Pre: x > 0

Code: y = x * 2

Post: y > 0 ∧ y > x

Prove: If x > 0, then x*2 > 0 and x*2 > x ✓

Logical Reasoning - Inference

Introduction

Propositional Logic Basics

Rules of Inference

Modus Ponens (most important rule)

Modus Tollens

Hypothetical Syllogism (chain rule)

Resolution (used in automated provers)

Predicate Logic (First-Order Logic)

Worked Example: Logic-Based Reasoning

Knowledge Base

Proof

Reasoning Under Uncertainty

Logic in AI Applications

Planning (STRIPS)

Prolog Programming

Summary

Continue learning this concept

Logical Reasoning - Inference

Introduction

Propositional Logic Basics

Rules of Inference

Modus Ponens (most important rule)

Modus Tollens

Hypothetical Syllogism (chain rule)

Resolution (used in automated provers)

Predicate Logic (First-Order Logic)

Worked Example: Logic-Based Reasoning

Knowledge Base

Proof

Reasoning Under Uncertainty

Logic in AI Applications

Planning (STRIPS)

Prolog Programming

Summary

Continue learning this concept