Knowledge Representation Reasoning

Knowledge representation and reasoning (KR) is the branch of artificial intelligence that asks how a machine can be given a body of knowledge—facts, rules, categories, uncertainties—in a form it can use to draw conclusions, answer questions, and justify its answers.

11 frameworks, from 1958 to today · Artificial Intelligence · Computer Science

still a working view ended · each leads to its entry below

Overview

Knowledge representation and reasoning (KR) is the branch of artificial intelligence that asks how a machine can be given a body of knowledge—facts, rules, categories, uncertainties—in a form it can use to draw conclusions, answer questions, and justify its answers1. What is at stake is the difference between a program that merely computes and one that knows something: that can be told a new fact and infer what follows, that can explain why a conclusion holds, and that can notice when its beliefs conflict. For decades KR was the intellectual core of "good old-fashioned AI," and its ideas—frames, semantic networks, description logics, ontologies, non-monotonic inference—now sit quietly inside databases, the web, and the knowledge graphs behind search engines and question-answering systems.

Logic as the first language of thought

The earliest and most durable idea was that knowledge should be written as formal logic. In the 1950s and 1960s, researchers building theorem provers and question-answering systems treated first-order logic as a universal representation: facts as predicates, general knowledge as quantified formulas, and reasoning as deduction. John McCarthy's 1959 paper "Programs with Common Sense" proposed that a program could be given everyday knowledge as logical axioms and use a reasoning engine to answer questions—an agenda that shaped the field for decades. Around the same time, Allen Newell and Herbert Simon's Logic Theorist and General Problem Solver demonstrated machine reasoning on symbolic expressions, and John Alan Robinson's 1965 resolution principle gave a single, complete inference rule for first-order logic, making automated deduction practical enough to build on.

Logic had real strengths: it was precise, compositional, and its conclusions were guaranteed sound. Its weakness was equally clear. Human knowledge is rarely a tidy set of universally true axioms. It is full of defaults ("birds fly"), exceptions, and context-dependent facts, and classical logic has no native way to revise a belief when new information arrives. That gap drove the next several waves.

Semantic networks and frames: knowledge as structure

In the late 1960s and 1970s, psychologists and AI researchers converged on the idea that knowledge is organized as a network of concepts linked by relations. Ross Quillian's 1968 semantic network model, built to represent word meanings and model human memory, stored concepts as nodes and associations as labeled edges, with meaning emerging from the pattern of connections. Semantic networks made inheritance natural: a canary is a bird, a bird has wings, so a canary has wings—traced by following links rather than by formal proof.

Marvin Minsky's 1974 essay "A Framework for Representing Knowledge" pushed this further with frames: structured records for stereotyped situations, with slots for attributes and default values that could be overridden. A frame for a "birthday party" would carry default expectations—cake, guests, gifts—that a particular party could override. Frames and their relatives, scripts (Roger Schank and Robert Abelson's 1977 structures for routine events like dining in a restaurant), captured the intuition that much of human knowledge is packaged, default-laden, and expectation-driven.

These representations were expressive and psychologically plausible, but they had a notorious problem: no agreed semantics. What exactly did a link mean? Did inheritance permit exceptions? Different systems gave different answers, and the same network could be read in incompatible ways. This ambiguity set up the field's central methodological turn.

Description logics: giving structure a formal meaning

The response was to rebuild structured representations on rigorous logical foundations. Beginning in the mid-1980s, work on description logics (originally called terminological logics or concept languages) defined a family of formal languages in which concepts are built from atomic ones using constructors—conjunction, roles (relations), existential and universal restrictions, number restrictions—with a model-theoretic semantics. The KL-ONE system, developed by Ronald Brachman and colleagues at BBN in the late 1970s and early 1980s, was the landmark early system; the later CLASSIC and LOOM systems and the DL family (ALC, SHIQ, and successors) gave the approach precision and, crucially, decidable reasoning. The trade-off was explicit: restrict expressiveness so that key reasoning tasks—is concept A subsumed by concept B? is this knowledge base consistent?—remain computable2. Description logics became the theoretical backbone of later ontology languages2.

Rules and expert systems: knowledge that earns its keep

