Course / Act II · The two worlds / Lectures Lecture 02

The symbolic world.

Before there were vectors, there were proofs. This is the other parent of neurosymbolic AI: a world of discrete symbols, rules, and search — its power, its price, and the exact places where it fails.

~50 min read Lecture 01 first 6 systems in the gallery 1 interactive lab Updated 2026-11-16

A robot arm, three blocks, a table. The goal is a tower. A symbolic system does not learn a policy from a million demonstrations; it represents the world as facts, the goal as a formula, and the plan as a sequence of actions whose preconditions and effects it can check. That is the promise. The rest of this lecture is about the price.

00 / The hookA plan is a discrete object.

Blocksworld is the fruit fly of planning. There is a table, a set of blocks, and a hand that can hold one block at a time. The goal is stated in logic: on(a, b). An action is a small program with a precondition and an effect. In PDDL, the language planners actually use, the stack action looks like this:

; PDDL fragment (:action stack :parameters (?x ?y) :precondition (and (clear ?x) (holding ?x) (clear ?y)) :effect (and (on ?x ?y) (clear ?x) (not (holding ?x)) (not (clear ?y))))

Give a planner the initial state and the goal, and it returns a plan: unstack(c, a), putdown(c), pickup(a), stack(a, b). Every step is a discrete object. Every precondition is checkable. If the plan fails, the failure is local: a precondition was false, or the model was wrong. There is no gradient to blame and no distribution shift to hide behind.

This is the symbolic bet: represent the world as structure, reason over the structure, and make every step inspectable. The bet pays in blocksworld, in Sudoku, in a proof assistant, and in a database query. It fails in a kitchen, on a street, and in any world whose facts you cannot finish writing down.

Caveat · the toy is the point

Blocksworld is small on purpose. The interesting question is not whether a planner can stack three blocks; it is what happens to the same machinery when the blocks are cups, the table is a cluttered counter, and the hand is a robot with a noisy camera. The toy isolates the reasoning from the perception. That separation is both the strength and the weakness of the whole tradition.

01 / The toolkitSix languages for structure.

“Symbolic AI” is not one formalism. It is a family of languages, each with a different trade-off between what it can say and what it can decide. The six that matter most for this course are propositional logic, first-order logic, Datalog, answer set programming, description logic, and production rules.

Propositional logic

The language of atoms and connectives: rain, wet, rain → wet. A model is an assignment of true and false to every atom; a formula is satisfied if the assignment makes it true. Entailment is defined semantically: K ⊨ φ iff every model of K is a model of φ. Deciding satisfiability is the original NP-complete problem (Cook, 1971); deciding entailment is the same problem in another dress.

Propositional logic is compositional and completely decidable. It is also flat: it cannot say “all cubes are red” without listing every cube. That is what quantifiers are for.

First-order logic

First-order logic (FOL) adds objects, predicates, functions, and quantifiers. ∀x (Cube(x) → Red(x)) says every cube is red; ∃x (On(x, a) ∧ Cube(x)) says something is on a and is a cube. A structure gives the predicates an extension; entailment is again truth in all models.

FOL is the language of mathematics and the reference point for knowledge representation. It is also undecidable: Church and Turing showed that no procedure decides entailment for all first-order formulas. It is semi-decidable — a complete proof procedure will eventually find a proof if one exists, but it may run forever when the formula is not entailed. That asymmetry is not a detail; it is the reason practical systems use fragments.

Datalog

Datalog is the fragment that made logic programming practical. A program is a set of facts and rules:

% facts parent(alice, bob). parent(bob, carol). parent(carol, dave). % rules ancestor(X, Y) :- parent(X, Y). ancestor(X, Y) :- parent(X, Z), ancestor(Z, Y).

