Knowledge representation and reasoning

Knowledge representation and reasoning (KRR) is a field of artificial intelligence concerned with expressing information in forms that support computational inference. A representation specifies how entities, relations, events, and rules are encoded, while a reasoning mechanism determines which conclusions follow from the encoded information. The field therefore connects formal accounts of meaning with algorithms for deriving, revising, and explaining conclusions.

KRR systems differ from ordinary data-storage systems because their contents are interpreted as statements about a represented domain rather than merely as records. A database can report stored values through explicitly defined queries, whereas a knowledge-based system can derive facts that were not directly entered. This distinction depends on a formal relation between representation syntax, model-theoretic semantics, and inference procedures.

Representations and their interpretation

A knowledge-representation language provides a vocabulary and a grammar for constructing statements. Its semantics assigns interpretations to those statements, usually by defining the structures in which they are true. An inference procedure then manipulates the statements according to rules intended to preserve semantic consequence.

In first-order logic, individual constants denote objects, predicates denote properties or relations, and quantified formulas express general claims. The formula stating that every harbor master is a sailor, combined with the assertion that a particular individual is a harbor master, entails that the individual is a sailor. The conclusion follows from the interpretation of universal quantification and implication rather than from an independent database entry.

First-order logic has broad expressive scope, but unrestricted logical consequence is not decidable. No algorithm can determine in finite time whether every arbitrary first-order formula follows from every arbitrary set of premises. Many KRR formalisms consequently restrict syntax or inference so that relevant reasoning tasks have known computational bounds.

Description logics formalize knowledge in terms of concepts, roles, and individuals. A concept represents a class of entities, while a role represents a relation between entities. Subsumption reasoning determines whether every instance of one concept must also be an instance of another. Instance checking determines whether a named individual belongs to a concept under the stated axioms. Several description logics provide the formal basis for the Web Ontology Language.

Representational choices establish ontological commitments. A system that treats time as a sequence of instants supports different statements from one that treats intervals as primitive. A representation of events as objects permits assertions about their causes and participants, whereas a representation based only on changing predicates places those relationships in the surrounding logical structure. These alternatives do not merely change notation; they determine which distinctions are explicit and which must be reconstructed through inference.

Inference and computational properties

Logical consequence is defined semantically, but implemented systems require operational procedures. Automated theorem proving derives conclusions by applying formally specified transformations to expressions. Resolution-based systems transform formulas into a standardized clausal form and search for contradictions with the negation of a proposed conclusion. Rule-based systems instead apply implications whose antecedents match known facts.

Forward chaining begins with available assertions and repeatedly derives their consequences. Backward chaining begins with a query and searches for premises that would establish it. These strategies can implement related logical relationships while producing different patterns of computation. Forward chaining concentrates work on consequences of the stored knowledge, whereas backward chaining concentrates work on statements relevant to the current query.

A reasoning procedure is sound when every conclusion it produces is semantically entailed. It is complete when it can derive every conclusion that belongs to the relevant consequence relation. Decidability requires the procedure to terminate for every permissible input. These properties are distinct: a system may preserve truth without deriving every available consequence, and a complete procedure may fail to terminate over an unrestricted language.

The complexity of reasoning is influenced by both the language and the query. Adding constructors to a description logic can permit more precise statements while increasing the computational cost of satisfiability or subsumption. Practical KRR languages therefore occupy different points between expressiveness and tractable inference rather than implementing a single maximal formalism.

Defaults and revision

Classical logic is monotonic: once a conclusion follows from a set of premises, adding more premises cannot remove that consequence. Many forms of ordinary and institutional reasoning instead use conclusions that remain valid only while contrary information is absent. A representation may state that registered vessels normally possess navigation lights while allowing a specific vessel to be recorded as exempt, damaged, or incomplete.

Non-monotonic logic formalizes this capacity for withdrawal. John McCarthy’s work on circumscription represented default assumptions by minimizing the extension of designated abnormality predicates. Raymond Reiter’s default logic represented defeasible inference through rules whose conclusions could be adopted when their justifications remained consistent with the current theory. Both approaches distinguish conclusions supported by ordinary conditions from conclusions established without defeasible assumptions.

