- Atlas
- Computer Science
- Knowledge Representation Reasoning
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
- Logic-Based Knowledge Representation 1958-1990
- Semantic Networks and Frames 1968-1988
- Rule-Based Expert Systems 1970-1990
- Non-Monotonic Logic 1978-Present
- Description logic 1985-Present
- Graphical model 1985-Present
- Neuro-symbolic AI 1990-Present
- Answer Set Programming 1995-Present
- Ontologies and the Semantic Web 1995-Present
- Answer Set Programming and Constraint Formalisms 1999-Present
- Knowledge graph 2007-Present
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
- Knowledge representation and reasoning (introduction, Overview), Wikipedia
- Description logic, Wikipedia
- Symbolic artificial intelligence, Wikipedia
- Non-monotonic logic, Wikipedia
- Default logic, Wikipedia
- Semantic Web (History), Wikipedia
- Knowledge graph (History), Wikipedia
- 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.
- 1958-1990
Logic-Based Knowledge Representation
How can knowledge be written as formal logic?
- 1968-1988
Semantic Networks and Frames
How is knowledge organized as linked concepts?
- 1970-1990
- 1978-Present
Non-Monotonic Logic
How can reasoning retract beliefs when facts change?
- 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, (Attributive Language), allows atomic negation, concept intersection, universal restrictions (), and limited existential quantification (). More expressive languages add constructors like full existential quantification (), role hierarchies, number restrictions (e.g., ), 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 (, meaning every instance of is also an instance of ) and equivalences (). The ABox (assertional box) contains assertions about individuals, such as concept memberships () and role relationships (). 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 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)
- 1985-Present
- 1990-Present
- 1995-Present
- 1995-Present
Ontologies and the Semantic Web
How can shared vocabularies make web content machine-readable?
- 1999-Present
Answer Set Programming and Constraint Formalisms
How can logical rules and constraints be solved together?
- 2007-Present
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.
Non-Monotonic Logic reacted against Logic-Based Knowledge Representation
Non-monotonic logics arose because classical logic could not retract conclusions when new facts arrived. McCarthy's circumscription and Reiter's default logic were framed explicitly as extensions correcting the monotonicity of first-order logic.
Carried by John McCarthy; Raymond Reiter.
Description logic grew out of Semantic Networks and Frames
Description logics were built to give the structured representations of semantic networks and frames a rigorous model-theoretic semantics. Brachman's KL-ONE work grew directly out of the effort to formalize network links and inheritance.
Carried by Ronald Brachman; KL-ONE.
Answer Set Programming grew out of Non-Monotonic Logic
Answer set programming grew out of the stable-model semantics Gelfond and Lifschitz defined for logic programs with negation, which itself extended non-monotonic reasoning to computational logic programs. ASP is the computational realization of that non-monotonic semantics.
Carried by Michael Gelfond; Vladimir Lifschitz.
Ontologies and the Semantic Web grew out of Description logic
The OWL ontology language of the Semantic Web was built directly on description logics, inheriting their constructors and decidable reasoning. The DL tradition supplied the formal semantics for web ontologies.
Carried by OWL.
Semantic Networks and Frames reacted against Logic-Based Knowledge Representation
Semantic networks and frames were proposed as an alternative to logic-based representation, arguing that human knowledge is structured and default-laden rather than a set of logical axioms. Quillian's network and Minsky's frames defined themselves against the austere predicate-calculus picture.
Carried by Ross Quillian; Marvin Minsky; A Framework for Representing Knowledge (1974).
Graphical model reacted against Rule-Based Expert Systems
Probabilistic graphical models offered a principled treatment of uncertainty in place of the ad hoc certainty factors used in expert systems. Pearl's Bayesian networks were presented as a rigorous alternative to rule-based uncertainty handling.
Carried by Judea Pearl; Probabilistic Reasoning in Intelligent Systems (1988).
Answer Set Programming and Constraint Formalisms grew out of Answer Set Programming
Answer set programming was extended by integrating constraint formalisms, so that constraint satisfaction problems could be solved within the ASP framework. This combined stable-model reasoning with constraint propagation.
Knowledge graph grew out of Ontologies and the Semantic Web
Knowledge graphs carried forward the Semantic Web's triple-based representation of entities and relations, scaled to large linked datasets used by search engines. They inherited RDF-style subject-predicate-object modeling.
Ontologies and the Semantic Web influenced by Logic-Based Knowledge Representation
The Semantic Web's use of formal, machine-interpretable knowledge carried forward the logic-based ambition of encoding knowledge as formal statements a machine can reason over. RDF triples and OWL axioms continue that representational program.
Carried by Tim Berners-Lee.
Neuro-symbolic AI influenced by Rule-Based Expert Systems
Neuro-symbolic AI sought to combine neural learning with symbolic reasoning, partly in response to the brittleness and maintenance problems that sank rule-based expert systems. It aimed to keep symbolic knowledge while adding learned, robust components.
Neuro-symbolic AI influenced by Graphical model
Neuro-symbolic approaches drew on probabilistic graphical models as a bridge between symbolic structure and statistical learning, using graph-structured representations to connect the two. The graphical-model formalism supplied a way to reason under uncertainty alongside symbols.
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.
Logic-Based Knowledge Representation influenced by Formal Foundations of Computation and Logic in Computational Logic
Logic-based KR inherited from the foundational work of Church, Turing, Gödel and others the idea that deductive reasoning can be formalised and mechanised; McCarthy's Advice Taker (1958) proposed representing facts in a formal logical language and computing conclusions from them.
Carried by John McCarthy; Programs with Common Sense (1959).
Rule-Based Expert Systems led to Medical Expert Systems in Clinical Informatics
Rule-based expert system techniques, especially production rules with certainty factors, were taken up in medical consultation programs like MYCIN.
Carried by Edward H. Shortliffe; MYCIN.
Description logic influenced Formal Ontology and Linked Data in Knowledge Organization
Description logic provided the formal semantics underlying OWL, so that linked-data ontologies could be given decidable model-theoretic meaning.
Carried by OWL (2004).
Neuro-symbolic AI influenced by Connectionism in Artificial Intelligence
Connectionist neural networks supply the learning and distributed-representation half of neuro-symbolic systems; the hybrid programme is defined by joining connectionist learning to symbolic reasoning.
Neuro-symbolic AI influenced by Symbolic artificial intelligence in Artificial Intelligence
Neuro-symbolic AI takes the symbolic reasoning machinery of classical symbolic AI (logic-based representation, rules, search) and couples it with neural components; the symbolic half of the hybrid is inherited directly from this tradition.
Answer Set Programming grew out of Logic programming in Programming Paradigms
ASP is a branch of the logic programming paradigm, reusing its rule-based syntax and declarative reading while replacing Prolog's procedural semantics with stable-model semantics.
Answer Set Programming grew out of Logic Programming in Computational Logic
In computational logic, ASP is the answer-set semantics of logic programs made into a computing formalism; it descends from the stable-model and well-founded semantics literature of logic programming.
Carried by Michael Gelfond; Vladimir Lifschitz.
Answer Set Programming grew out of Logic programming in Programming Languages
Answer Set Programming grew directly out of logic programming: stable-model semantics for normal programs, developed in the late 1980s, was turned into a declarative problem-solving paradigm by the mid-1990s.
Carried by Michael Gelfond; Vladimir Lifschitz.
Ontologies and the Semantic Web grew out of Description logic in Computational Logic
OWL was built directly on description logics: its formal semantics and reasoning services derive from DL systems such as SHIQ and from the DL community's decidability results.
Ontologies and the Semantic Web grew out of Knowledge Representation and Ontologies in Computational Logic
The Semantic Web's ontology layer grew directly out of knowledge representation and ontology work in computational logic, including frame-based systems, description logics and the OWL standard built on them.
Answer Set Programming and Constraint Formalisms grew out of Logic Programming in Computational Logic
In computational logic, ASP-and-constraint systems are logic programs extended with constraint domains, descending from the stable-model semantics of logic programming.
Answer Set Programming and Constraint Formalisms grew out of Logic programming in Programming Languages
ASP with constraint formalisms is a direct extension of logic programming: constraint atoms were added to answer-set programs, keeping the stable-model semantics of the parent paradigm.

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 ReasoningRelated fields
Fields its ideas are linked to
- Computational Logic 8 links
- Knowledge Organization 5 links
- Artificial Intelligence 3 links
- Probabilistic Ai 2 links
- Cognitive Science 2 links
- Information Science 2 links
- Logic 2 links
- Programming Languages 2 links
- Programming Paradigms 2 links
- Ai Safety 1 link
- Computer Vision 1 link
- Planning And Search 1 link
More in Artificial Intelligence
- Ai Ethics And Fairness
- Ai Safety
- Artificial Intelligence
- Computer Vision
- Deep Learning
- Evolutionary Computation
- Machine Learning
- Multiagent Systems
- Natural Language Processing
- Planning And Search
- Probabilistic Ai
- Reinforcement Learning
- Speech Recognition And Synthesis
See where Knowledge Representation Reasoning sits on the Map of Human Knowledge