---
title: Knowledge Representation
module: Logic and Planning
moduleNumber: 3
lessonNumber: 11
order: 311
summary: >
  First-order logic gives you the language; this lesson is about what to say in
  it. This first part builds the content: a general upper ontology from the top
  down, categories as first-class objects with taxonomies and inheritance,
  physical composition and the count-noun/mass-noun split, events and time reified
  through the event calculus, and belief modeled with modal logic — the machinery
  for representing the world an agent reasons about.
topics: [Logic]
sources:
  - book: AIMA
    ref: "Ch. 12 — Knowledge Representation; §12.1 Ontological Engineering; §12.2 Categories and Objects"
  - book: AIMA
    ref: "§12.3 Events; §12.4 Mental Events and Mental Objects"
---


[First-order logic](/artificial-intelligence/logic-and-planning/first-order-logic)
settles the _syntax_ of a knowledge base: objects, relations, functions,
quantifiers, and the [inference](/artificial-intelligence/logic-and-planning/inference-and-resolution)
that draws new sentences from old. It says nothing about _what_ to write down. In
a toy domain the choice barely matters — the wumpus world gets by with a handful
of predicates and almost any encoding works. A domain like shopping on the
Internet or driving a car needs general, reusable representations of concepts
that recur everywhere: objects, substances, time, events, and beliefs. Designing
those representations is **ontological engineering**, and it is the difference
between a logic that _could_ describe the world and a knowledge base that
actually does.[^onto]

The plan of the chapter is to build the content first and the reasoning
machinery second. We start with a general ontology and work down through
categories, physical objects and stuff, events and time, and mental objects.
Then we return to technology: reasoning systems built specifically for
categories (semantic networks and description logics), and the handling of
default information, where a conclusion holds only until some more specific fact
overrides it.

## The upper ontology

We will not write a complete description of everything — that would overflow even
a thousand-page book — but we can lay down the general framework and leave
placeholders where domain knowledge slots in later, the way an object-oriented
framework defines `Window` and expects you to subclass it into
`SpreadsheetWindow`. The framework of the most general concepts is an **upper
ontology**, so called because graphs are drawn with the general concepts at the
top and specializations below.

$$
% caption: The upper ontology of the world. Each link means the lower concept is
% a specialization of the upper one; specializations need not be disjoint (a
% human is both an animal and an agent), and physical objects sit under
% generalized events for reasons developed in the section on fluents.
\begin{tikzpicture}[>=stealth, font=\footnotesize, xscale=1.28,
  n/.style={font=\footnotesize, inner sep=1.5pt},
  every path/.style={black}]
  \definecolor{acc}{HTML}{2348F2}
  \node[n, text=acc] (any) at (0,3.6) {Anything};
  \node[n] (abs) at (-3.7,2.6) {AbstractObjects};
  \node[n] (gev) at (3.9,2.6)  {GeneralizedEvents};
  % abstract side
  \node[n] (sets) at (-6.3,1.6) {Sets};
  \node[n] (num)  at (-5.3,1.6) {Numbers};
  \node[n] (rep)  at (-2.7,1.6) {RepresentationalObjects};
  \node[n] (cat)  at (-6.3,0.6) {Categories};
  \node[n] (sent) at (-3.7,0.6) {Sentences};
  \node[n] (meas) at (-1.9,0.6) {Measurements};
  \node[n] (times) at (-2.6,-0.4) {Times};
  \node[n] (wts)   at (-1.3,-0.4) {Weights};
  % event side
  \node[n] (intv) at (1.0,1.6) {Interval};
  \node[n] (plc)  at (2.7,1.6) {Places};
  \node[n] (phys) at (4.5,1.6) {PhysicalObjects};
  \node[n] (proc) at (6.6,1.6) {Processes};
  \node[n] (mom)  at (1.0,0.6) {Moments};
  \node[n] (thing) at (3.7,0.6) {Things};
  \node[n] (stuff) at (5.7,0.6) {Stu\/f\/f};
  \node[n] (ani) at (3.0,-0.4) {Animals};
  \node[n] (agt) at (4.4,-0.4) {Agents};
  \node[n] (sol) at (5.2,-0.4) {Solid};
  \node[n] (liq) at (6.1,-0.4) {Liquid};
  \node[n] (gas) at (7.0,-0.4) {Gas};
  \node[n] (hum) at (3.7,-1.4) {Humans};
  \draw (any) -- (abs); \draw (any) -- (gev);
  \draw (abs) -- (sets); \draw (abs) -- (num); \draw (abs) -- (rep);
  \draw (rep) -- (cat); \draw (rep) -- (sent); \draw (rep) -- (meas);
  \draw (meas) -- (times); \draw (meas) -- (wts);
  \draw (gev) -- (intv); \draw (gev) -- (plc); \draw (gev) -- (phys); \draw (gev) -- (proc);
  \draw (intv) -- (mom); \draw (phys) -- (thing); \draw (phys) -- (stuff);
  \draw (thing) -- (ani); \draw (thing) -- (agt);
  \draw (stuff) -- (sol); \draw (stuff) -- (liq); \draw (stuff) -- (gas);
  \draw (ani) -- (hum); \draw (agt) -- (hum);
