Reasoning Systems and Default Logic

This builds on Knowledge Representation, which built the content of a knowledge base: an upper ontology, categories and composed objects, events reified through the event calculus, and belief modeled in modal logic. Here we turn to the machinery that makes such a base practical.

Reasoning systems for categories

Categories are the primary building blocks of large-scale knowledge bases, and two families of systems are built specifically to organize and reason with them. Semantic networks give a graphical notation and fast inheritance algorithms; description logics give a formal language for defining and combining categories, with efficient tests for subset and superset relations.

Semantic networks

A semantic network displays objects and categories as nodes and relations as labeled links. A $M e mb er O f$ link from $M a r y$ to $F e ma l e P er so n s$ encodes $M a r y \in F e ma l e P er so n s$ ; a $S i s t er O f$ link between $M a r y$ and $J o hn$ encodes $S i s t er O f (M a r y, J o hn)$ ; $S u b se tO f$ links chain categories upward. Despite an old rivalry between logic and semantic networks, a semantic net with well-defined semantics simply is a form of logic — a more convenient human interface over the same objects, relations, and quantification.

A semantic network with four objects (John, Mary, 1, 2) and four categories. A single-boxed Legs link asserts a property of every member; the double-boxed HasMother link asserts a relation that holds for each member individually. John's own Legs link (value 1) overrides the inherited default 2.

Inheritance runs by following $M e mb er O f$ up to a category, then $S u b se tO f$ links upward until a boxed property link is found. Mary has two legs because $P er so n s$ has a $L e g s$ link with value 2 and $M a r y \in F e ma l e P er so n s \subset P er so n s$ . The simplicity and transparency of this inference — you can see exactly which links the procedure will traverse — is the main attraction over general theorem proving.

Two complications matter. Links are binary, so an $n$ -ary assertion like $F l y (S hank a r, N e w Y or k, N e w D e l hi, Y es t er d a y)$ cannot be drawn directly; the fix is to reify the proposition as an event object with $A g e n t$ , $O r i g in$ , $D es t ina t i o n$ , and $D u r in g$ links — the same reification move from earlier, now forced by the notation. And multiple inheritance, where an object belongs to two categories offering conflicting values, can make the inheritance algorithm find two answers; some object-oriented languages ban it outright, but semantic networks usually allow it and defer the conflict to default reasoning.

Description logics

Description logics formalize what a semantic network means while keeping taxonomic structure central. They are notations designed to make it easy to describe and combine category definitions. The two principal inference tasks are:

A description-logic language such as CLASSIC builds concepts from an algebra of operators on predicates — something first-order logic cannot do. Bachelors are unmarried adult males:

B a c h e l or = A n d (U nma r r i e d, A d u l t, M a l e)

Concepts combine with constructors like $A l l (r o l e, co n ce pt)$ (every filler of a role is in a concept), $A t L e a s t (n, r o l e)$ and $A tM os t (n, r o l e)$ (cardinality bounds, the clean version of the exactly two legs problem), and $F i l l s (r o l e, in d i v i d u a l)$ . Men with at least three unemployed, married sons who all married doctors, and at most two daughters who are all physics-or-math professors:

A n d (M an, A t L e a s t (3, S o n), A tM os t (2, D a ug h t er), A l l (S o n, A n d (U n e m pl oy e d, M a r r i e d, A l l (S p o u se, D oc t or))), \dots)

The point of description logics is tractability. A problem is posed by describing it and asking which of several solution categories subsumes it, and the design goal is that subsumption testing run in time polynomial in the size of the descriptions. The cost is that keeping subsumption tractable usually means giving up general negation and disjunction, which force a first-order system into exponential case analysis. So either hard problems cannot be stated, or they need exponentially large descriptions — but the tractability results at least tell a designer which constructs are expensive.

The subsumption relation over concepts forms a lattice, and classification finds where a new concept fits into it.

A subsumption lattice. Each upward edge means the lower concept is subsumed by (is a subset of) the upper; classifying a new concept means inserting it at the right place, below everything that subsumes it and above everything it subsumes.

The edge from $B a c h e l or$ up to $A d u l tM a l e$ in the lattice is not drawn by hand — a classifier derives it by comparing definitions. Take

B a c h e l or = A n d (U nma r r i e d, A d u l t, M a l e) A d u l tM a l e = A n d (A d u l t, M a l e)

