Default Reasoning, Nonmonotonic Logic, and Ontologies

The Qualification and Ramification Problems

Qualification problem: it’s impossible to list ALL preconditions of an action. - “The car will start if… battery is charged AND fuel is present AND engine is not seized AND ignition works AND…” - Real-world actions have infinite possible failure modes

Ramification problem: actions have indirect effects. - “If I fill the bathtub with water, the water level rises, the weight on the floor increases, the bathroom becomes humid…” - Impossible to specify all indirect effects

Classical FOL handles neither well — it’s monotonic (adding more facts can only derive more conclusions, never retract existing ones).

Nonmonotonic Logic

In nonmonotonic reasoning, conclusions can be retracted when new information arrives:

Birds typically fly.
Tweety is a bird.
→ Tweety flies (by default)

[Later] Tweety is a penguin.
→ Retract "Tweety flies"

Classical FOL cannot represent “typically” — it’s monotonic.

Default Logic (Reiter, 1980)

A default rule has the form:

α : β / γ

Read: “If α is true and β is consistent with current knowledge, then conclude γ.”

Example: Bird(x) : Flies(x) / Flies(x) — “If x is a bird and it’s consistent that x flies, then conclude x flies.”

When Penguin(Tweety) is added and Flies(Tweety) becomes inconsistent, the default no longer fires.

Circumscription (McCarthy, 1980)

Minimize the extension of a predicate — assume everything is false unless forced to be true.

Abnormality approach:

∀x Bird(x) ∧ ¬Abnormal(x) → Flies(x)

Circumscription minimizes Abnormal — assumes no bird is abnormal unless there’s a specific reason.

Truth Maintenance Systems (TMS)

TMS tracks justifications for beliefs: - If a justification becomes invalid (new contradicting facts), the belief is retracted - Maintains a consistent belief state dynamically

Used in planning and diagnosis systems where beliefs change incrementally.

Internet and Semantic Web Ontologies

OWL (Web Ontology Language)

Based on Description Logic (DL) — a decidable fragment of FOL: - Concepts = unary predicates - Roles = binary predicates - Restricted to: subclass, intersection, union, complement, existential/universal restriction

OWL provides decidable reasoning: - Concept subsumption: is every C1 a C2? - Instance checking: is x an instance of C? - Satisfiability: is C consistent?

RDF/RDFS (Resource Description Framework)

Triple store: (subject, predicate, object)

(John, rdf:type, foaf:Person)
(John, foaf:name, "John Smith")

SPARQL

Query language for RDF — like SQL for triple stores.

CYC: The Large-Scale KB Effort

CYC (Douglas Lenat, 1984–present): attempt to encode all human commonsense knowledge in FOL. - ~1.5 million rules, ~30 million facts - Multiple “microtheories” — contexts where different assumptions hold - Mixed results — impressive coverage, but commonsense reasoning remains hard

Lesson: knowledge engineering at scale is extremely difficult. Neural approaches (language models) implicitly learn commonsense — but without interpretability or formal guarantees.

Relevance to DynamICCL