5. Knowledge Representation and Reasoning

Introduction and Context

Artificial intelligence systems do not act intelligently merely because they store data. They must also represent what data means, identify relationships among entities, draw conclusions, and revise conclusions when new evidence appears. Knowledge representation and reasoning (KR&R) addresses this problem. It concerns the languages, structures, and procedures through which an intelligent agent describes the world and uses those descriptions to make decisions.

Knowledge representation differs from ordinary data storage. A database may record that a patient has a temperature of 39°C. A knowledge-based system can represent that the patient has a fever, that fever may be evidence of infection, that some infections require urgent assessment, and that the conclusion is uncertain until additional symptoms are examined. The first statement is a fact; the others involve concepts, rules, relationships, inference, and uncertainty.

KR&R is central to expert systems, intelligent search, language understanding, planning, robotics, recommendation, compliance analysis, and decision support. It also complements machine learning. Machine learning is effective at discovering patterns from examples, whereas symbolic representation makes assumptions, relationships, constraints, and explanations explicit. Contemporary AI increasingly combines both approaches in neuro-symbolic systems.

Learning Objectives

After studying this chapter, students should be able to:

1. Explain the role and characteristics of knowledge representation in intelligent systems.

2. Construct and interpret propositional and first-order predicate logic representations.

3. Distinguish deduction, induction, abduction, and non-monotonic reasoning.

4. Describe rule-based systems, semantic networks, ontologies, and knowledge graphs.

5. Apply Bayesian networks and fuzzy logic to reasoning under uncertainty.

6. Evaluate expert systems in terms of inference, explanation, maintenance, and governance.

7. Identify practical, ethical, technical, and organizational challenges in knowledge-based AI.

What Counts as Knowledge?

Knowledge is structured information that supports interpretation, prediction, explanation, or action. In an AI system, it may include objects, properties, events, procedures, causal relationships, constraints, and degrees of belief. A representation is useful when it is sufficiently expressive to describe the relevant domain, yet sufficiently precise for a computer to manipulate.

Four properties are particularly important. Representational adequacy is the ability to describe the objects and relationships required by a task. Inferential adequacy is the ability to derive new knowledge from existing knowledge. Inferential efficiency concerns whether reasoning can be performed within acceptable computational limits. Acquisitional efficiency concerns how easily knowledge can be added or revised.

A knowledge base normally contains two related elements: a set of explicit assertions and a reasoning mechanism. The assertions may be facts such as “The server is overloaded,” rules such as “If a server is overloaded, response time may increase,” or definitions such as “Every graduate student is a student.” The inference engine applies formal or approximate procedures to these assertions.

Knowledge is often classified as:

• Declarative knowledge: facts and relationships about the world.
• Procedural knowledge: methods or steps for performing a task.
• Structural knowledge: relationships among concepts, such as hierarchy or part–whole structure.
• Heuristic knowledge: experience-based rules that are useful but not guaranteed.
• Meta-knowledge: knowledge about the reliability, source, or applicability of other knowledge.

A major design decision is whether a system should use a general-purpose representation or a domain-specific one. General representations support reuse, while domain-specific models can capture specialist distinctions more efficiently.

Propositional Logic: Reasoning with Complete Statements

Propositional logic represents propositions that are either true or false. Let P mean “The network is available” and Q mean “The application is responsive.” The basic logical connectives are:

• Negation: ¬P, meaning “not P”
• Conjunction: P ∧ Q, meaning “P and Q”
• Disjunction: P ∨ Q, meaning “P or Q”
• Implication: P → Q, meaning “if P, then Q”
• Biconditional: P ↔ Q, meaning “P if and only if Q”

A proposition has a truth value under an interpretation. A compound expression is a tautology if it is true under every interpretation, a contradiction if it is false under every interpretation, and satisfiable if it is true under at least one interpretation.

A knowledge base entails a statement when the statement is true in every model in which the knowledge base is true. This is written KB ⊨ α. Entailment is a semantic concept; it differs from a proof procedure, which is an algorithm used to establish entailment.