In parallel, the 1970s and 1980s brought the most commercially successful phase of KR: rule-based expert systems. Edward Feigenbaum and colleagues' DENDRAL (from the mid-1960s) and later MYCIN (developed at Stanford in the 1970s for diagnosing blood infections) encoded specialist knowledge as hundreds of if–then rules with confidence factors, separated from a general inference engine. The architecture—a knowledge base plus a reasoning engine—was the field's signature contribution, and it spread into industry: XCON configured computer orders at Digital Equipment Corporation, and by the mid-1980s expert-system shells were a commercial boom.

The boom exposed limits. Rules were brittle at their edges, hard to maintain as they multiplied, and unable to reason gracefully with uncertainty or with knowledge that was incomplete or inconsistent. The crash of the expert-system market in the late 1980s was a formative disappointment, and it pushed the field in two directions: toward more principled treatments of uncertainty and non-deductive inference, and toward more rigorous, reusable knowledge structures3.

Reasoning that can change its mind: non-monotonic logic

Classical logic is monotonic: adding premises never invalidates a previous conclusion4. Everyday reasoning is not like that—learning that Tweety is a penguin should retract the conclusion that Tweety flies5. From the late 1970s, a cluster of formalisms addressed this. John McCarthy's 1980 circumscription formalized the assumption that the objects one can prove to exist are all the objects there are. Raymond Reiter's 1980 default logic added rules of the form "if X is consistent with what is known, conclude Y." Robert Moore's autoepistemic logic (1985) reasoned about what an agent does and does not know. Drew McDermott and Jon Doyle's 1980 truth maintenance systems tackled the bookkeeping problem: how to track which beliefs depend on which, and retract the consequences of a retracted belief. These formalisms made precise the intuition behind frames and semantic networks, and they remain the standard account of defeasible reasoning.

Uncertainty and the probabilistic turn

Expert systems had handled uncertainty with ad hoc certainty factors. A more principled alternative arrived with probabilistic graphical models: Bayesian networks, introduced by Judea Pearl in the 1980s (his 1988 book Probabilistic Reasoning in Intelligent Systems is the landmark), represent a set of variables and their conditional dependencies as a directed acyclic graph, allowing compact encoding of joint probability distributions and efficient inference. Markov networks and, later, factor graphs extended the family. This work moved uncertainty from a patch on symbolic reasoning to a first-class representational framework, and it seeded the neighboring field of probabilistic AI. Its relationship to logic—how to combine probabilistic and logical knowledge—remains an active question.

Ontologies and the Semantic Web

The 1990s and 2000s saw KR scale up from single systems to shared, machine-readable vocabularies. The ontology movement, drawing on philosophy's term for a theory of what exists, aimed at explicit, formal specifications of the concepts in a domain. The DARPA-funded CYC project, begun by Doug Lenat in 1984, was an early large-scale attempt to encode common-sense knowledge. The Semantic Web initiative, articulated by Tim Berners-Lee and colleagues around 2001, proposed annotating web content with machine-interpretable meaning6. Its language stack—RDF for facts as subject–predicate–object triples, OWL for ontologies (built on description logics), and SPARQL for querying—standardized the field's vocabulary. OWL's design directly inherited the description-logic tradition, and its decidable fragments made automated reasoning over web-scale ontologies feasible in principle.

Answer set programming and constraint formalisms

Another strand made logic computational in a different way. Answer set programming (ASP), grounded in the stable-model semantics that Michael Gelfond and Vladimir Lifschitz defined in 1988, treats a logic program as a specification of the sets of beliefs ("answer sets") that satisfy it. By the late 1990s and 2000s, efficient solvers made ASP a practical tool for combinatorial search and non-monotonic reasoning, and it now competes with—and sometimes complements—constraint satisfaction and SAT-based methods. These formalisms share a conviction: declarative knowledge should be stated as what must hold, with the engine finding how.

Knowledge graphs and the return of structure at scale

In the 2010s, the semantic-network idea returned under a new name. Google's 2012 announcement of its Knowledge Graph—a large store of entities and relations used to enrich search results—popularized the term, though large entity-relation stores had been built earlier (Freebase, launched in 2007, and DBpedia, extracted from Wikipedia from 2007)7. Knowledge graphs combine graph structure, ontologies, and often probabilistic or embedding-based methods, and they now underpin search, recommendation, and question answering. Their rise reflects a pragmatic synthesis: the field's old structural intuitions, made operational at industrial scale.

Neuro-symbolic integration and the present