\end{tikzpicture}
$$

Two properties separate a general-purpose ontology from a pile of special-purpose
ones. It should apply to essentially any domain, once you add domain-specific
axioms — nothing can be finessed or omitted. And in a demanding
domain, different areas of knowledge must **unify**, because one problem touches
several at once: a circuit-repair robot reasons about electrical connectivity,
physical layout, timing, and labor cost simultaneously, so the sentences about
time must combine with the sentences about space and work equally well for
nanoseconds and minutes as for angstroms and meters.

In practice, general ontological engineering has had only limited
success — none of the largest AI systems share one ontology, partly because
agreeing on an ontology is a social act. "Every ontology is a treaty," in Tom
Gruber's phrase. The ontologies that do exist were built four ways: hand-crafted
by trained logicians (CYC), imported from a structured database (DBpedia, from
Wikipedia), extracted by parsing text (TextRunner, from Web pages), or
crowdsourced from volunteers (OpenMind).

A second caveat is about the logic itself. We use first-order logic even though
parts of the world resist it: most generalizations have exceptions or hold only
to a degree. "Tomatoes are red" is a useful rule, but some tomatoes are green,
yellow, or orange. Handling exceptions matters, but it is orthogonal to getting
the ontology right, so we defer it to the sections on default reasoning below and
the full treatment of uncertainty to
[probability](/artificial-intelligence/uncertainty/probability-and-bayes).

## Categories and objects

Most reasoning happens at the level of **categories**, not individuals. A shopper
wants _a_ basketball, not the particular ball $BB_9$. Categories also drive
prediction: from green-and-yellow mottled skin, a foot of diameter, red flesh,
and a location in the fruit aisle you infer _watermelon_, and from that you infer
it would be good in a fruit salad. Perception classifies; the class then predicts.

First-order logic offers two ways to represent a category. You can use a predicate,
$Basketball(b)$, or you can **reify** the category as an object, $Basketballs$,
and relate individuals to it with membership and subset relations. Reification —
turning a proposition into an object you can quantify over and attach facts to — is
what lets a category be a thing in its own right. Writing $b \in Basketballs$ says
$b$ is a member; $Basketballs \subset Balls$ says the first category is a
**subcategory** (subclass, subset — we use the terms interchangeably) of the
second.

Subclass relations organize categories into a **taxonomy**. Taxonomies are old and
large: biology organizes roughly ten million living and extinct species into one
hierarchy, and library science built the Dewey Decimal system to classify all of
knowledge. The point of the hierarchy is **inheritance**: assert that every member
of $Food$ is edible, that $Fruit \subset Food$ and $Apples \subset Fruit$, and
every apple inherits edibility without a separate axiom.

$$
% caption: A fragment of a taxonomy. Each downward link is a subclass relation
% ($Apples \subset Fruit$), and edibility asserted at $Food$ is inherited by
% every category below it down to the individual apple $A_1$.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  c/.style={draw, minimum width=17mm, minimum height=7mm, font=\footnotesize},
  i/.style={draw, minimum width=13mm, minimum height=6mm, font=\footnotesize}]
  \definecolor{acc}{HTML}{2348F2}
  \node[c, draw=acc, text=acc] (food) at (0,2.6) {Food};
  \node[c] (fruit) at (-1.6,1.2) {Fruit};
  \node[c] (veg)   at (1.9,1.2)  {Vegetables};
  \node[c] (apple) at (-2.6,-0.1) {Apples};
  \node[c] (orange) at (-0.4,-0.1) {Oranges};
  \node[i] (a1) at (-2.6,-1.5) {A1};
  \draw[black] (food) -- (fruit); \draw[black] (food) -- (veg);
  \draw[black] (fruit) -- (apple); \draw[black] (fruit) -- (orange);
  \draw[black] (apple) -- (a1);
  \node[acc, font=\scriptsize, anchor=west] at (0.9,2.6) {edible (asserted here)};
  \draw[->, acc, thick] (0.6,2.35) .. controls (1.6,0.2) and (-1.2,-1.15) .. (a1.east);
  \node[acc, font=\scriptsize, anchor=west] at (-1.4,-1.5) {inherited};
