Metadata Card

• Prerequisites: ch01 Search Algorithms, Vol 10 Probability Theory
• Estimated time: 45 minutes
• Core difficulty: Advanced
• Reading mode: High focus
• Completion: Able to build a logical reasoning system, represent constraint satisfaction problems, understand Bayesian network inference mechanisms

Your Progress

At the first workbench in the Model Workshop, you learned search—finding paths in a known space.

But Ahua's next letter asked: "What if the knowledge itself is incomplete?" You put down the letter, looking at the second workbench. There's another set of tools here: logical reasoning, probabilistic networks—not finding paths, but making judgments under uncertainty.

Your Task

Search assumes you can enumerate all states. But in reality, knowledge is often fragmented and noisy. You need a "representation" to encapsulate knowledge, paired with a "reasoning" mechanism to derive new conclusions. This chapter follows three paths: logic (deterministic), CSP (constraint-driven), and Bayesian networks (probability-driven).

Chapter Layers

• Required: Propositional logic reasoning, constraint satisfaction problems, Bayesian network representation
• Optional: Exact and approximate inference in Bayesian networks
• Advanced: Viewing knowledge representation as a search space design problem

Breaking Through · Tracing the Origin

You see a rule: "If it rains, the ground gets wet." Now the ground is wet—you conclude: it rained. Is this reasoning correct? It depends on an implicit assumption: no other reason could make the ground wet. You've done the reverse of Modus Ponens—but in real-world logic, this is the "affirming the consequent" fallacy.

A truly reliable knowledge system not only reasons but also evaluates the reliability of its reasoning. This is the starting point of this chapter.

Propositional Logic and Reasoning

Propositional logic is the most basic knowledge representation language. Each proposition takes a true or false value, combined with logical connectives (→, ∧, ∨, ¬).

The reasoning workbench in the Model Workshop starts with the simplest rule chains. Forward chaining repeatedly applies rules from known facts until saturation—this is exactly the 'if-then' reasoning you use in complex condition checks.

# Simple rule-based reasoning engine
rules = [
    ("rain", "ground_wet"),       # rain → ground_wet
    ("ground_wet", "slippery"),   # ground_wet → slippery
]

def forward_chain(facts, rules):
    """Forward chaining inference: derive new facts from known facts"""
    known = set(facts)
    changed = True
    while changed:
        changed = False
        for premise, conclusion in rules:
            if premise in known and conclusion not in known:
                known.add(conclusion)
                changed = True
    return known

facts = forward_chain(["rain"], rules)
print(facts)  # {'rain', 'ground_wet', 'slippery'}

Forward chaining starts from known facts and applies rules repeatedly until saturation. Backward chaining starts from the goal and searches in reverse: to prove "slippery," you need to prove "ground_wet," which requires proving "rain."

Constraint Satisfaction Problems

Many real-world reasoning problems are constraint-driven. For example, scheduling: a teacher can't teach two classes at the same time, each course has a fixed classroom capacity—you need to find an assignment satisfying all constraints.

CSP is modeled with the triple of variables, domains, and constraints:

Backtracking search for constraint satisfaction problems is another classic framework. You assign values to all variables, checking each time whether the assignment conflicts with existing assignments—it's search with constraints.

from itertools import product

def backtrack_search(variables, domains, constraints):
    """Backtracking search for solving CSP"""
    assignment = {}

    def consistent(var, value, assignment):
        return all(
            constraint(var, value, v, assignment[v])
            for v in assignment
            for constraint in constraints.get((var, v), [])
        )

    def search(assignment):
        if len(assignment) == len(variables):
            return assignment
        var = next(v for v in variables if v not in assignment)
        for value in domains[var]:
            if consistent(var, value, assignment):
                assignment[var] = value
                result = search(assignment)
                if result:
                    return result
                del assignment[var]
        return None

    return search({})

Example: map coloring—adjacent regions can't share the same color.

