AI Notes
Learn predicate logic. Quantifiers, predicates, unification. AI logic 2024.
From Propositional to Predicate Logic
Propositional logic deals with whole statements (P, Q, R) that are either true or false. But it cannot express statements about objects, their properties, or relationships. "All humans are mortal" cannot be stated in propositional logic without listing every human individually. Predicate logic (first-order logic, FOL) adds variables, quantifiers, predicates, and functions, enabling vastly more expressive knowledge representation.
Predicate logic is the mathematical foundation for AI knowledge representation, database theory, program verification, and automated theorem proving. Understanding FOL is essential for reasoning systems, Prolog programming, and semantic web technologies.
Syntax of Predicate Logic
Components
| Constants | specific objects |
| Variables | placeholders for objects |
| Predicates | properties or relationships |
| Functions | mappings from objects to objects |
| Connectives: ∧ (and), ∨ (or), ¬ (not), | (implies), ↔ (iff) |
Well-Formed Formulas
Atomic formulas
Loves(john, mary) — John loves Mary
Greater(age(john), 18) — John's age > 18
Complex formulas
∀x (Human(x) → Mortal(x))
"For all x, if x is human then x is mortal"
∃x (Student(x) ∧ Smart(x))
"There exists an x such that x is a student and x is smart"
∀x (Parent(x, y) → Older(x, y))
"For all x, if x is parent of y then x is older than y"
Translating English to Predicate Logic
Common Patterns
| "Every student studies" | ∀x (Student(x) → Studies(x)) |
| NOTE: Universal uses | , NOT ∧ |
| "Some dogs are friendly" | ∃x (Dog(x) ∧ Friendly(x)) |
| "No cat likes water" | ¬∃x (Cat(x) ∧ Likes(x, water)) |
| Equivalently: ∀x (Cat(x) | ¬Likes(x, water)) |
| "Only adults can vote" | ∀x (CanVote(x) → Adult(x)) |
| NOTE: "Only A are B" means B | A (reverse!) |
| "John's mother loves everyone" | ∀y Loves(mother(john), y) |
Complex Translations
| ∀x ((Student(x) ∧ StudiesHard(x)) | Passes(x, exam)) |
| ∃x (Teacher(x) ∧ ∀y (Student(y) | Teaches(x, y))) |
| Reading 1 | ¬∃x ∀y Likes(x, y) — no one likes everyone |
| Reading 2 | ∀x ∃y ¬Likes(x, y) — everyone has someone they don't like |
Inference Rules in Predicate Logic
Universal Instantiation (UI)
| From | ∀x P(x) |
| Infer | P(a) for any constant a |
| ∀x (Human(x) | Mortal(x)) |
Existential Instantiation (EI)
From: ∃x P(x)
Infer: P(c) for a NEW constant c (Skolem constant)
Example:
∃x (Prime(x) ∧ Even(x))
——————————————————————————
Prime(c) ∧ Even(c) [c is a fresh constant, could be 2]
Universal Generalization (UG)
From: P(a) proved for arbitrary a (no assumptions about a)
Infer: ∀x P(x)
Must ensure a was truly arbitrary (not a specific constant)
Unification: Matching Predicate Expressions
Unification finds substitutions that make two expressions identical:
| Substitution | {x/mary} |
| Result | Knows(john, mary) |
| Substitution | {y/john, x/mary} |
| Result | Knows(john, mary) |
| Substitution | {x/john}... but then Knows(john, john) ≠ Knows(john, mary) |
| Most General Unifier (MGU) | most flexible substitution |
Predicate Logic in AI Systems
Prolog (Programming in Logic)
% Knowledge base
parent(tom, bob).
parent(tom, liz).
parent(bob, ann).
parent(bob, pat).
% Rules
grandparent(X, Z) :- parent(X, Y), parent(Y, Z).
sibling(X, Y) :- parent(Z, X), parent(Z, Y), X \= Y.
% Query
?- grandparent(tom, ann).
% Prolog traces: parent(tom, bob), parent(bob, ann) → yes!Semantic Web (OWL/RDF)
OWL axioms (description logic, subset of FOL):
Human ⊑ ∃hasParent.Human (every human has a human parent)
Father ≡ Male ⊓ Parent (father = male and parent)
Enables: automated classification, consistency checking
Limitations of Predicate Logic
| 1. Undecidability | No algorithm can determine truth of all FOL formulas |
| 2. Semi-decidability | Can prove true formulas, but may loop on false ones |
| 4. Frame problem | Describing what DOESN'T change is verbose |
Interview Questions
Q: What's the difference between ∀x (P(x) → Q(x)) and ∀x (P(x) ∧ Q(x))? A: The first says "all P's are Q's" (if something is P, then it's Q). The second says "everything is both P and Q" (much stronger, usually wrong). "All cats are animals" is ∀x(Cat(x)→Animal(x)), NOT ∀x(Cat(x)∧Animal(x)) which would claim everything is a cat AND an animal.
Q: Why use → with ∀ and ∧ with ∃? A: ∀x(P(x)∧Q(x)) claims everything satisfies both P and Q—too strong. ∀x(P(x)→Q(x)) claims "among P-things, all are Q." Similarly, ∃x(P(x)→Q(x)) is trivially true when anything is not-P, so ∃x(P(x)∧Q(x)) correctly says "something is both P and Q."
Q: What is Skolemization? A: Removing existential quantifiers by replacing existentially quantified variables with Skolem functions. ∃x∀y P(x,y) becomes P(c,y). ∀x∃y P(x,y) becomes P(x,f(x))—the choice of y depends on x. Needed for resolution-based theorem proving.
Exam Focus
Revise definitions, diagrams, examples, and short-answer points for Predicate Logic - First-Order Logic.
Interview Use
Prepare one clear explanation, one practical example, and one common mistake for this Artificial Intelligence topic.
Search Terms
artificial-intelligence, artificial intelligence, artificial, intelligence, knowledge, representation, predicate, logic
Related Artificial Intelligence Topics