\end{tikzpicture}
$$

First-order logic states many kinds of category fact cleanly. An object is a
member: $BB_9 \in Basketballs$. A category is a subclass: $Basketballs \subset
Balls$. Every member has a property: $(x \in Basketballs) \Rightarrow
Spherical(x)$. Members can be recognized by properties, giving a sufficient
condition for membership; and the category as a whole can have properties, as in
$Dogs \in DomesticatedSpecies$ — note that because $Dogs$ is itself a member here,
$DomesticatedSpecies$ must be a category _of categories_.

Membership and subclass are not the only relations we need between categories.
Two categories are **disjoint** if they share no members; a set of categories is an
**exhaustive decomposition** of a larger one if every member of the larger belongs
to at least one; and a disjoint exhaustive decomposition is a **partition**.

> **Definition (Partition).** A set of categories $s$ partitions a category $c$
> when its members are pairwise disjoint and together cover $c$:
> $Partition(s,c) \iff Disjoint(s) \land ExhaustiveDecomposition(s,c)$. So
> $Partition(\{Males, Females\}, Animals)$ says every animal is exactly one of
> male or female.

Categories can also be **defined** by necessary and sufficient conditions rather
than merely described: $x \in Bachelors \iff Unmarried(x) \land x \in Adults
\land x \in Males$. Such strict definitions are the exception, though. Most
real-world categories are **natural kinds** with no clean definition — a tomato is
_typically_ dull scarlet, roughly spherical, two to four inches across, but there
is variation at every feature and no crisp boundary. The practical response is to
separate what is true of _all_ members from what is true of _typical_ ones, using
a function $Typical(c) \subseteq c$, and to attach the soft facts to
$Typical(Tomatoes)$. This is the first appearance of default reasoning; we return
to it below.

### Physical composition

One object can be **part of** another. $PartOf(Bucharest, Romania)$,
$PartOf(Romania, EasternEurope)$, and so on up to $PartOf(Europe, Earth)$; the
relation is transitive and reflexive, so a reasoner concludes $PartOf(Bucharest,
Earth)$. Categories of **composite objects** are characterized by structural
relations among their parts. A biped has exactly two legs attached to a body:

$$
Biped(a) \;\Rightarrow\; \exists\, l_1, l_2, b \;\; Leg(l_1) \land Leg(l_2) \land
Body(b) \land PartOf(l_1, a) \land PartOf(l_2, a) \land Attached(l_1, b) \land
Attached(l_2, b) \land l_1 \neq l_2
$$

with a further clause forcing any third leg to be one of the first two. The "exactly
two" idiom is awkward in first-order logic; description logics, later in this
lesson, make cardinality constraints like this far cleaner.

The mass of a composite object is the sum of its parts' masses — unlike a category,
which has no mass even when its members do. To talk about the collective object
formed from some parts without ascribing to it the abstract nothing-ness of a set,
we use a **bunch**. If the apples are $Apple_1, Apple_2, Apple_3$, then
$BunchOf(\{Apple_1, Apple_2, Apple_3\})$ is a normal, if unstructured, object with
those apples as parts, and it can have a weight where the _set_ cannot. $BunchOf(s)$
is defined as the smallest object of which each element of $s$ is a part — an
instance of **logical minimization**, defining an object as the least one meeting a
condition.

### Measurements

Objects have height, mass, cost. The values assigned to such properties are
**measures**, represented with a **units function** applied to a number. If $L_1$ is
a line segment, $Length(L_1) = Inches(1.5) = Centimeters(3.81)$; conversions equate
multiples of one unit to another, $Centimeters(2.54 \times d) = Inches(d)$. Note
$\text{\textdollar}(1)$ is not a dollar bill — there is exactly one object named $\text{\textdollar}(1)$, though
there can be many dollar bills — and $Inches(0)$ and $Centimeters(0)$ denote the
same zero length while $Seconds(0)$ does not.

Not every measure has an agreed numerical scale. Exercises have difficulty, poems
have beauty; imposing a number on beauty would be a mistake. What matters is not
the number but that measures can be **ordered**. We can believe one exercise is
tougher than another, and that a tougher exercise yields a lower expected score,
using only $>$ and $<$:

$$
e_1, e_2 \in Exercises \land Difficulty(e_1) > Difficulty(e_2) \;\Rightarrow\;
ExpectedScore(e_1) < ExpectedScore(e_2)
$$

That is enough to decide which exercises to attempt, with no numerical difficulty
ever assigned. Monotonic relationships of this kind are the basis of **qualitative
physics**, which reasons about physical systems without solving their equations.

### Objects: things and stuff