The most recent turn confronts a tension that has run through the whole history. Connectionist systems—neural networks, and since the 2010s large language models—learn patterns from data with impressive flexibility but opaque, hard-to-audit reasoning. Symbolic KR offers explicit, verifiable knowledge but is brittle and expensive to author. Neuro-symbolic integration seeks combinations: neural networks that learn representations, paired with symbolic reasoners that enforce constraints, support explanation, or supply background knowledge8. The idea is old—attempts to marry the two date back decades—but it gained urgency as deep learning spread. Today the field's main approaches coexist: description logics and OWL for ontologies, ASP and SAT for declarative problem-solving, probabilistic graphical models for uncertainty, knowledge graphs for large-scale structured data, and hybrid neuro-symbolic systems for combining learning with reasoning. The open questions are the old ones in new dress: how to represent common-sense knowledge at scale, how to reason with inconsistency and uncertainty together, how to make a system's conclusions explainable, and how to let learned and hand-authored knowledge correct each other.

References

  1. Knowledge representation and reasoning (introduction, Overview), Wikipedia
  2. Description logic, Wikipedia
  3. Symbolic artificial intelligence, Wikipedia
  4. Non-monotonic logic, Wikipedia
  5. Default logic, Wikipedia
  6. Semantic Web (History), Wikipedia
  7. Knowledge graph (History), Wikipedia
  8. Neuro-symbolic AI, Wikipedia

The frameworks of Knowledge Representation Reasoning