variables = ['WA', 'NT', 'SA', 'Q', 'NSW', 'V', 'T']
domains = {v: ['R', 'G', 'B'] for v in variables}
constraints = {}
pairs = [('WA','NT'),('WA','SA'),('NT','SA'),('NT','Q'),
         ('SA','Q'),('SA','NSW'),('SA','V'),('Q','NSW'),
         ('NSW','V')]
for a, b in pairs:
    constraints[(a,b)] = [lambda x, xv, y, yv: xv != yv]

print(backtrack_search(variables, domains, constraints))
# {'WA': 'R', 'NT': 'G', 'SA': 'B', 'Q': 'R', 'NSW': 'G', 'V': 'R', 'T': 'R'}

The difficulty of CSP isn't expressiveness—it's search efficiency. Variable ordering and value ordering heuristics (MRV, degree heuristic, least-constraining value) can massively impact backtracking counts.

Bayesian Networks

Logical systems can't handle uncertainty. Bayesian networks use a graph structure to represent probabilistic dependencies between variables: nodes are random variables, directed edges represent "direct influence," and each node has a conditional probability table.

Logical reasoning only deals with a deterministic world: if it doesn't rain, the ground isn't wet. But reality isn't like that—a 'sprinkler' can also make the ground wet. Bayesian networks use probability to represent multiple possible causes simultaneously.

# A simple Bayesian network inference
# Events: rain → ground_wet
#         sprinkler → ground_wet
# rain and sprinkler are independent

import numpy as np

class BayesNet:
    def __init__(self):
        self.nodes = {}
        self.cpts = {}

    def add_node(self, name, parents, prob_table):
        self.nodes[name] = parents
        self.cpts[name] = prob_table

    # Given evidence, compute marginal probability by enumeration

def enumeration_ask(query, evidence, net):
    """Enumerate all hidden variables to compute P(query | evidence)"""
    hidden = [v for v in net.nodes if v not in evidence and v != query]
    return _enumerate_all(net.variables(), evidence, hidden, net)

# Variable elimination is more efficient for practical inference
def variable_elimination(net, query, evidence, ordering):
    """Variable elimination method"""
    factors = []
    for var in net.variables():
        factor = net.make_factor(var, evidence)
        factors.append(factor)
    for var in ordering:
        if var not in query and var not in evidence:
            factors = _sum_out(var, factors)
    result = _normalize(_pointwise_product(factors))
    return result

Exact inference in Bayesian networks is NP-hard (variable elimination has exponential complexity in the worst case), so large networks typically use approximate inference methods like Gibbs sampling or likelihood weighting.

Common Pitfalls

• The "closed-world assumption" in logical systems: what's not proven true is considered false? Or not proven true is unknown? In AI terms, this is default negation vs. open world.
• In CSP, consistency doesn't equal satisfiability—node consistency and arc consistency don't guarantee a solution exists.
• The conditional independence assumption in Bayesian networks is crucial—if your conditional probability table doesn't satisfy the graph structure, inference will be wrong.
• The directionality of Bayesian networks implies causality, but correlation doesn't equal causation—two observed correlated variables might share a third unobserved common cause.

Pass Challenges

• Warm-up (15 min): Implement a backward chaining engine. Input the goal "slippery," output which initial facts are needed.
• Challenge (30 min): Use CSP to implement a simple Sudoku solver (9x9, backtracking + MRV heuristic).
• Observation: Build a 3-node Bayesian network (A→B→C), given P(A), P(B|A), P(C|B), compute P(B|C=1). Compare the steps needed for enumeration vs. variable elimination.

Traveler's Notes

Knowledge representation determines what an AI system can "think," and the reasoning mechanism determines "how it thinks." Logic provides guarantees, probability provides flexibility—their combination is the foundation of truly intelligent reasoning.

-> Next Chapter Preview

Search and reasoning alone aren't enough—agents need to learn from environmental interaction without complete knowledge. That's what reinforcement learning does.