Some of reality resists **individuation** — division into distinct objects. Cut an
aardvark in half and you do not get two aardvarks; cut a lump of butter in half and
each piece is still butter. English marks the distinction with **count nouns**
(aardvark, hole, theorem) and **mass nouns** (butter, water, energy). To represent
_stuff_, put the gross lumps you interact with into the ontology as objects —
$Butter_3$ is the lump you left on the table — alongside the category $Butter$,
whose members are all such lumps, with the rule that any part of a butter-object is
also a butter-object:

$$
b \in Butter \land PartOf(p, b) \;\Rightarrow\; p \in Butter
$$

$$
% caption: Cutting a count-noun object destroys it (half an aardvark is not an
% aardvark), while any part of a mass-noun object is another object of the same
% kind (half of some butter is butter). Intrinsic properties survive the cut;
% extrinsic ones do not.
\begin{tikzpicture}[>=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  % --- count noun (left) ---
  \node[font=\footnotesize] at (1.4,2.7) {count noun: aardvark};
  \draw[black] (0,0.7) ellipse (1.55 and 0.75);
  \node[font=\footnotesize] at (0.55,0.7) {one object};
  \draw[red, thick, dashed] (1.4,1.7) -- (1.4,-0.3);
  \node[red, font=\scriptsize, anchor=south] at (1.4,1.75) {cut};
  \draw[->, black] (1.4,-0.6) -- (1.4,-1.2);
  \node[red, font=\footnotesize, align=center] at (1.4,-1.8) {two halves,\\neither an aardvark};
  % --- mass noun (right) ---
  \begin{scope}[xshift=6.2cm]
    \node[font=\footnotesize] at (1.4,2.7) {mass noun: butter};
    \draw[black] (0,0.05) rectangle (2.8,1.45);
    \node[font=\footnotesize] at (0.65,0.75) {a lump};
    \draw[acc, thick, dashed] (1.4,1.45) -- (1.4,0.05);
    \node[acc, font=\scriptsize, anchor=south] at (1.4,1.5) {cut};
    \draw[->, black] (1.4,-0.3) -- (1.4,-0.9);
    \node[acc, font=\footnotesize, align=center] at (1.4,-1.5) {both halves\\are butter};
  \end{scope}
\end{tikzpicture}
$$

The reason is that some properties are **intrinsic** — density, boiling point,
color, flavor, ownership — belonging to the substance rather than the object, and
retained under subdivision. Others are **extrinsic** — weight, length, shape — and
are not. A category defined only by intrinsic properties is a substance, or mass
noun; a category whose definition mentions any extrinsic property is a count noun.
$Stuff$ is the most general substance (no intrinsic properties specified); $Thing$
is the most general count noun.

The intrinsic/extrinsic split is the underlying distinction; the count-noun/mass-noun
grammar reflects it. The test is behavior under subdivision. Take a lump of butter
$Butter_3$ with density $0.911$ grams per cubic centimeter, weight $250$ grams, and
temperature $18$ degrees Celsius, and cut it in half.

$$
% caption: Intrinsic vs. extrinsic under subdivision. Cutting Butter_3 preserves the
% intrinsic properties (density, temperature, and the fact of being butter) but
% halves the extrinsic weight; a category defined only by intrinsic properties is a
% substance.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  box/.style={draw, minimum width=30mm, minimum height=13mm, align=center, font=\scriptsize}]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  \node[box] (whole) at (0,0) {Butter\_3\\density 0.911\\weight 250 g\\temp 18 C};
  \node[box] (h1) at (5.6,1.1) {half\\density 0.911\\weight 125 g\\temp 18 C};
  \node[box] (h2) at (5.6,-1.1) {half\\density 0.911\\weight 125 g\\temp 18 C};
  \draw[->, black] (whole) -- (h1) node[midway, above, sloped, font=\scriptsize] {cut};
  \draw[->, black] (whole) -- (h2) node[midway, below, sloped, font=\scriptsize] {cut};
  \node[acc, font=\scriptsize, anchor=west] at (8.3,0.5) {intrinsic: unchanged};
  \node[red, font=\scriptsize, anchor=west] at (8.3,-0.4) {extrinsic: halved};
\end{tikzpicture}
$$

Density, temperature, and butter-hood are intrinsic and survive: both halves have
density $0.911$ and both are butter, so the axiom $b \in Butter \land PartOf(p, b)
\Rightarrow p \in Butter$ holds. Weight is extrinsic and does not survive: each half
weighs $125$ grams, not $250$. If we had defined a category $QuarterPoundOfButter$
by its weight, cutting a member would produce two non-members — the count-noun
behavior, where the weight clause smuggles an extrinsic property into the
definition and turns a mass noun back into a count noun. This is why $Stuff$
specifies no extrinsic property at all, and why every count noun's definition can be
traced to at least one extrinsic clause.