Subsumption between conjunctions has a syntactic test: $A n d (A_{1}, \dots, A_{m})$ is subsumed by $A n d (B_{1}, \dots, B_{n})$ exactly when every conjunct $B_{j}$ on the right is subsumed by some conjunct on the left. To ask whether $B a c h e l or$ is subsumed by $A d u l tM a l e$ , check each conjunct of $A d u l tM a l e$ against the conjuncts of $B a c h e l or$ . The right side's $A d u l t$ matches $B a c h e l or$ 's $A d u l t$ ; the right side's $M a l e$ matches $B a c h e l or$ 's $M a l e$ . Both conjuncts on the right are covered, so $B a c h e l or ⊑ A d u l tM a l e$ — every bachelor is an adult male. The reverse fails: $A d u l tM a l e$ 's definition has no conjunct subsumed by $B a c h e l or$ 's $U nma r r i e d$ , so a married adult male is an adult male but not a bachelor, and $A d u l tM a l e \neq ⊑ B a c h e l or$ . The subsumption is strict, which is why the lattice draws $B a c h e l or$ strictly below $A d u l tM a l e$ .

Classification runs the same test to place an individual. Suppose the knowledge base holds $G eor g e \in A n d (M an, U nma r r i e d, A d u l t)$ , where $M an = A n d (M a l e, A d u l t)$ has already been reduced. Flattening the conjunction gives $A n d (M a l e, A d u l t, U nma r r i e d)$ , which by the same conjunct-matching test is subsumed by $A n d (U nma r r i e d, A d u l t, M a l e) = B a c h e l or$ . The classifier therefore concludes $G eor g e \in B a c h e l or$ without any rule mentioning George — the membership falls out of the definitions. Adding the fact $M a r r i e d (G eor g e)$ later makes $G eor g e \in U nma r r i e d$ unsatisfiable, and a consistency check flags the contradiction rather than silently deriving a false membership.

Description logics matured into OWL, the Web Ontology Language of the Semantic Web, where machine-readable ontologies annotate Web resources and a reasoner classifies and checks them. That is the industrial descendant of the taxonomic tradition running back through semantic networks.

Reasoning with default information

The semantic-net example already leaked a non-classical idea: the assertion all persons have two legs had only default status, overridden for John. In a strictly logical knowledge base that would be a flat contradiction. Handling it properly means giving up monotonicity — the property, from propositional logic, that adding sentences never retracts a conclusion. Commonsense reasoning is routinely nonmonotonic: seeing a parked car you believe it has four wheels though only three are visible, and you retract that only if new evidence (the owner carrying a wheel, the car jacked up) arrives.

Two ideas are the setting for this. The closed-world assumption takes any proposition not entailed by the knowledge base to be false — useful, but crude. Later we prefer the graded alternative of probability, where a belief has a degree rather than a bare default; this section is the logical route to the same problem.

Circumscription and default logic

Circumscription is a sharper closed-world assumption: name particular predicates that are assumed as false as possible — false for every object except those known to make them true. To encode birds fly by default, introduce an abnormality predicate and write:

B i r d (x) \land \neg A bn or ma l_{1} (x) \Rightarrow F l i es (x)

Circumscribing $A bn or ma l_{1}$ lets a reasoner assume $\neg A bn or ma l_{1} (x)$ unless told otherwise, so $F l i es (T w ee t y)$ follows from $B i r d (T w ee t y)$ — but is withdrawn the moment $A bn or ma l_{1} (T w ee t y)$ is asserted. Circumscription is a model preference logic: a sentence is entailed with default status if it holds in all preferred models (here, those with the fewest abnormal objects), rather than in all models.

The classic example is the Nixon diamond: Nixon is a Quaker (so a pacifist by default) and a Republican (so not a pacifist by default).

The Nixon diamond. Nixon inherits pacifism from Quaker and non-pacifism from Republican; the two default paths conflict, and a plain circumscriptive reasoner has two preferred models, staying agnostic about Pacifist(Nixon).

A plain reasoner has two preferred models and stays agnostic about whether Nixon is a pacifist. Prioritized circumscription breaks the tie by minimizing one abnormality predicate ahead of another, letting religious defaults, say, take precedence over political ones.

Default logic takes a different route, with default rules of the form $P : J_{1}, \dots, J_{n} / C$ : given prerequisite $P$ , and if each justification $J_{i}$ is consistent with the knowledge base, conclude $C$ . Birds fly is $B i r d (x) : F l i es (x) / F l i es (x)$ . The Nixon diamond becomes two default rules, one concluding $P a c i f i s t (x)$ and one $\neg P a c i f i s t (x)$ . The meaning of a set of default rules is given by its extensions — maximal consistent sets of conclusions, each a coherent way of applying the defaults. The Nixon diamond has two extensions, one where he is a pacifist and one where he is not.

