Knowledge Representation

First-order logic settles the syntax of a knowledge base: objects, relations, functions, quantifiers, and the inference 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.¹

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.

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.

Categories and objects

Most reasoning happens at the level of categories, not individuals. A shopper wants a basketball, not the particular ball $B{B}_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.

First-order logic states many kinds of category fact cleanly. An object is a member: $B{B}_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.

Categories can also be defined by necessary and sufficient conditions rather than merely described: $x\in Bachelors\leftrightarrow Unmarried(x)\wedge x\in Adults\wedge 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:

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 $Appl{e}_1,Appl{e}_2,Appl{e}_3$, then $BunchOf(\{Appl{e}_1,Appl{e}_2,Appl{e}_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{\$}(1)$ is not a dollar bill — there is exactly one object named $\text{\$}(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 $<$:

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 — $Butte{r}_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:

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 $Butte{r}_3$ with density $0.911$ grams per cubic centimeter, weight $250$ grams, and temperature $18$ degrees Celsius, and cut it in half.

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\wedge 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 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 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\wedge Flyer(E_1,Shankar)\wedge Origin(E_1,SF)\wedge 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:

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:

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)\leftrightarrow e=Start$ and $Terminates(e,HaveArrow(a),t)\leftrightarrow 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$:

Each conjunct discharges. The first is the initial-state event. The second follows from $Initiates(e,HaveArrow(a),t)\leftrightarrow 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

Now let the agent shoot at $t=5$: $Happens(Shoo{t}_5,(5,5))$ with $Shoo{t}_5\in Shootings(Agent)$. By the termination axiom, $Terminates(Shoo{t}_5,HaveArrow(Agent),5)$, and any attempt to prove $T(HaveArrow(Agent),6)$ now fails at the third conjunct, because $Shoo{t}_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:

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.

$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.

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.

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$.

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)\vee {\mathbf{K}}_{Clark}\neg Identity(Superman,Clark)]$. Standard axioms follow: an agent's knowledge is closed under implication, $({\mathbf{K}}_{a}P\wedge {\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, 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.