Several inference patterns are fundamental. Modus ponens states that from P → Q and P, one may infer Q. Modus tollens states that from P → Q and ¬Q, one may infer ¬P. A common error is affirming the consequent: from P → Q and Q, incorrectly inferring P. The consequence may have several possible causes.

Propositional logic is clear and mathematically manageable, but it cannot naturally express individuals, relations, or quantities. “The database is unavailable” is representable, but “Every analyst who accesses the database must authenticate” requires a richer formalism.

Predicate Logic and the Structure of the World

First-order predicate logic, also called first-order logic (FOL), represents objects and relationships. A predicate expresses a property or relation. For example:

Student(Amina)

means that Amina is a student, while Enrolled(Amina, AI101) means that Amina is enrolled in course AI101. Variables and quantifiers permit general statements:

∀x Student(x) → HasID(x)

This means that every student has an identification record. Existential quantification is written as ∃x, meaning “there exists at least one.” Thus, ∃x Researcher(x) ∧ Uses(x, Robot) states that at least one researcher uses a robot.

The distinction between constants, variables, predicates, functions, and quantifiers is essential. A constant denotes a particular entity; a variable ranges over entities; a predicate denotes a property or relation; and a function maps entities to an entity or value. Predicate logic can represent taxonomies, ownership, spatial relations, temporal relations, and constraints more naturally than propositional logic.

A useful inference method is unification, which finds substitutions that make two expressions identical. The expressions Advises(x, Student) and Advises(Dr_Rao, y) unify with x = Dr_Rao and y = Student. Automated theorem proving may use resolution, in which clauses are transformed into a standard form and complementary literals are combined to derive a contradiction or prove a target.

FOL is expressive, but unrestricted reasoning can be computationally expensive. Moreover, classical logic assumes precise truth values and does not by itself represent uncertainty, default assumptions, time-dependent knowledge, or inconsistent sources.

Rules, Expert Systems, and Inference Strategies

A rule-based system represents knowledge as condition–action or condition–conclusion statements. A typical rule is:

IF a transaction is unusually large AND the account is newly created, THEN flag the transaction for review.

The facts currently known are held in working memory. The inference engine identifies rules whose conditions match those facts and adds conclusions or recommends actions.

In forward chaining, reasoning begins with available facts and repeatedly applies applicable rules until a goal is reached or no new facts can be generated. It is data-driven and useful for monitoring, classification, and event processing. In backward chaining, reasoning begins with a goal and searches for rules that could establish it, recursively seeking their premises. It is goal-driven and common in diagnostic and query-oriented systems.

When several rules are applicable, a conflict-resolution strategy is needed. Possible strategies include preferring more specific rules, using the most recently added facts, assigning priorities, or selecting the rule with the greatest estimated utility. Poor conflict resolution can make system behavior unpredictable.

Expert systems traditionally contain a knowledge base, inference engine, working memory, explanation facility, and user interface. The explanation facility is important because a professional user may need to know not only the recommendation but also which facts and rules produced it. Knowledge acquisition remains difficult: specialists may disagree, use tacit knowledge, or describe exceptions that are not easily formalized.

A rule “If symptom A, then disease B” is not automatically a causal law. It may be a heuristic association, and its reliability may vary with context. Professional systems must therefore distinguish logical implication from empirical evidence.

Semantic Networks, Ontologies, and Knowledge Graphs

A semantic network represents concepts as nodes and relations as labelled links. For example, “sparrow” may be linked to “bird” by an is-a relation, and “bird” to “animal” by another is-a relation. Other links may express part-of, located-in, causes, owned-by, or similar-to relationships. Inheritance allows a system to transfer appropriate properties from a general concept to a specific one.

An ontology is a formal and explicit specification of concepts, categories, relationships, constraints, and sometimes axioms within a domain. It typically distinguishes classes from individuals and specifies properties, domains, ranges, and logical restrictions. In a healthcare ontology, “Medication” may be a class, “prescribedFor” a relation, and “Drug X” an individual. Ontologies support shared vocabulary and interoperability across applications.

A knowledge graph represents entities and their relationships as a graph, often using triples of the form subject–predicate–object. For example:

(University A, offers, Artificial Intelligence)

(Artificial Intelligence, partOf, Computer Science)