## Events

Situation calculus, from the [planning](/artificial-intelligence/logic-and-planning/classical-planning)
material, describes a world where actions are discrete, instantaneous, and happen
one at a time. That breaks down for a continuous action like filling a bathtub: it
cannot describe what happens _during_ the action, nor two actions overlapping in
time. **Event calculus** fixes this by being built on points of time rather than
situations.[^event]

Event calculus reifies **fluents** and events. The fluent $At(Shankar, Berkeley)$
is an object naming the fact of Shankar being in Berkeley — it does not by itself
assert that the fact holds. To assert a fluent is true at a time we use the
predicate $T$, as in $T(At(Shankar, Berkeley), t)$. Events are members of event
categories: $E_1 \in Flyings \land Flyer(E_1, Shankar) \land Origin(E_1, SF) \land
Destination(E_1, DC)$. We then say $Happens(E_1, i)$ to place the event over a time
interval $i = (t_1, t_2)$.

The complete vocabulary is compact:

| Predicate | Meaning |
| --- | --- |
| $T(f, t)$ | fluent $f$ is true at time $t$ |
| $Happens(e, i)$ | event $e$ happens over interval $i$ |
| $Initiates(e, f, t)$ | event $e$ causes fluent $f$ to start holding at $t$ |
| $Terminates(e, f, t)$ | event $e$ causes fluent $f$ to cease holding at $t$ |
| $Clipped(f, i)$ | $f$ ceases to be true at some point during $i$ |
| $Restored(f, i)$ | $f$ becomes true at some point during $i$ |

A distinguished event $Start$ describes the initial state. The core axiom says a
fluent holds now if some past event initiated it and no intervening event clipped
it:

$$
Happens(e, (t_1, t_2)) \land Initiates(e, f, t_1) \land \lnot Clipped(f, (t_1, t))
\land t_1 < t \;\Rightarrow\; T(f, t)
$$

with a symmetric axiom for termination. This is the event-calculus analogue of a
successor-state axiom, and domain-specific fluents are defined the same way — the
wumpus agent gets an arrow only at the start and loses it only by shooting:
$Initiates(e, HaveArrow(a), t) \iff e = Start$ and $Terminates(e, HaveArrow(a), t)
\iff e \in Shootings(a)$. Because events are reified, arbitrary extra facts attach
freely: $Bumpy(E_1)$ records that the flight was bumpy, with no need to grow a
predicate's arity.

For example, run the arrow fluent all the way through the axioms.
The wumpus agent's history opens with $Happens(Start, (0, 0))$, and $Start$ is
the only event before the agent does anything. To show the agent still holds its
arrow at time $t = 5$, given that nothing has been shot yet — the only events in the
interval are movements and turns — instantiate the initiation axiom with $e = Start$,
$f = HaveArrow(Agent)$, $t_1 = 0$, and $t = 5$:

$$
\underbrace{Happens(Start, (0, 0))}_{\text{given}} \;\land\;
\underbrace{Initiates(Start, HaveArrow(Agent), 0)}_{\text{from } e = Start} \;\land\;
\underbrace{\lnot Clipped(HaveArrow(Agent), (0, 5))}_{\text{no shot yet}} \;\land\;
\underbrace{0 < 5}_{\text{true}}
$$

Each conjunct discharges. The first is the initial-state event. The second follows
from $Initiates(e, HaveArrow(a), t) \iff e = Start$ with $e$ bound to $Start$. The
third follows from the structure of the domain: $Clipped(f, i)$
means some event terminates $f$ inside $i$, and the only terminator of $HaveArrow$ is
a shooting; since no member of $Shootings(Agent)$ has happened in $(0, 5)$, nothing
clips the fluent. The fourth is arithmetic. The core axiom's antecedent is
satisfied, so it fires and concludes

$$
T(HaveArrow(Agent), 5)
$$

Now let the agent shoot at $t = 5$: $Happens(Shoot_5, (5, 5))$ with $Shoot_5 \in
Shootings(Agent)$. By the termination axiom, $Terminates(Shoot_5, HaveArrow(Agent),
5)$, and any attempt to prove $T(HaveArrow(Agent), 6)$ now fails at the third
conjunct, because $Shoot_5$ clips the fluent in $(0, 6)$ — $Clipped(HaveArrow(Agent),
(0, 6))$ holds. The fluent is true at 5 and false at 6, with no frame axiom listing
the movements and turns that left it untouched. That is the whole point of the
event-calculus treatment of the frame problem: persistence is the default, and only
initiation and termination events are written down.