Open problems remain. If cars have four wheels is a default, what exactly does it mean to hold it in a knowledge base, and what is a good set of default rules — if we cannot decide rule by rule whether one belongs, we have a nonmodularity problem. And using default beliefs to make decisions, weighing the strength of a belief against the cost of a wrong action, is the hardest issue, pushing toward embedding default reasoning inside probability or utility theory.

Truth maintenance systems

Many conclusions in a knowledge base have only default status and will sometimes turn out wrong, so they must be retractable. Retracting is not as simple as deleting. Suppose the base contains $P$ , and $P \Rightarrow Q$ was used to add $Q$ . Naively retracting everything inferred from $P$ removes $Q$ — but $Q$ may have other justifications ( $R$ and $R \Rightarrow Q$ ), so it should survive. A truth maintenance system (TMS) manages exactly these dependencies. This is belief revision: revising the base to reflect new information about a fixed world.

The naive approach numbers sentences $P_{1}, \dots, P_{n}$ by insertion order; to retract $P_{i}$ , undo everything back to just before it and reassert the rest. Correct, but retracting $P_{i}$ costs $n - i$ reassertions and re-derivations — impractical when facts pour in.

A JTMS (justification-based TMS) is smarter: annotate each sentence with a justification, the set of sentences it was inferred from. If $P \Rightarrow Q$ is present and $Tell (P)$ fires, $Q$ is added with justification ${P, P \Rightarrow Q}$ . On $Retract (P)$ , the JTMS deletes exactly those sentences for which $P$ is in every justification. If $Q$ also had justification ${R, R \Rightarrow Q}$ , it survives. Rather than deleting a sentence that loses all justifications, the JTMS marks it out (and in when a justification is restored), so inference chains are kept and need not be rederived.

A JTMS dependency network.

Q

has two independent justifications, so retracting

P

(which removes the left one) leaves

Q

in via the right one; a node goes out only when it loses every justification.

A concrete trace shows what in every justification means. Put five sentences in the base and let the JTMS record the justification set of each derived one:

Sentence	Justification set	Status
$R ain s$	${}$ (premise)	in
$S p r ink l er$	${}$ (premise)	in
$R ain s \Rightarrow W e tG r a ss$	${}$ (premise)	in
$S p r ink l er \Rightarrow W e tG r a ss$	${}$ (premise)	in
$W e tG r a ss$	${R ain s, R ain s \Rightarrow W e tG r a ss}$	in

Firing $S p r ink l er \Rightarrow W e tG r a ss$ adds a second justification for the same node, so $W e tG r a ss$ now carries two:

J_{1} = {R ain s, R ain s \Rightarrow W e tG r a ss} J_{2} = {S p r ink l er, S p r ink l er \Rightarrow W e tG r a ss}

Now call $Retract (R ain s)$ . The JTMS deletes only sentences with $R ain s$ in every justification. $W e tG r a ss$ fails that test: $R ain s \in J_{1}$ but $R ain s \in / J_{2}$ , so $J_{2}$ still supports it and $W e tG r a ss$ stays in, its label narrowed to ${J_{2}}$ . Retract $S p r ink l er$ as well and $J_{2}$ dies too; with no justification left, $W e tG r a ss$ is marked out rather than erased, so if either premise returns the node flips back in with no re-derivation of the implication chains. Compare the naive insertion-order scheme, which on $Retract (R ain s)$ would blindly undo $W e tG r a ss$ and every later sentence and then reassert them one by one.

TMSs also speed up analysis of multiple hypothetical situations. Choosing Olympic sites, a great deal of reasoning follows from $S i t e (A t h l e t i cs, B u c ha r es t)$ ; to consider $S i t e (A t h l e t i cs, S ibi u)$ instead, retract the first, assert the second, and the TMS revises only what depends on the change — inference chains not touching the choice are reused.

An ATMS (assumption-based TMS) goes further. A JTMS represents one state at a time; an ATMS keeps all states considered so far, labeling each sentence not simply in or out but with the set of assumption sets under which it holds. This makes context-switching between hypothetical worlds nearly free. ATMSs also generate explanations: an explanation of $P$ is a set of sentences $E$ that entails $P$ , possibly including assumptions — sentences not known true but which would suffice. For car won't start, an ATMS makes assumptions like battery dead or no gas in any order, then reads off from $P$ 's label which assumption sets would justify it.