Knowledge graphs may integrate structured databases, documents, sensors, and external sources. They support entity linking, semantic search, recommendation, question answering, fraud analysis, and supply-chain visibility. However, graph connectivity does not guarantee truth. Each assertion should have provenance, timestamp, confidence, and, where relevant, information about the source.

Ontologies and knowledge graphs are related but not identical. An ontology provides the conceptual vocabulary and constraints; a knowledge graph uses such vocabulary to describe particular entities and facts. A graph may be useful without a formally complete ontology, while an ontology may exist without a large populated graph.

Reasoning Under Uncertainty

Classical logic is appropriate when statements are crisp and reliable. Real environments are rarely so simple. Sensors are noisy, evidence is incomplete, experts disagree, and the meaning of an observation depends on context. AI systems therefore require models of uncertain belief.

Bayesian Reasoning

Bayesian reasoning updates a prior belief after observing evidence. Bayes’ theorem is:

P(H|E) = [P(E|H)P(H)] / P(E)

Here H is a hypothesis and E is evidence. P(H) is the prior probability, P(E|H) is the likelihood, P(E) is the evidence probability, and P(H|E) is the posterior probability.

A medical screening example illustrates base-rate effects. Even a test with high sensitivity and specificity may produce many false positives when the disease is rare. A responsible system must therefore communicate posterior risk rather than presenting a positive test as certainty.

A Bayesian network is a directed acyclic graph whose nodes represent random variables and whose edges represent conditional dependencies. The graph factorizes a joint distribution:

P(X1, ..., Xn) = ∏ P(Xi | Parents(Xi))

This factorization can greatly reduce the number of probabilities that must be specified. Inference may be exact or approximate. Bayesian networks are useful for diagnosis, risk assessment, fault detection, and predictive maintenance. The graph structure expresses dependency assumptions, but an arrow should not automatically be interpreted as proof of causation.

Fuzzy Logic

Probability represents uncertainty about whether a proposition or event is true. Fuzzy logic represents gradual membership in a concept. A temperature of 30°C may have membership 0.8 in the fuzzy set “hot,” depending on the chosen membership function. This does not mean that the temperature is 80 percent physically hot; it expresses the degree to which it satisfies a linguistic category.

A fuzzy controller commonly includes fuzzification, a rule base, an inference mechanism, and defuzzification. Rules may state: “If temperature is high and occupancy is low, then cooling power is moderate.” Fuzzy logic is valuable when experts can describe control policies linguistically but precise mathematical models are difficult to obtain.

Probability and fuzzy logic should not be confused. Probability concerns uncertainty or frequency; fuzzy membership concerns vagueness or graded applicability. A system may use both, but they answer different questions.

Non-Monotonic and Default Reasoning

In classical monotonic logic, adding premises does not invalidate a conclusion already derived. Everyday reasoning is often non-monotonic. We may infer that a bird flies, then withdraw that conclusion after learning that the bird is a penguin. Default logic, defeasible rules, and truth-maintenance systems support such revision.

Open-world and closed-world assumptions also matter. Under a closed-world assumption, failure to find a fact may be treated as evidence that it is false, as in many database applications. Under an open-world assumption, failure to find a fact means only that it is unknown. Confusing these assumptions can produce serious errors in compliance, medical, and legal applications.

Combining Symbolic and Statistical AI

Symbolic systems provide explicit structures, constraints, and explanations; statistical models provide robust pattern recognition from large and imperfect datasets. A hybrid architecture may use a language model to extract entities from documents, an ontology to normalize them, a knowledge graph to connect them, and a rule or probabilistic engine to assess implications.

Such systems require careful interface design. Extracted facts may be uncertain, contradictory, or incorrectly linked to entities. Confidence scores should not be treated as logical truth. Human review may be required for high-impact inferences. Retrieval-augmented generation is another example: a generative model retrieves relevant documents or graph facts before producing an answer, thereby improving grounding while not eliminating hallucination risk.

Applications Across Organizations

