AI · Knowledge, reasoning, and planning

8 · First-Order Logic

Represent objects, their properties, and relations—not just whole statements. Explore how quantifiers turn a compact rule into claims about a domain.

From symbols to a world

8.1 Representation Revisited

Good representation makes important distinctions explicit while keeping inference manageable. First-order logic (FOL) adds individuals and relations to propositional logic's indivisible facts.

8.2 Syntax and Semantics of First-Order Logic

Constants name objects, predicates express properties or relations, and functions map objects to objects. A model supplies a domain and interpretations; quantifiers range over that domain. ∀ means “for every,” ∃ means “for at least one.”

8.3 Using First-Order Logic

Translate “every learner reads a book” as ∀x (Learner(x) → ∃y (Book(y) ∧ Reads(x,y))). Variables are bound by quantifiers; predicates state what is true of chosen objects.

8.4 Knowledge Engineering in First-Order Logic

Choose the task and vocabulary, encode general rules and specific facts, then ask queries and check whether the resulting model captures intended meanings. A formalization is only as sound as its assumptions.

Key terms and a scope check

Domain: objects a model talks about. Interpretation: which objects constants name and which tuples make predicates true. Quantifier scope: the formula governed by ∀ or ∃. A variable is bound inside its quantifier’s scope; elsewhere it is free.

In ∀x (Learner(x) → ∃y (Book(y) ∧ Reads(x,y))), the existential quantifier is inside ∀x: each learner may have a different book. Reversing the quantifiers to ∃y∀x would claim one shared book that every learner reads.

Model trace: the domain is {Mira, Noah, Pip}; Kind is true of Mira and Noah only. ∀x Kind(x) is false, with Pip as a counterexample; ∃x Kind(x) is true, with Mira and Noah as witnesses. The answer is relative to this finite model, not a claim about all real objects.

Interactive model

Quantifiers over a domain

Predicate: Kind(x)

Toggle facts about each object, then evaluate ∀x Kind(x) or ∃x Kind(x) in this finite model.

Formula to evaluate

∀x Kind(x) ∃x Kind(x)

Model evaluation

Demo algorithm and complexity

For a domain of n objects, the code checks each stored Kind fact: universal is true iff all n facts are true; existential is true iff at least one is true. It also lists all true objects to show witnesses, or reports the first counterexample.

Time: O(n) per evaluation. Auxiliary space: O(n) for the temporary witness list created while evaluating; the facts and rendered labels/checkboxes also occupy O(n) model/UI space. The displayed domain currently has n = 3. This assumes a finite, nonempty domain and one stored Boolean fact per object.