There are no function symbols, so the Herbrand universe is finite; evaluation reaches a least fixpoint in polynomial time in the size of the data (though the combined complexity can be exponential in the program). Recursion is built in, which is exactly what a graph query needs. Negation is allowed only in strata, so the program has a unique intended model. Datalog is the language of queries, policies, and many program analyses — and the lab for this lecture is a small interpreter for it.

Answer set programming

Answer set programming (ASP) generalizes logic programming with stable-model semantics and default negation. A program is a set of rules; an answer set is a set of atoms that is closed under the rules and is its own reduct's least model. The practical style is generate, define, test: guess a candidate with choice rules, define what follows, and eliminate candidates that violate a constraint. Sudoku is the canonical example: guess a digit for each empty cell, define the row/column/box constraints, and let the solver find the stable models.

ASP is expressive and concise, and it is not polynomial: deciding whether a program has an answer set is NP-complete in general. The trade-off is deliberate. You give up tractability to get a declarative encoding of a combinatorial search.

Description logic

Description logic is a family of decidable fragments designed for ontologies. Concepts denote sets of individuals, roles denote binary relations, and a knowledge base has a TBox (terminology: Parent ⊑ Person) and an ABox (assertions: Parent(alice)). OWL is the web standard built on description logic. The fragments trade expressivity for decidability: EL is polynomial, ALC is ExpTime-complete, and richer fragments climb further.

Production rules and frames

Expert systems used simpler languages: IF–THEN production rules and frame-like structures with slots and defaults. They are not as clean as FOL, but they were deployable, and they made the knowledge-acquisition problem visible: someone has to write the rules, and someone has to keep them true.

Table 1.1 · The symbolic languages, compared by what they can say and what they can decide.
LanguageWhat it addsInferenceComplexityTypical use
Propositional logicAtoms and connectivesTruth tables, SAT, resolutionNP-completeCircuits, constraints, SAT solvers
First-order logicObjects, predicates, quantifiersResolution, sequent calculusUndecidable; semi-decidableMathematics, knowledge representation
DatalogHorn rules, recursion, no functionsLeast fixpoint, semi-naivePTIME data complexityGraph queries, program analysis
ASPStable models, default negationAnswer-set solvingNP-completeConfiguration, scheduling, puzzles
Description logicConcepts, roles, TBox/ABoxTableau, saturationEL PTIME; ALC ExpTimeOntologies, the semantic web
Production rulesIF–THEN rules, working memoryForward chainingDepends on the rule setExpert systems, business rules

02 / InferenceHow a conclusion is forced.

Inference is the engine of the symbolic world. There are two directions to run it, and two ways to prove that a step is licensed.

Forward and backward chaining

Forward chaining starts from the facts and fires every rule whose body is satisfied, adding conclusions until nothing new appears. It is data-driven: add a fact, and the consequences propagate. Datalog evaluation is forward chaining to a fixpoint. Backward chaining starts from the query, finds rules whose head matches it, and recursively tries to prove their bodies. It is goal-driven: Prolog's SLD resolution is the canonical example.

The two directions are dual, not equivalent in cost. Forward chaining computes every consequence; backward chaining computes only what the query needs. If the query is one fact in a large database, backward chaining is usually the right default. If the facts change constantly and many queries share consequences, forward chaining amortizes the work.

Unification and resolution

Unification is the operation that makes two terms identical by substituting variables. To prove ancestor(alice, dave), backward chaining unifies it with the head ancestor(X, Y), binding X = alice, Y = dave, then tries the rule body parent(alice, Z), ancestor(Z, dave). The substitution is the trace; a proof is a sequence of such substitutions.

Resolution is the completeness engine behind first-order theorem provers. Put the premises and the negation of the goal in clausal form; repeatedly resolve a clause containing l with a clause containing ¬l; if the empty clause appears, the goal is entailed. Resolution is sound and refutation-complete. It is not a decision procedure for FOL, because the search space can be infinite.

C1 ∨ l,   C2 ∨ ¬l   ⟹   C1 ∨ C2
(2.1)

The fixpoint, concretely