Knowledge representation supports many professional settings. In finance, rules and graphs can link customers, accounts, beneficial owners, transactions, and sanctions data for risk analysis. In manufacturing, a semantic model can connect machines, components, maintenance histories, sensor events, and failure modes. In healthcare, ontologies help integrate clinical terminology, while Bayesian models support differential diagnosis. In education, student models can represent competencies, prerequisites, evidence of mastery, and recommended learning activities.

In enterprise analytics, a semantic layer allows users to ask for “revenue” or “active customer” according to shared organizational definitions rather than independent interpretations of database fields. In cybersecurity, knowledge graphs connect alerts, assets, vulnerabilities, identities, and attack techniques. In legal and regulatory work, rule engines can identify obligations and exceptions, but qualified professionals must review ambiguous interpretations.

The organizational value of KR&R depends not only on algorithms. It also depends on governance of vocabulary, ownership of definitions, update procedures, data quality, access control, and accountability for decisions.

Illustrative Case Study: A Hospital Deterioration Decision-Support System

Background

The following is an illustrative case. A hospital wishes to identify adult inpatients whose condition may be deteriorating. The organization has electronic health records, laboratory results, nursing observations, medication data, and clinical protocols stored in different systems.

Situation and Problem

A simple threshold rule based only on temperature generated too many alerts. Clinicians also needed explanations, and the system had to distinguish missing data from normal values. Furthermore, an alert should support—not replace—clinical judgment.

Analysis

The design team developed an ontology containing concepts such as patient, observation, medication, infection indicator, vital sign, and care unit. A knowledge graph linked each observation to a patient, time, measurement unit, and source. Rules represented explicit protocol conditions, such as repeated abnormal measurements or combinations of symptoms. A Bayesian network estimated deterioration risk using several variables, including trends rather than isolated values. Missing observations were represented as unknown rather than automatically normal.

The system used forward chaining to trigger candidate alerts and probabilistic inference to rank them. A clinician-facing explanation displayed the observations used, their timestamps, applicable rules, and the factors that increased or reduced estimated risk. A governance committee defined escalation thresholds and required periodic review.

Approach and Solution

The project began with a limited pilot in one ward. Domain experts validated the ontology and reviewed rules. Historical data were used to examine alert burden and missed cases, while prospective monitoring assessed whether clinicians found explanations useful. Access controls restricted sensitive information, and every recommendation was logged with the model version and evidence available at the time.

Outcome

The combined approach produced a more informative alerting process than the original single-threshold design. The principal improvement was not simply a higher predictive score; it was better prioritization and greater transparency. The system still required human confirmation because correlations could reflect documentation practices, treatment decisions, or differences among patient populations.

Learning Points

The case demonstrates that effective KR&R often combines ontology, graph structure, rules, and probability. It also shows why uncertainty, provenance, missingness, explainability, and workflow integration must be designed together. A technically sophisticated inference engine cannot compensate for poorly defined concepts or inadequate clinical governance.

Limitations, Risks, and Common Errors

Knowledge acquisition is expensive and knowledge bases become obsolete. Changes in policies, terminology, products, and scientific understanding require maintenance. Rules may conflict, and a large graph may contain duplicate, stale, or falsely linked entities. Automated reasoning can amplify an incorrect premise.

Several mistakes recur in practice. Designers may confuse correlation with causation, treat unknown as false, ignore time, omit provenance, or assume that a highly connected graph is reliable. They may also encode exceptions as ad hoc patches until the system becomes inconsistent and unmaintainable. In probabilistic systems, poorly calibrated probabilities can be more misleading than explicit uncertainty. In fuzzy systems, membership functions may reflect unexamined expert assumptions.

Computational complexity is another constraint. Satisfiability and theorem-proving problems can become difficult as expressiveness grows. Practical systems often use restricted rule languages, approximate inference, caching, indexing, or modular reasoning to achieve acceptable performance.

Ethical, Governance, and Professional Considerations

Knowledge-based AI can influence health, employment, credit, safety, and access to services. Organizations must identify who is accountable for the knowledge base, inference policy, and final decision. Important controls include provenance tracking, version management, audit logs, access restrictions, validation against relevant populations, and mechanisms for correction and appeal.

