Knowledge, logic and reasoning under uncertainty

Intelligent behaviour depends on knowledge: facts about the world, rules about how things work, and the ability to combine them to reach new conclusions. For decades, much of AI research focused on representing knowledge explicitly, in forms a computer can manipulate, and on reasoning with it. This approach produced expert systems, knowledge graphs, planning systems and formal verification tools that are still in use. It also ran into a fundamental difficulty: real knowledge is uncertain, incomplete and full of exceptions. This lesson covers logic and rule-based reasoning, knowledge graphs, and probabilistic reasoning with Bayes' rule, which together underpin how AI systems handle uncertainty, and explains how these ideas relate to modern learned systems.

Logic and inference

Logic is a precise language for stating facts and deriving conclusions. In propositional logic, statements are true or false and are combined with AND, OR, NOT and IF-THEN. Inference rules derive new true statements from old ones. The most famous is modus ponens: from "if P then Q" and "P", conclude "Q". For example, from "if the server room temperature exceeds 35 °C, then an alarm sounds" and "the temperature is 37 °C", a system concludes that an alarm sounds.

First-order logic adds objects, properties and relationships with variables and quantifiers ("for all" and "there exists"), so it can state general rules such as "every server in a rack shares that rack's power feed". Logic is sound (it never derives false conclusions from true premises) and transparent (every conclusion can be traced to its premises), which is why it remains essential in safety-critical software, hardware verification, databases and legal and regulatory reasoning.

Expert systems and their limits

Expert systems of the 1970s and 1980s encoded the knowledge of human specialists as hundreds or thousands of if-then rules, with an inference engine to apply them. MYCIN, developed at Stanford in the 1970s, recommended antibiotics for blood infections and performed comparably to specialists in tests; XCON configured computer orders for Digital Equipment Corporation and saved the company millions of dollars a year. Expert systems were a commercial boom in the 1980s (Lesson 2).

They also revealed hard problems:

• Knowledge acquisition bottleneck: experts struggle to state their knowledge as rules, and extracting it is slow and expensive.
• Brittleness: systems fail badly on situations their rules did not anticipate.
• Maintenance: large rule bases become inconsistent and hard to update.
• Common sense: people rely on vast amounts of unstated everyday knowledge ("water is wet", "people do not like to wait"), which proved extremely difficult to write down. The Cyc project, begun in 1984, spent decades encoding millions of common-sense facts.
• Uncertainty: real rules have exceptions and degrees of confidence.

Rule-based systems survive wherever rules are clear and explanations are required: tax software, eligibility checks, building control sequences, fraud rules, and business process automation. Many modern AI products combine learned models with rules for policy, safety and compliance.

Knowledge graphs

A knowledge graph represents knowledge as a network of entities (nodes) connected by relationships (edges), such as "Toronto — is located in — Ontario" or "GPU H100 — manufactured by — NVIDIA". Large knowledge graphs, such as Wikidata, with over 100 million items, and those built by search engines, power the information panels in search results, question answering, product recommendations and data integration in large organizations.

Graphs support inference: if A is located in B and B is located in C, then A is located in C. Today, knowledge graphs are often combined with language models, which can extract facts from text to build graphs and use graphs to ground their answers in verified facts (Lesson 9).

Planning

Knowledge about actions lets a system plan: find a sequence of actions that achieves a goal. Classical planning describes each action by its preconditions (what must be true before it) and effects (what becomes true or false after it), an approach introduced with the STRIPS planner developed for Shakey, a mobile robot built at the Stanford Research Institute between 1966 and 1972 that could plan routes and push boxes between rooms. A planner searches through possible sequences of actions (Lesson 3), using the action descriptions to reason about which actions are useful.

Planning is used in logistics, manufacturing schedules, space missions (NASA used automated planners to operate spacecraft), video game characters and robotics. A data centre maintenance procedure is a kind of plan: to replace a UPS module safely, the system must first be transferred to bypass, which requires the bypass to be available, and so on. Planning systems can check such procedures for missing steps or unsafe orderings.

Why uncertainty matters

Most real-world reasoning is uncertain. A medical test can be wrong; a sensor can fail; a rule like "birds fly" has exceptions; and evidence is incomplete. Early AI systems handled uncertainty with ad hoc "certainty factors", which could produce inconsistent results. From the 1980s, researchers such as Judea Pearl showed how probability theory provides a principled foundation for reasoning with uncertainty, an idea that transformed AI.

Probability measures degrees of belief between 0 (impossible) and 1 (certain). The key tool for updating beliefs with evidence is Bayes' rule:

where \(P(H)\) is the prior probability of a hypothesis \(H\) before seeing evidence, \(P(E \mid H)\) is the likelihood of the evidence if the hypothesis is true, and \(P(H \mid E)\) is the posterior probability after seeing the evidence.

p_disease = 0.01
sensitivity = 0.95
false_positive = 0.05

p_pos = sensitivity * p_disease + false_positive * (1 - p_disease)
posterior = sensitivity * p_disease / p_pos
print(f"P(positive test) = {p_pos:.4f}")
print(f"P(disease | positive) = {posterior:.3f}")

prior = p_disease
for test in range(1, 4):
    p_pos = sensitivity * prior + false_positive * (1 - prior)
    prior = sensitivity * prior / p_pos
    print(f"after {test} independent positive test(s): {prior:.3f}")

for base in [0.001, 0.01, 0.1, 0.3]:
    post = sensitivity * base / (sensitivity * base + false_positive * (1 - base))
    print(f"prevalence {base:>5}: P(disease | positive) = {post:.3f}")

P(positive test) = 0.0590
P(disease | positive) = 0.161
after 1 independent positive test(s): 0.161
after 2 independent positive test(s): 0.785
after 3 independent positive test(s): 0.986
prevalence 0.001: P(disease | positive) = 0.019
prevalence  0.01: P(disease | positive) = 0.161
prevalence   0.1: P(disease | positive) = 0.679
prevalence   0.3: P(disease | positive) = 0.891

The result surprises most people: with a disease affecting 1% of the population, a positive result from a test that is 95% accurate means only about a 16% chance of disease, because the few true positives are outnumbered by false positives from the much larger healthy population. Ignoring the prior (the base rate) is one of the most common reasoning errors, made by people and by poorly designed systems. A second independent positive test raises the probability to about 79%.

Bayesian networks

Real problems involve many uncertain variables that influence each other. A Bayesian network represents them as a graph in which arrows show direct influence, and each variable has a table of probabilities given its parents. For example, a network for diagnosing a data centre outage might link "utility failure" and "generator fault" to "UPS on battery", and that to "battery depleted" and "load dropped". Given evidence (the load dropped and the utility was normal), the network computes the most likely causes. Bayesian networks are used in medical diagnosis, fault detection, risk assessment and spam filtering, and they make reasoning transparent because the structure and probabilities can be inspected.

Decisions under uncertainty

Knowing probabilities is not enough; an intelligent agent must act. Decision theory combines probabilities with utilities (values of outcomes) and chooses the action with the highest expected utility:

Logic, probability and learning today

Modern machine learning systems are, in a sense, probabilistic reasoners whose knowledge is learned from data rather than written by hand: a classifier outputs probabilities, and a language model is a probability distribution over text. But they lack some strengths of explicit knowledge: guaranteed consistency, easy updating of individual facts, and transparent explanations. Researchers in neurosymbolic AI combine the two, for example by letting language models call logic engines, calculators and databases (tool use), or by constraining learned systems with rules. When reliability and explanation matter, as in medicine, law, engineering and finance, explicit knowledge and well-calibrated probabilities remain essential.