For a Datalog program, let I0 be the set of facts. At each round, for every rule and every substitution that makes the body true in In, add the head:

In+1 = In ∪ { head(r)σ  |  r ∈ P,   body(r)σ ⊆ In }
(2.2)

The sequence is monotone and bounded by the finite Herbrand base, so it stabilizes. The least fixpoint is the intended model. This is why Datalog terminates, and why it cannot express “there exists a path of arbitrary length” with a function symbol that builds new terms.

Closed world, open world

Closed-world semantics assumes that what is not derivable is false. That is the right default for a database and for Datalog with negation. Open-world semantics assumes that unknown means unknown, which is the right default for an ontology: the fact that you have not recorded a person's parent does not make them parentless. The choice changes what a negative answer means, and it is one of the first questions to ask of any symbolic system.

Definition · the three properties that matter

Soundness: every provable formula is true in all models. Completeness: every entailed formula is provable. Decidability: a procedure always terminates with yes or no. A system can be sound and complete but undecidable (FOL), sound and decidable but incomplete (many DL fragments), or neither. The label “logic-based” says nothing until you know which.

Inference answers “what follows?”. Search answers “what should I do?”. The two are cousins: a proof is a path through a space of clauses, and a plan is a path through a space of states.

State-space search

A search problem is a set of states, a start state, a goal test, a set of actions with costs, and a successor function. Breadth-first search is complete and optimal for unit costs; depth-first search is memory-light but not optimal; uniform-cost search is Dijkstra on the state graph. A* adds a heuristic h(n) and expands the node with the smallest f(n) = g(n) + h(n). If h is admissible — never overestimates the true cost — A* is optimal. If it is consistent, A* never reopens a closed node under the standard graph-search implementation.

The heuristic is where domain knowledge enters. A good heuristic is a relaxed problem: ignore some preconditions, solve the easier problem, and use its cost as a lower bound. This is the same move as a symbolic abstraction, and it is why planning heuristics are a bridge between search and representation.

Planning

Classical planning is state-space search with a structured state. In STRIPS, a state is a set of ground atoms, and an action is a triple (Pre, Add, Del). The frame problem is the question of what an action leaves unchanged: if you list only the changes, you need an assumption that everything else persists; if you list everything, the representation explodes. PDDL makes the assumption explicit with add and delete effects, but the underlying issue does not disappear.

Forward search treats planning as search from the initial state; backward search treats it as search from the goal, using regression over actions. Partial-order planning represents a plan as a set of actions with ordering constraints and causal links, so it can leave irrelevant actions unordered. Modern planners combine forward search with powerful heuristics (hadd, hmax, landmarks, delete-relaxation), or compile bounded planning to SAT (SATPlan).

The complexity is humbling: bounded STRIPS planning is PSPACE-complete (Bylander, 1994). The worst case is not the typical case — modern planners solve huge instances — but the worst case explains why planning is not a subroutine you can call for free.

The three problems of a changing world

Classical planning assumes a closed, static, deterministic model. Real worlds violate all three assumptions, and the violations have names:

  • The frame problem: what does not change when an action occurs, and how to represent it without enumerating everything.
  • The ramification problem: the indirect consequences of an action — the cup moves, so the water spills, so the table is wet — must be represented too.
  • The qualification problem: the endless conditions under which an action is guaranteed to work. No finite list is complete.

These are not bugs in a particular planner. They are the price of describing a changing world in a discrete language. A neural policy avoids the price by learning a reactive mapping, and pays in a different currency: it cannot tell you why, and it cannot guarantee that its plan is executable.

04 / Knowledge & expertsThe model is the bottleneck.

An expert system is a knowledge base plus an inference engine. MYCIN (Shortliffe, 1976) diagnosed bacterial infections with a few hundred IF–THEN rules and a certainty-factor calculus. DENDRAL identified molecular structures; XCON configured computer orders. The pattern was the same: extract a specialist's rules, encode them, and run forward chaining.

