First-Order Logic: Overview and Motivation
Chapter 8 — First-Order Logic Book: Artificial Intelligence: A Modern Approach (Russell & Norvig, 4th ed) Pages: 251–290
Why First-Order Logic?
Propositional logic (Ch.7) can only represent facts about a fixed, finite set of things.
Problems with propositional logic: - Requires
separate symbol for every fact: Pit_1_3,
Pit_2_3, … (doesn’t generalize) - Cannot express “All
squares adjacent to a pit are breezy” as a single rule - Does not scale
to large or open-ended domains
First-Order Logic (FOL) extends propositional logic with: - Objects: the things in the world - Relations: properties of objects or relationships between them - Functions: mappings from objects to objects - Variables and quantifiers: statements over all or some objects
FOL can express:
∀s Breezy(s) ↔︎ ∃r Adjacent(r, s) ∧ Pit(r)
The Ontological Commitment
| Logic | Assumes world contains | Example |
|---|---|---|
| Propositional | Facts (true/false) | Raining |
| First-order | Objects and relations | Father(John, Mary) |
| Temporal | Time and facts | Raining(Now) |
| Probabilistic | Degrees of belief | P(Raining)=0.7 |
FOL’s ontological commitment: the world consists of objects (individuals) that may have properties and stand in relations to one another.
Epistemological Commitment
What agents can believe about logical sentences:
| Logic | Belief states |
|---|---|
| Propositional | true / false / unknown |
| First-order | true / false / unknown |
| Probability theory | 0.0 to 1.0 (degree) |
FOL maintains crisp true/false/unknown beliefs — not degrees. Probability (Ch.12+) handles uncertainty.
Key Insight: Power Through Generality
FOL allows a single rule to capture what propositional logic needs O(n) propositions to represent:
Propositional (for each square (i,j)):
B_1_1 ↔ (P_1_2 ∨ P_2_1)
B_1_2 ↔ (P_1_1 ∨ P_1_3 ∨ P_2_2)
... (one per square)First-order:
∀b,s Breezy(b) ∧ Adjacent(b,s) → ∃p Pit(p) ∧ At(p,s)One rule replaces n² rules. FOL is compositionally expressive.