Explicit rules are not automatically fair. A rule can encode discriminatory policy, use a biased definition, or produce unequal effects even when applied consistently. Probabilistic models may inherit historical inequities, while knowledge graphs may systematically omit communities or misrepresent identity. Privacy risks increase when graphs make relationships easier to infer than they were in the original data sources.

Professional practice requires proportionality: high-impact decisions deserve stronger validation, human oversight, explanation, and review than low-risk recommendations. System documentation should describe intended use, known limitations, assumptions, data sources, update procedures, and situations in which the system must not be used.

Current Developments and Best Practices

Modern KR&R is evolving through graph machine learning, ontology learning, neural-symbolic reasoning, probabilistic programming, causal representation, and retrieval-grounded generative systems. Large language models can assist with knowledge extraction and ontology construction, but automated extraction requires verification because fluent language is not evidence of factual accuracy.

Effective projects generally follow these practices:

1. Define the decision or question before selecting a representation.

2. Establish a controlled vocabulary and clear ownership of concepts.

3. Record provenance, timestamps, confidence, and semantic versioning.

4. Separate facts, assumptions, rules, predictions, and actions.

5. Test inference with positive, negative, boundary, and contradiction cases.

6. Make closed-world or open-world assumptions explicit.

7. Combine automated reasoning with domain-expert review where consequences are high.

8. Monitor drift, error patterns, alert burden, and downstream effects.

9. Design explanations for the actual user and workflow.

10. Treat maintenance and governance as continuing operational responsibilities.

Chapter Summary

Knowledge representation gives AI systems formal or semi-formal structures for describing entities, properties, events, rules, and relationships. Propositional logic handles complete true-or-false statements, while predicate logic represents objects and quantified relations. Rule-based systems use forward or backward chaining, and expert systems add working memory and explanation facilities. Semantic networks, ontologies, and knowledge graphs organize concepts and interconnections, with provenance and governance needed to preserve trust. Because real environments contain incomplete, noisy, and vague information, Bayesian networks, fuzzy logic, default reasoning, and belief revision are important complements to classical logic. Practical systems increasingly combine symbolic and statistical methods. Their success depends not only on inference accuracy but also on maintainability, explainability, fairness, privacy, accountability, and integration with organizational decisions.

Key Terms

Knowledge representation: The formal or structured encoding of information for computational interpretation and reasoning.

Inference: The process of deriving conclusions from facts, rules, or evidence.

Proposition: A declarative statement that has a truth value.

Predicate: A symbol expressing a property or relation involving one or more entities.

Tautology: A logical expression true under every possible interpretation.

Entailment: A relationship in which a conclusion is true in every model of a knowledge base.

Unification: Finding substitutions that make logical expressions identical.

Forward chaining: Data-driven inference that begins with known facts and applies matching rules.

Backward chaining: Goal-driven inference that works backward from a desired conclusion.

Expert system: A knowledge-based system designed to perform or support specialist reasoning.

Semantic network: A graph representation of concepts connected by labelled semantic relations.

Ontology: A formal specification of concepts, relations, constraints, and axioms in a domain.

Knowledge graph: A graph of entities and semantically labelled relationships, often represented as triples.

Provenance: Information about the source, time, or process through which a fact was obtained.

Bayes’ theorem: A rule for updating a hypothesis probability using prior belief and observed evidence.

Bayesian network: A directed acyclic graph representing conditional dependencies among random variables.

Fuzzy logic: A logic that represents graded membership or applicability rather than only binary truth.

Non-monotonic reasoning: Reasoning in which new information can retract a previously derived conclusion.

Open-world assumption: The principle that absence of a fact does not imply that the fact is false.

Neuro-symbolic AI: An approach combining learned statistical models with explicit symbolic representations or reasoning.

Review Questions

Short Answer Questions

1. What distinguishes knowledge representation from ordinary data storage?

2. Define entailment in propositional or predicate logic.

3. Differentiate forward chaining from backward chaining.

4. What is the role of provenance in a knowledge graph?

5. How does fuzzy membership differ from probability?

Long Answer Questions

1. Explain the expressive capabilities and limitations of propositional logic and first-order predicate logic.

2. Describe the architecture of an expert system and discuss the importance of its explanation facility.