The results were real, and the failure mode was predictable. The rules were expensive to elicit, expensive to maintain, and brittle at the edges. MYCIN's certainty factors were not probabilities; they were ad hoc numbers combined by a formula that happened to work on the cases the authors tried. When the domain shifted, the rule base did not adapt. This is the knowledge-acquisition bottleneck: the hard part is not the inference engine, it is the model.

Cyc is the extreme case: a decades-long attempt to encode common sense as a huge, hand-authored ontology and rule base. It produced a remarkable artifact and a lesson: common sense is not a finite list of facts. It is a web of default assumptions, exceptions, and context-sensitive regularities. The long tail is the whole problem.

Table 4.1 · Three expert systems and what they teach.
SystemRepresentationInferenceDomainLesson
MYCINProduction rules + certainty factorsForward chainingBacterial infectionsRules can encode expertise; confidence is not probability
DENDRALRules + candidate generationGenerate and testMolecular structureA good search space beats a general reasoner
XCONConfiguration rulesForward chainingComputer ordersDeployed value, then maintenance debt

Description-logic ontologies took a different route: keep the language decidable, accept incompleteness in the modeling, and use classification (subsumption) as the main inference. OWL ontologies are used in biomedicine and the semantic web for exactly this reason. The model is still the bottleneck, but the inference is predictable.

05 / The balanceWhat the tradition gets right — and wrong.

The symbolic tradition is not a failed precursor. It is a set of engineering achievements with a specific profile. The profile is easiest to see as a scorecard.

Table 5.1 · The symbolic profile. Real systems mix these strengths and weaknesses; the table locates the defaults.
DimensionSymbolic strengthSymbolic weakness
RepresentationCompositional, inspectable, variable-bindingRequires a hand-built vocabulary and model
InferenceDeduction with soundness/completeness guaranteesBrittle under uncertainty; can be intractable
DataLearns from rules, not from millions of examplesCannot acquire the rules from raw experience
PerceptionInterfaces cleanly with a symbolic abstractionCannot ground its own symbols in pixels
MaintenanceEvery rule is visible and reviewableEvery rule must be maintained; the base drifts
Open worldsExplicit assumptions (closed/open) can be statedDefaults, exceptions, and context are hard

The historical verdict is not “symbols lost.” It is that symbols alone could not solve perception, and neural networks alone could not solve composition and verification. The first AI winter followed overpromising on general reasoning; the expert-system bust followed overpromising on hand-built knowledge. The symbol grounding problem and the frame problem are the two fault lines that the next decades did not erase.

The honest scorecard

A symbolic system is excellent when the world is already discretized, the rules are known, and the answer must be checkable. It is poor when the input is pixels, the rules are tacit, or the world is open. Most real problems are mixtures. That is the opening for neurosymbolic AI, not a victory lap for either side.

06 / The bridgeSymbols as a language for constraints.

The neurosymbolic move is not to replace the symbolic tradition with learning. It is to use symbolic structure where it is strong — as a constraint, a memory, a plan, a proof, or a check — and learning where it is strong — perception, prediction, and proposal. The five interfaces from Lecture 01 are the design space:

Table 6.1 · What a symbolic component can do inside a learned system.
InterfaceSymbolic roleConcrete example
Logic as lossA penalty for violating a constraintSemantic loss on a classifier's output
Logic as architectureAn executor inside the modelDeepProbLog's neural predicates
Logic as dataStructure for inputs or embeddingsA knowledge graph or ontology embedding
Logic as searchA proposal generator plus a symbolic searchAlphaGeometry's auxiliary constructions
Logic as verifierA monitor that checks a candidateA planner validating an LLM's plan

The bridge is easiest to see in planning. A language model can propose a plan in natural language; a PDDL planner can check whether the plan is executable and repair it. The LLM handles the open-ended translation from a messy request to a formal domain; the planner handles the combinatorial search and the guarantee. Neither replaces the other. The interface is the point.

