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:
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.
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:
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.
| Language | What it adds | Inference | Complexity | Typical use |
|---|---|---|---|---|
| Propositional logic | Atoms and connectives | Truth tables, SAT, resolution | NP-complete | Circuits, constraints, SAT solvers |
| First-order logic | Objects, predicates, quantifiers | Resolution, sequent calculus | Undecidable; semi-decidable | Mathematics, knowledge representation |
| Datalog | Horn rules, recursion, no functions | Least fixpoint, semi-naive | PTIME data complexity | Graph queries, program analysis |
| ASP | Stable models, default negation | Answer-set solving | NP-complete | Configuration, scheduling, puzzles |
| Description logic | Concepts, roles, TBox/ABox | Tableau, saturation | EL PTIME; ALC ExpTime | Ontologies, the semantic web |
| Production rules | IF–THEN rules, working memory | Forward chaining | Depends on the rule set | Expert 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.
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:
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.
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.
03 / Search & planningReasoning as a path through states.
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.
| System | Representation | Inference | Domain | Lesson |
|---|---|---|---|---|
| MYCIN | Production rules + certainty factors | Forward chaining | Bacterial infections | Rules can encode expertise; confidence is not probability |
| DENDRAL | Rules + candidate generation | Generate and test | Molecular structure | A good search space beats a general reasoner |
| XCON | Configuration rules | Forward chaining | Computer orders | Deployed 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.
| Dimension | Symbolic strength | Symbolic weakness |
|---|---|---|
| Representation | Compositional, inspectable, variable-binding | Requires a hand-built vocabulary and model |
| Inference | Deduction with soundness/completeness guarantees | Brittle under uncertainty; can be intractable |
| Data | Learns from rules, not from millions of examples | Cannot acquire the rules from raw experience |
| Perception | Interfaces cleanly with a symbolic abstraction | Cannot ground its own symbols in pixels |
| Maintenance | Every rule is visible and reviewable | Every rule must be maintained; the base drifts |
| Open worlds | Explicit assumptions (closed/open) can be stated | Defaults, 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.
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:
| Interface | Symbolic role | Concrete example |
|---|---|---|
| Logic as loss | A penalty for violating a constraint | Semantic loss on a classifier's output |
| Logic as architecture | An executor inside the model | DeepProbLog's neural predicates |
| Logic as data | Structure for inputs or embeddings | A knowledge graph or ontology embedding |
| Logic as search | A proposal generator plus a symbolic search | AlphaGeometry's auxiliary constructions |
| Logic as verifier | A monitor that checks a candidate | A 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.
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.
07 / Six systemsOne tradition, six lessons.
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.
Prolog and Datalog
A query is answered by a proof. The engine unifies, backtracks, and returns a substitution. Datalog removes function symbols to guarantee termination.
ASP Sudoku
Generate a candidate, define the consequences, test the constraints. The answer set is a valid grid. The same pattern encodes scheduling and configuration.
PDDL planners
Fast Downward and FF search over a grounded state space with delete-relaxation heuristics. The output is a plan, not a policy.
MYCIN
A few hundred rules, forward chaining, and certainty factors. It matched specialists on its benchmark and exposed the maintenance problem.
Cyc and ConceptNet
Hand-built common-sense knowledge: concepts, relations, and defaults. The artifact is impressive; the long tail is the lesson.
Lean and Coq
A proof assistant checks every step against a small kernel. The guarantee is formal; the cost is that a human must write the proof.
08 / RecapWhat you should be able to do now.
Explain why a symbolic system represents a plan as a discrete, checkable object.
Place propositional logic, FOL, Datalog, ASP, and description logic on the expressivity/complexity ladder.
Trace forward and backward chaining, unification, and resolution on a small example.
Explain the frame, ramification, and qualification problems — and why they are representational, not implementational.
Describe A* and why admissibility gives optimality.
Explain the knowledge-acquisition bottleneck and why MYCIN's certainty factors are not probabilities.
State what symbolic AI is strong and weak at, without slogans.
Map a symbolic component onto the five neurosymbolic interfaces.
Exercises
- 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?
- 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?
- Design a heuristic. For blocksworld, define an admissible heuristic and prove it never overestimates. Then find a state where it is very loose.
- 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?
- 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?
- 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.