3. Compare semantic networks, ontologies, and knowledge graphs, using an organizational example.

4. Explain Bayesian networks, including their graph structure, factorization, and practical uses.

5. Discuss how ethical and governance requirements affect the design of knowledge-based AI systems.

Analytical / Application Questions

1. A compliance database contains no record that a supplier has passed a security audit. Explain how a closed-world assumption and an open-world assumption would lead to different conclusions.

2. Design a small hybrid reasoning approach for detecting suspicious financial transactions. Identify the ontology elements, rules, probabilistic variables, and human-review points.

3. A rule states, “If a customer receives a premium offer, then the customer is highly loyal.” Analyze why this may be an invalid inference and propose a more appropriate representation of uncertainty or causality.

22. Multiple Choice Questions with Answers

Question 1

Which statement best expresses logical entailment?

A. A conclusion is plausible because it appears frequently in the data

B. A conclusion is true in every model in which the knowledge base is true

C. A conclusion has a fuzzy membership value greater than 0.5

D. A conclusion is selected by the most recently activated rule

Correct Answer: B. A conclusion is true in every model in which the knowledge base is true

Question 2

A system begins with the goal ‘Is this transaction fraudulent?’ and searches for rules that could establish that goal. Which inference strategy is being used?

A. Forward chaining

B. Backward chaining

C. Fuzzification

D. Unification only

Correct Answer: B. Backward chaining

Question 3

What is the principal purpose of unification in first-order logic?

A. To assign probabilities to propositions

B. To convert a graph into a database table

C. To find substitutions that make logical expressions match

D. To measure the vagueness of a concept

Correct Answer: C. To find substitutions that make logical expressions match

Question 4

Which statement correctly distinguishes an ontology from a knowledge graph?

A. An ontology specifies domain concepts and constraints, while a knowledge graph populates relationships among entities

B. An ontology stores only numerical data, while a knowledge graph stores only text

C. An ontology is always probabilistic, while a knowledge graph is always deterministic

D. There is no meaningful distinction between them

Correct Answer: A. An ontology specifies domain concepts and constraints, while a knowledge graph populates relationships among entities

Question 5

A rare disease has a highly accurate diagnostic test, but most positive results are false positives. Which concept most directly explains this outcome?

A. The inheritance property of semantic networks

B. The base-rate effect in Bayesian reasoning

C. The closed-world assumption

D. The conflict-resolution strategy of rule systems

Correct Answer: B. The base-rate effect in Bayesian reasoning

Question 6

What does a fuzzy value of 0.8 for ‘high temperature’ represent?

A. An 80 percent probability that the temperature exists

B. An 80 percent chance that the sensor is correct

C. The degree to which the temperature belongs to the fuzzy concept ‘high’

D. A logical proof that the temperature is high

Correct Answer: C. The degree to which the temperature belongs to the fuzzy concept ‘high’

Question 7

Under an open-world assumption, failure to find a fact means that the fact is:

A. False

B. True

C. Unknown unless additional evidence is available

D. Automatically inconsistent

Correct Answer: C. Unknown unless additional evidence is available

Question 8

Which design choice is most appropriate for a high-impact clinical alert system?

A. Treat every missing measurement as normal

B. Hide the evidence so users cannot challenge the alert

C. Record evidence, provenance, model version, and provide human review

D. Use a single threshold regardless of clinical context

Correct Answer: C. Record evidence, provenance, model version, and provide human review

Question 9

Why can a highly connected knowledge graph still be unreliable?

A. Graph connectivity proves all assertions are causal

B. Connections may be duplicated, stale, incorrectly linked, or unsupported by provenance

C. Knowledge graphs cannot represent relationships

D. Graphs are incapable of storing timestamps

Correct Answer: B. Connections may be duplicated, stale, incorrectly linked, or unsupported by provenance

Question 10

Which statement best describes non-monotonic reasoning?

A. New information can cause a previously derived conclusion to be withdrawn

B. All conclusions remain true after any new information is added

C. Only numerical probabilities may be used

D. The system cannot represent exceptions

Correct Answer: A. New information can cause a previously derived conclusion to be withdrawn