### Processes

The events so far are **discrete events** — a definite beginning, middle, and end.
Shankar's trip from San Francisco to Washington is one; interrupted halfway it
would be a different event. But the category $Flyings$ has a different quality: take
any small sub-interval of the flight and it is still a member of $Flyings$. A
category with this property is a **process** or **liquid event**:

$$
(e \in Processes) \land Happens(e, (t_1, t_4)) \land (t_1 < t_2 < t_3 < t_4)
\;\Rightarrow\; Happens(e, (t_2, t_3))
$$

Liquid versus discrete events mirrors the distinction between stuff and things —
some call liquid events **temporal substances** and substances like butter
**spatial substances**.

### Time intervals

Event calculus lets us talk about time itself. Intervals come in two kinds:
**moments**, with zero duration, and **extended intervals** — and
$Partition(\{Moments, ExtendedIntervals\}, Intervals)$. Fix an arbitrary time scale
(midnight GMT, January 1, 1900, is time 0), and functions $Begin$, $End$, $Time$,
and $Duration$ pick out endpoints, absolute times, and lengths.

The relations _between_ two intervals — proposed by Allen — cover every way two
intervals can sit relative to each other. $Meet(i,j)$ holds when the end of $i$ is
the start of $j$; the rest are defined by comparing endpoints.

$$
% caption: Allen's interval relations. Each pair of bars shows how interval $i$
% (shaded) sits relative to $j$; $Meet$, $Before$/$After$, $During$, $Overlap$,
% $Starts$, $Finishes$, and $Equals$ exhaust the possibilities up to symmetry.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  bi/.style={draw, fill=black!12, minimum height=4.5mm, inner sep=0pt},
  bj/.style={draw, fill=white, minimum height=4.5mm, inner sep=0pt}]
  \definecolor{acc}{HTML}{2348F2}
  % Meet
  \node[font=\footnotesize, anchor=east] at (-0.2,3.4) {Meet(i,j)};
  \node[bi, minimum width=10mm] at (0.6,3.4) {i};
  \node[bj, minimum width=10mm] at (1.7,3.4) {j};
  % Before/After
  \node[font=\footnotesize, anchor=east] at (-0.2,2.5) {Before(i,j)};
  \node[bi, minimum width=8mm] at (0.5,2.5) {i};
  \node[bj, minimum width=8mm] at (2.0,2.5) {j};
  % During
  \node[font=\footnotesize, anchor=east] at (-0.2,1.6) {During(i,j)};
  \node[bi, minimum width=8mm] at (1.2,1.75) {i};
  \node[bj, minimum width=16mm] at (1.4,1.25) {j};
  % Overlap
  \node[font=\footnotesize, anchor=east] at (-0.2,0.6) {Overlap(i,j)};
  \node[bi, minimum width=11mm] at (0.9,0.75) {i};
  \node[bj, minimum width=11mm] at (1.9,0.25) {j};
  % right column
  \begin{scope}[xshift=6.2cm]
    \node[font=\footnotesize, anchor=east] at (-0.2,3.4) {Starts(i,j)};
    \node[bi, minimum width=7mm] at (0.55,3.55) {i};
    \node[bj, minimum width=14mm] at (0.9,3.05) {j};
    \node[font=\footnotesize, anchor=east] at (-0.2,2.2) {Finishes(i,j)};
    \node[bi, minimum width=7mm] at (1.25,2.35) {i};
    \node[bj, minimum width=14mm] at (0.9,1.85) {j};
    \node[font=\footnotesize, anchor=east] at (-0.2,1.0) {Equals(i,j)};
    \node[bi, minimum width=12mm] at (0.8,1.15) {i};
    \node[bj, minimum width=12mm] at (0.8,0.65) {j};
  \end{scope}
\end{tikzpicture}
$$

$Overlap$ is asymmetric here: $Overlap(i,j)$ holds only if $i$ begins before $j$.
With these relations we can say the reign of Elizabeth II immediately followed that
of George VI, $Meets(ReignOf(GeorgeVI), ReignOf(ElizabethII))$, and that the reign
of Elvis overlapped the 1950s.