The label is the whole mechanism. Designate a set of assumptions ${B a tt er y D e a d, N o G a s, S t a r t er B r o k e n}$ — sentences the reasoner may posit but does not know true. Each derived sentence is labelled with a set of assumption sets, where every member is a minimal collection of assumptions sufficient to derive it. Given the rules $B a tt er y D e a d \Rightarrow W o n tS t a r t$ , $N o G a s \Rightarrow W o n tS t a r t$ , and $S t a r t er B r o k e n \Rightarrow W o n tS t a r t$ , the label of $W o n tS t a r t$ becomes

L (W o n tS t a r t) = {{B a tt er y D e a d}, {N o G a s}, {S t a r t er B r o k e n}}

read as: the car fails to start under any one of these assumptions. A sentence requiring two assumptions at once, say $D im L i g h t s$ needing both a weak battery and lights left on, would carry a label whose member is the two-element set ${B a tt er y D e a d, L i g h t s O n}$ .

An ATMS label. Each derived sentence carries a set of minimal assumption sets; WontStart holds under any one of three single-assumption sets, so its label has three members, while a conclusion needing two assumptions carries a two-element set. Reading the label off gives every diagnosis at once.

Because the label is computed once and updated incrementally as rules fire, the reasoner never re-solves the diagnosis when it switches from considering $B a tt er y D e a d$ to considering $N o G a s$ ; both contexts are already recorded in the label. That is the trade the ATMS makes against the JTMS: more bookkeeping per sentence, but every hypothetical context available at once instead of one at a time.

Truth maintenance is not free — its complexity is at least that of propositional inference, so it is NP-hard. Used carefully, though, a TMS gives a logical system a real increase in its ability to cope with complex environments and hypotheses.

From description logics to OWL and the Semantic Web

The taxonomic tradition described here — semantic networks, then description logics with subsumption and classification — became a deployed standard. The Web Ontology Language (OWL) was published as a W3C recommendation in 2004 and revised as OWL 2 in 2009, and its expressive dialect OWL 2 DL is grounded in a specific description logic. Horrocks, Kutz, and Sattler, in The Even More Irresistible SROIQ (KR 2006), defined that logic, $S R O I Q$ , by extending an earlier one with complex role-inclusion axioms, qualified number restrictions, and reflexive and irreflexive roles, and gave a tableau reasoning procedure for it; their paper is the logical basis W3C adopted for OWL 2. The constructors are the same $A l l$ , $A t L e a s t$ , $A tM os t$ , and $F i l l s$ this lesson used, formalized to the point of a decidability proof.

The line from this lesson's machinery to deployed standards. Semantic networks and description logics feed the SROIQ logic behind OWL 2; tableau reasoners such as HermiT decide subsumption and classification over ontologies; knowledge graphs like Wikidata supply the facts at Web scale.

Deciding subsumption over such a logic needs an actual reasoner. HermiT, described by Glimm, Horrocks, Motik, Stoilos, and Wang in the Journal of Automated Reasoning (2014), is an OWL 2 reasoner built on a hypertableau calculus; it performs classification, entailment checking, and consistency testing over OWL ontologies and is compliant with the OWL 2 direct semantics standardized by the W3C. It is the industrial version of the subsumption and consistency tests this lesson stated abstractly.

The other modern current is the large curated store of facts. Wikidata, described by Vrandečić and Krötzsch in Communications of the ACM (2014), is a free, collaboratively edited knowledge base built to hold the structured, multilingual factual data behind Wikipedia; it represents facts as items with property-value statements, a reification of the same object-relation structure this lesson began with. Earlier, Miller's WordNet (Communications of the ACM, 1995) organized English nouns, verbs, adjectives, and adverbs into synonym sets linked by hyponym and other lexical relations — a hand-built taxonomy of word senses that became a standard resource in language processing. Between the reasoners and the fact stores, the two halves of this subject — the machinery here and the content of the previous lesson — each have a deployed descendant.

Where this sits

First-order logic supplies the language; these two lessons cover using it well at scale. An ontology fixes the top-level categories; reification turns categories, propositions, and events into objects you can quantify over and pin facts to; the event calculus threads time and change through the whole thing; modal logic represents agents' beliefs. On top of that content, description logics keep subsumption tractable, and default reasoning with a truth maintenance system lets conclusions be held tentatively and withdrawn cleanly when the beliefs beneath them change.

The recurring problem across all of it is exceptions — most useful rules hold only by default. The logical treatments here (circumscription, default logic, TMSs) buy retractability but not degree: they cannot say a car has four wheels with probability $0.99$ . That graded account is the alternative developed under uncertainty, where the same commonsense inferences reappear as conditioning on evidence rather than overriding a default.