The same pattern appears in language (a model proposes a logical form, a solver checks it), in mathematics (a model proposes a construction, a proof assistant checks the proof), and in databases (a model proposes a query, the database executes it). The symbolic component is not a rival; it is a contract.

Source note · on the modern planning results

PlanBench (arXiv:2206.10498) evaluates LLMs on planning tasks and finds substantial gaps; LLM+P (arXiv:2304.11477) and LLM-Modulo (arXiv:2402.01817) use external planners or critics; the Embodied Agent Interface (arXiv:2410.07166) separates planning errors from grounding errors. Read the benchmarks, not the slogans: the results are task- and model-specific.

The gallery is deliberately old-fashioned. None of these systems has a neural component. Each is a clean instance of a symbolic idea that neurosymbolic systems still use.

08 / RecapWhat you should be able to do now.

01

Explain why a symbolic system represents a plan as a discrete, checkable object.

02

Place propositional logic, FOL, Datalog, ASP, and description logic on the expressivity/complexity ladder.

03

Trace forward and backward chaining, unification, and resolution on a small example.

04

Explain the frame, ramification, and qualification problems — and why they are representational, not implementational.

05

Describe A* and why admissibility gives optimality.

06

Explain the knowledge-acquisition bottleneck and why MYCIN's certainty factors are not probabilities.

07

State what symbolic AI is strong and weak at, without slogans.

08

Map a symbolic component onto the five neurosymbolic interfaces.

Exercises

  1. Trace the fixpoint. Take the ancestry program in §1 and compute I0 through I3 for a four-person family. Which facts appear at which round?
  2. Break the closed world. Add a negation to the ancestry program and find a case where the result depends on whether the world is closed. Is the program stratified?
  3. Design a heuristic. For blocksworld, define an admissible heuristic and prove it never overestimates. Then find a state where it is very loose.
  4. Encode a puzzle. Write an ASP program for a 4×4 Sudoku (or a scheduling problem) with generate-define-test. How many answer sets does it have without the clues?
  5. Compare two interfaces. Take the planning problem and describe how a loss, an architecture, and a verifier would each use the same PDDL model. What does each guarantee?
  6. Write the caveat. Find a claim in the modern LLM-planning literature and state the benchmark, the assumption, and the caveat in one paragraph.

Check your understanding

Ten questions, with explanations. The score is not the point; the questions you cannot answer are the reading list.

Reading list

The first five are the spine of this lecture. The rest are the next layer.

McCarthy & Hayes, “Some Philosophical Problems from the Standpoint of Artificial Intelligence” (1969).
The frame problem, stated before anyone knew how much it would matter.
Fikes & Nilsson, “STRIPS: A New Approach to the Application of Theorem Proving to Problem Solving” (1971).
The planning representation that every later planner answers to.
McDermott et al., “PDDL — The Planning Domain Definition Language” (1998).
The standard language; read a domain file, then a plan.
Apt, Blair & Walker, “Towards a Theory of Declarative Knowledge” (1988).
The semantics of logic programs and the least fixpoint.
Shortliffe, Computer-Based Medical Consultations: MYCIN (1976).
The expert-system template, including its certainty factors and its limits.
Russell & Norvig, Artificial Intelligence: A Modern Approach, chs. 7–11.
The standard treatment of logic, inference, and planning.
Valmeekam et al., “PlanBench” · arXiv:2206.10498.
What LLMs actually do on planning benchmarks.
Liu et al., “LLM+P” · arXiv:2304.11477.
Natural language → PDDL → a classical planner.
Kambhampati et al., “LLMs Can't Plan, But Can Help Planning in LLM-Modulo Frameworks” · arXiv:2402.01817.
Generate candidates; let external critics and verifiers check them.
Li et al., “Embodied Agent Interface” · arXiv:2410.07166.
Separates planning errors from grounding errors in embodied agents.