What makes the seven relations a usable calculus rather than a list is
**composition**: given how $i$ relates to $j$ and how $j$ relates to $k$, the
possible relations between $i$ and $k$ are fixed, and the reasoner can chain
constraints without ever looking at numerical endpoints. Some compositions pin the
result to a single relation. If $Meets(i, j)$ and $Meets(j, k)$, then the end of $i$
is the start of $j$ and the end of $j$ is the start of $k$, so $i$ finishes strictly
before $k$ starts: $Before(i, k)$, and nothing else is possible. Chaining
$Before(i, j)$ with $Before(j, k)$ likewise forces $Before(i, k)$ — the relation is
transitive. Other compositions leave a disjunction. If $Before(i, j)$ and
$Meets(j, k)$, then $i$ ends before $j$ starts and $j$ ends where $k$ starts, which
still puts all of $i$ before $k$: again $Before(i, k)$. But composing $Overlap(i, j)$
with $During(j, k)$ leaves several possibilities — $i$ might overlap $k$, start it,
or sit during it — and the entry in the composition table is a set of relations, not
one.

$$
% caption: Reading the interval composition table. Given Meets(i,j) and Meets(j,k),
% the transitive chain forces Before(i,k): i ends where j starts, j ends where k
% starts, so i lies strictly before k with no other relation possible.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  bar/.style={draw, minimum height=4.5mm, inner sep=0pt}]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  \node[bar, fill=black!12, minimum width=14mm] (i) at (0,1.9) {i};
  \node[bar, fill=white, minimum width=14mm] (j) at (1.5,1.0) {j};
  \node[bar, fill=black!12, minimum width=14mm] (k) at (3.0,0.1) {k};
  % meeting-point guides
  \draw[acc, dashed] (0.75,2.15) -- (0.75,0.75);
  \draw[red, dashed] (2.25,1.25) -- (2.25,-0.15);
  \node[acc, font=\scriptsize, anchor=south] at (0.75,2.2) {i ends = j starts};
  \node[red, font=\scriptsize, anchor=north] at (2.25,-0.2) {j ends = k starts};
  \node[font=\footnotesize, anchor=west] at (5.0,1.9) {Meets(i,j)};
  \node[font=\footnotesize, anchor=west] at (5.0,1.0) {Meets(j,k)};
  \draw[black] (4.9,0.55) -- (7.6,0.55);
  \node[font=\footnotesize, text=acc, anchor=west] at (5.0,0.1) {gives Before(i,k)};
\end{tikzpicture}
$$

The full table is a 13-by-13 grid (the seven relations here plus the inverses of the
six asymmetric ones), and constraint propagation over it is how interval reasoners
answer questions like whether two events could have coincided given only qualitative
statements about their order.

### Fluents and objects

A physical object can be viewed as a generalized event — a chunk of space-time. The
USA began in 1776 as a union of thirteen states and continues today as a union of
fifty; its changing properties are state fluents like $Population(USA)$. Consider
$President(USA)$. It cannot be a term that denotes a different person at different
times, because a term denotes exactly one object in a model. Instead
$President(USA)$ denotes a single object that _is_ George Washington from 1789 to
1797, John Adams from 1797 to 1801, and so on — the four-dimensional object whose
temporal slices are the successive presidents.

$$
% caption: The object $President(USA)$ across time, as a four-dimensional entity
% whose temporal slices are the successive presidents; each slice is that
% president for the duration of the term.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  slab/.style={draw, fill=black!8, minimum width=13mm, minimum height=18mm}]
  \definecolor{acc}{HTML}{2348F2}
  \node[slab] (w) at (0,0) {Washington};
  \node[slab] (a) at (2.6,0) {Adams};
  \node[slab] (j) at (5.2,0) {Je\/f\/ferson};
  \node[font=\scriptsize, anchor=north] at (0,-1.05) {1789};
  \node[font=\scriptsize, anchor=north] at (2.6,-1.05) {1797};
  \node[font=\scriptsize, anchor=north] at (5.2,-1.05) {1801};
  \draw[->, acc, thick] (-1.2,-1.5) -- (6.6,-1.5);
  \node[acc, font=\footnotesize, anchor=west] at (6.6,-1.5) {time};
  \node[font=\footnotesize, anchor=south] at (2.6,1.05) {President(USA)};
  \draw[black, dashed] (-0.9,0.9) -- (6.1,0.9);
\end{tikzpicture}
$$

To say Washington was president throughout 1790 we write $T(Equals(President(USA),
GeorgeWashington), AD1790)$, using the _function_ $Equals$ rather than the logical
predicate $=$ — because $T$ takes an object, not a truth value, and because the two
are not logically identical (that could never change over time); they are identical
only in their 1790 subevents.

## Mental objects and modal logic

The agents built so far have beliefs and deduce new ones, but none has knowledge
_about_ belief. That is useful for controlling inference: if Alice asks Bob the
square root of 1764 and he says "I don't know," her "think harder" is reasonable
because the answer is derivable; but "think harder" about whether his mother is
sitting down is pointless — better to reason that his mother _knows_ and could be
asked.