Each framework is a way of working the field has used: when it held, and the question it answers.

  1. 1958-1990

    Logic-Based Knowledge Representation

    How can knowledge be written as formal logic?

    Fly to its tower in Nousfarer

  2. 1968-1988

    Semantic Networks and Frames

    How is knowledge organized as linked concepts?

    Fly to its tower in Nousfarer

  3. 1970-1990

    Rule-Based Expert Systems

    How can rules capture expert knowledge?

    Fly to its tower in Nousfarer

  4. 1978-Present

    Non-Monotonic Logic

    How can reasoning retract beliefs when facts change?

    Fly to its tower in Nousfarer

  5. 1985-Present

    Description logic

    How can structured concepts be given precise meaning?

    About Description logic
    Description Logics (DLs) emerged in the mid-1980s to solve a persistent tension in knowledge representation: how to combine the expressive power of logic-based formalisms with the intuitive, hierarchical structure of frame-based and semantic-network systems, while keeping core reasoning tasks computationally tractable. The central problem was that earlier frame-based and network approaches lacked a clear, formal semantics, making it impossible to guarantee that a reasoner would draw correct conclusions. Pure first-order logic, while semantically rigorous, was undecidable for many practically useful fragments. Description Logics addressed this by defining a family of languages that sit between propositional logic and first-order logic in expressiveness, but whose key inference problems—such as checking whether a concept is satisfiable or whether one concept subsumes another—are decidable and can be implemented with efficient algorithms. The framework's distinctive contribution was to treat the terminological knowledge of an application domain (the concepts and their relationships) as a formal theory, separate from assertional knowledge about specific individuals, and to provide sound and complete reasoning services over that theory.
    A first course in Description Logics typically builds from the following core ideas. The fundamental building blocks are concepts (unary predicates, like "Person" or "HappyParent"), roles (binary predicates, like "hasChild"), and individuals (constants, like "Alice"). These are combined using constructors to form complex descriptions; the set of allowed constructors defines a specific DL language. The simplest language, AL\mathcal{AL} (Attributive Language), allows atomic negation, concept intersection, universal restrictions (∀R.C\forall R.C), and limited existential quantification (∃R.⊤\exists R.\top). More expressive languages add constructors like full existential quantification (∃R.C\exists R.C), role hierarchies, number restrictions (e.g., ≥nR\geq n R), and nominals (singleton classes). The knowledge base in DLs has two components: the TBox (terminological box) contains axioms that define the vocabulary of the domain, such as concept inclusions (C⊑DC \sqsubseteq D, meaning every instance of CC is also an instance of DD) and equivalences (C≡DC \equiv D). The ABox (assertional box) contains assertions about individuals, such as concept memberships (a:Ca : C) and role relationships ((a,b):R(a,b) : R). The central reasoning tasks include subsumption (checking whether one concept is more general than another), satisfiability (checking whether a concept can have any instances), classification (computing the full subsumption hierarchy of all named concepts in a TBox), and instance checking (determining whether an individual belongs to a given concept). These tasks are typically performed by a semantic reasoner, which uses tableau-based algorithms to explore possible models. The trade-off between expressivity and complexity is a defining theme: adding more constructors makes the language more useful for modeling but can increase the computational complexity of reasoning, sometimes from polynomial time to exponential or even NEXPTIME-complete. The Web Ontology Language (OWL) and its profiles (OWL 2 EL, OWL 2 QL, OWL 2 RL) are direct descendants of DLs, designed to support the Semantic Web by providing a standardized, DL-based ontology language with different computational guarantees.
    The intellectual history of Description Logics begins in the early 1980s, as researchers in knowledge representation grew frustrated with the lack of formal semantics in Semantic Networks and Frame-Based Representation. The term "description logic" was coined during this period, replacing earlier labels like "terminological systems" and "concept languages." The key figures who shaped the framework in its local dominance window (1985–2026) include Ronald J. Brachman, who with Hector J. Levesque and Raymond Reiter laid the foundations for the field. Brachman and Levesque's 1984 paper "The Tractability of Subsumption in Frame-Based Description Languages" is a seminal work that explicitly addressed the computational complexity of reasoning in structured representations. Francesco M. Donini, Maurizio Lenzerini, Daniele Nardi, and Werner Nutt were central to systematizing the family of DL languages and their complexity results in the late 1980s and early 1990s. Franz Baader and Ulrike Sattler later contributed foundational work on tableau-based reasoning algorithms and the development of the SHOIQ\mathcal{SHOIQ} family of languages that underpin OWL. The framework's relationship with its peers is instructive: it absorbed the structural intuition of Frame-Based Representation and Semantic Networks but replaced their informal semantics with a logic-based foundation. It coexisted with Logic Programming and Rule-Based Knowledge Systems, but distinguished itself by focusing on terminological reasoning rather than rule-based inference. It provided a formal backbone for Ontologies, which emerged as a separate framework around 1993. The successor framework, Probabilistic Knowledge Representation, began to extend DLs with probabilistic uncertainty around 1988, but DLs themselves remain a vibrant area of research and application, especially in biomedical informatics and the Semantic Web.
    The 13 concepts its tower teaches
    • ABox
    • Classification
    • Concepts
    • Constructors
    • Expressivity vs. Complexity
    • Individuals
    • Instance Checking
    • Roles
    • Satisfiability
    • Semantic Reasoner
    • Subsumption
    • TBox
    • Web Ontology Language (OWL)

    Fly to its tower in Nousfarer

  6. 1985-Present

    Graphical model

    How can uncertainty be represented and reasoned with?

    Fly to its tower in Nousfarer

  7. 1990-Present

    Neuro-symbolic AI

    How can learning and symbolic reasoning be combined?

    Fly to its tower in Nousfarer

  8. 1995-Present

    Answer Set Programming

    How can a logic program specify sets of beliefs?

    Fly to its tower in Nousfarer

  9. 1995-Present

    Ontologies and the Semantic Web

    How can shared vocabularies make web content machine-readable?

    Fly to its tower in Nousfarer

  10. 1999-Present

    Answer Set Programming and Constraint Formalisms

    How can logical rules and constraints be solved together?

    Fly to its tower in Nousfarer

  11. 2007-Present

    Knowledge graph

    How can entities and relations be stored at scale?

    Fly to its tower in Nousfarer

How the ideas connect

Each arrow runs from an earlier idea to the later one it shaped. The list below says what passed between them.

Logic-Based Knowledge RepresentationSemantic Networks and FramesRule-Based Expert SystemsNon-Monotonic LogicDescription logicGraphical modelNeuro-symbolic AIAnswer Set ProgrammingOntologies and the Semantic WebAnswer Set Programming and Constraint…Knowledge graph

Beyond the field

Where Knowledge Representation Reasoning's ideas came from in other fields, and what they led to there: the strongest 12 of 42 links.

A city in Nousfarer: a red-carpeted stair climbing terraces to a crowned tower on an acropolis, more towers round it, forest and snowy mountains beyond.
A city in Nousfarer, the game played in the browser.

Knowledge Representation Reasoning is a planet in Nousfarer

Its city has a tower for each of these 11 frameworks. Land, walk in, and climb one concept at a time.

Land on Knowledge Representation Reasoning

Related fields

Fields its ideas are linked to

More in Artificial Intelligence

See where Knowledge Representation Reasoning sits on the Map of Human Knowledge