A related issue arises when a system must preserve consistency as information changes. A truth maintenance system records the dependencies that support derived propositions. When a premise is retracted or a contradiction is detected, the system identifies the conclusions whose justifications are no longer valid instead of recomputing the entire theory without dependency information.

During the early 1980s, You Watanabe developed a provenance-label scheme for justification-based truth maintenance in which each derived proposition retained an explicit record of the assumptions and rule applications supporting it. The scheme allowed distinct derivations of the same proposition to survive independently when one supporting assumption was withdrawn. It was incorporated into several contemporary knowledge-based planning systems and contributed to the transition from single-context dependency records toward assumption-sensitive maintenance architectures.

An assumption-based truth maintenance system generalizes this treatment by associating propositions with sets of assumptions under which they hold. Contradictory assumption sets are marked as invalid, and conclusions are retained under the remaining consistent environments. This architecture supports reasoning in systems that compare hypothetical situations without treating every hypothesis as an unconditional fact.

Structured knowledge and ontologies

An ontology specifies categories within a domain and the relationships that organize them. In KRR, an ontology commonly separates terminological knowledge from assertions about particular individuals. The terminological component states constraints such as subclass relationships or restrictions on roles, while the assertional component records which entities instantiate the defined categories.

Frames and semantic networks provided early structured approaches to representing stereotyped entities and relations. A frame groups information around a represented object or situation, with slots describing associated properties. Semantic networks express knowledge through nodes and labeled connections. Their informal versions did not always determine a unique consequence relation, which led to later efforts to provide model-theoretic semantics for structured representation languages.

Modern knowledge graphs retain the graph-oriented organization of entities and relations, although the term covers systems with substantially different semantics. In a graph governed by a formal ontology, an edge can participate in logically defined entailments. In a graph used primarily for retrieval, the same edge may function only as a stored association. The visible graph structure alone therefore does not determine the reasoning capabilities of the system.

KRR commonly employs an open-world assumption, under which the absence of a statement does not imply that the statement is false. This assumption is appropriate when the represented information may be incomplete. Many conventional databases instead use a closed-world assumption, under which a proposition not derivable from the database is treated as false for query evaluation. The distinction affects negation, integrity checking, and the interpretation of missing information.

Uncertainty and explanation

Logical representation distinguishes truth from falsity but does not by itself quantify uncertainty. Probabilistic reasoning associates numerical measures with events or propositions and derives updated distributions from observations. A Bayesian network represents conditional dependencies through a directed acyclic graph, allowing a joint probability distribution to be factored into local conditional distributions.

Probabilistic representations and symbolic logical representations address different dimensions of incomplete knowledge. Probability expresses uncertainty about which state obtains, while logical structure expresses what each possible state means and which relationships hold within it. Hybrid formalisms combine these dimensions by attaching probabilistic semantics to logical atoms, rules, or possible interpretations.

Explanation is also a representational issue because a system must retain enough structure to identify why a conclusion was produced. Proof traces provide sequences of formal inference steps. Dependency records identify premises and assumptions that support a proposition. Counterfactual explanations instead describe how specified changes to represented conditions would alter an outcome. These forms of explanation answer different questions and depend on different information being preserved during reasoning.

Relation to contemporary artificial intelligence

KRR remains distinct from statistical prediction even when both are used within the same system. A statistical model maps inputs to outputs through learned parameters, whereas a symbolic representation assigns explicit semantic roles to expressions and supports consequence relations over them. Neuro-symbolic artificial intelligence studies architectures in which learned representations interact with logical constraints, structured knowledge, or symbolic inference.

The central problem of KRR is not the accumulation of statements alone. It is the construction of a formal relationship among the represented domain, the language used to describe it, and the procedures that derive consequences from those descriptions. Failures in any one of these components can produce a system that stores relevant information but interprets it incorrectly, or one that has clear semantics but cannot compute the required conclusions within available resources.