We model this with **propositional attitudes** an agent can hold toward a mental
object: $Believes$, $Knows$, $Wants$, $Intends$, $Informs$. These do not behave
like ordinary predicates. Suppose we write $Knows(Lois, CanFly(Superman))$. If
Superman is Clark Kent, then equality reasoning — built into first-order logic —
forces $Knows(Lois, CanFly(Clark))$, which is false: Lois does not know Clark can
fly. The cause is **referential transparency**: in ordinary logic the term used
to name an object does not matter, only the object. For $knows$ and $believes$ the
term _does_ matter — this is **referential opacity**.

**Modal logic** addresses this by adding operators that take _sentences_ as
arguments. "Agent $A$ knows $P$" is written $\mathbf{K}_A P$. The semantics uses a
collection of **possible worlds** connected by **accessibility relations**, one per
modal operator: world $w_1$ is accessible from $w_0$ for agent $A$ if everything in
$w_1$ is consistent with what $A$ knows in $w_0$.

> **Definition (Knowledge in modal logic).** $\mathbf{K}_A P$ is true at world $w$
> exactly when $P$ is true in _every_ world accessible from $w$ for $A$. The agent
> knows $P$ iff $P$ holds in all worlds it considers possible.

$$
% caption: Possible worlds and accessibility. From the actual world $w_0$, agent
% $A$'s accessible worlds are those consistent with what $A$ knows; $A$ knows $P$
% iff $P$ holds in every one of them. A world where $2+2=5$ is accessible to no
% agent.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  w/.style={draw, minimum width=17mm, minimum height=9mm, font=\footnotesize}]
  \definecolor{acc}{HTML}{2348F2}
  \node[w, draw=acc, text=acc] (w0) at (0,0) {w0: actual};
  \node[w] (w1) at (3.4,1.3) {w1: P};
  \node[w] (w2) at (3.4,-1.3) {w2: P};
  \node[w] (w3) at (6.6,0) {w3: P};
  \draw[->, acc, thick] (w0) -- (w1) node[midway, above, font=\scriptsize, text=black] {Acc};
  \draw[->, acc, thick] (w0) -- (w2) node[midway, below, font=\scriptsize, text=black] {Acc};
  \draw[->, acc, thick] (w1) -- (w3);
  \draw[->, acc, thick] (w2) -- (w3);
  \node[font=\scriptsize, align=center, text=black] at (3.3,0) {P holds in\\all accessible\\worlds, so A\\knows P};
\end{tikzpicture}
$$

Because modal sentences nest, we can reason about what one agent knows about
another's knowledge. Even though Lois does not know Superman's secret identity, she
knows that Superman knows it: $\mathbf{K}_{Lois}[\mathbf{K}_{Clark}
Identity(Superman, Clark) \lor \mathbf{K}_{Clark} \lnot Identity(Superman, Clark)]$.
Standard axioms follow: an agent's knowledge is closed under implication,
$(\mathbf{K}_a P \land \mathbf{K}_a(P \Rightarrow Q)) \Rightarrow \mathbf{K}_a Q$;
knowledge implies truth, $\mathbf{K}_a P \Rightarrow P$; and agents can introspect,
$\mathbf{K}_a P \Rightarrow \mathbf{K}_a(\mathbf{K}_a P)$. The remaining weakness is
**logical omniscience**: the possible-worlds model forces an agent that knows some
axioms to know _all_ their consequences, which is implausible for belief. Attempts
to bound rationality to $k$ reasoning steps have been largely unsatisfactory.


## Where this continues

We now have the content of a knowledge base — an ontology, categories, composed
objects, reified events threaded by time, and a modal account of belief. What we
have not built is the _machinery_ that makes such a base practical at scale: how to
organize categories for fast inheritance, how to keep the core inferences tractable,
and how to handle the fact that almost every useful rule holds only by default.

This continues in
[Reasoning Systems and Default Logic](/artificial-intelligence/logic-and-planning/reasoning-systems-and-defaults),
which covers semantic networks and description logics with their subsumption and
classification, default reasoning by circumscription and default logic, and truth
maintenance systems that retract conclusions cleanly when the beliefs beneath them
change.

[^onto]: **AIMA**, Ch. 12 — Knowledge Representation, §12.1 Ontological Engineering: the question of what _content_ to put in a knowledge base, the upper ontology of general concepts, and the four routes by which real ontologies (CYC, DBpedia, TextRunner, OpenMind) were built.
[^event]: **AIMA**, §12.3 Events: event calculus based on time points rather than situations, reifying fluents and events, with the $T$/$Happens$/$Initiates$/$Terminates$/$Clipped$/$Restored$ vocabulary, processes as liquid events, and Allen's interval relations.