Lecture 02 · The two worlds

The symbolic world.

Before there were vectors, there were proofs. This is the other parent of neurosymbolic AI: discrete symbols, rules, search — and the exact places where they fail.

9 sections 6 systems 1 Datalog lab Self-paced
00 · Learning objectivesLecture 02 · The symbolic world

By the end of this lecture

Four things you can do.

01

Name the toolkit

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

02

Trace an inference

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

03

Explain search and planning

Say why A* is optimal with an admissible heuristic, and why planning is PSPACE-complete in the worst case.

04

Separate power from price

State what symbolic AI is strong and weak at — and map a symbolic component onto the five interfaces.

S/V · Lecture 02
00 · The hookLecture 02 · The symbolic world

A plan is a discrete object

Blocks, a hand, a goal.

B A C HAND TABLE
Goal: on(A, B). The hand holds one block at a time.
; PDDL (: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))))

Every step is checkable. If the plan fails, the failure is local: a precondition was false, or the model was wrong.

S/V · Lecture 02
00 · The hookLecture 02 · The symbolic world

What the planner returns

Four steps, each forced.

01unstack(c, a)  — c is clear, c is on a
02putdown(c)  — the hand is holding c; c becomes clear on the table
03pickup(a)  — a is clear and on the table
04stack(a, b)  — the hand holds a; b is clear
The plan is a proof in another language. Each step is licensed by the previous state and the action schema; the final state satisfies the goal.
S/V · Lecture 02
00 · The hookLecture 02 · The symbolic world

The price of the toy

Three problems with a changing world.

Frame

What does an action leave unchanged? Representing persistence without listing every fact.

Ramification

The indirect consequences: the cup moves, the water spills, the table is wet.

Qualification

The endless conditions under which an action is guaranteed to work.

These are representational problems, not bugs in a planner. A neural policy avoids them by learning a reactive mapping — and pays by losing the guarantee.

S/V · Lecture 02
01 · The toolkitLecture 02 · The symbolic world
01 / 08

Six languages for structure.

Each one trades expressivity for decidability. The trade-off is the design space.

S/V · Lecture 02
01 · The toolkitLecture 02 · The symbolic world

From flat to quantified

Atoms, then objects.

Propositional

rain → wet, rain ⊨ wet. Truth tables decide it; satisfiability is NP-complete.

Flat: cannot say “all cubes are red” without listing every cube.

First-order

∀x (Cube(x) → Red(x)). Quantifiers range over objects; a model gives predicates an extension.

Expressive — and undecidable. Semi-decidable: a proof exists, but search may not terminate.

The trade-off starts here. Quantifiers buy composition; they cost a decision procedure. Every practical language is a fragment chosen to get one back.
S/V · Lecture 02
01 · The toolkitLecture 02 · The symbolic world

Recursion without functions

Datalog: the tractable fragment.

% 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).

No function symbols → finite Herbrand universe → the least fixpoint terminates. Recursion is built in; negation is stratified.

Data complexity is PTIME. Combined complexity can be exponential in the program, but the data is the part that grows.

This is the language of the lab.

In+1 = In ∪ { head(r)σ | body(r)σ ⊆ In }
(1)
S/V · Lecture 02
01 · The toolkitLecture 02 · The symbolic world

Generate, define, test

ASP: a language for combinatorial search.

% generate { digit(R,C,D) } :- cell(R,C). % define :- digit(R,C,D1), digit(R,C,D2), D1 != D2. % test: rows, columns, boxes :- clue(R,C,D), not digit(R,C,D).

Guess a candidate, define the consequences, eliminate the candidates that violate a constraint. The stable models that survive are the answers.

Expressive and concise. Deciding whether an answer set exists is NP-complete in general; the solver does the search.

The price is tractability, not clarity.

ASP is not a database. It is a declarative encoding of a search problem. The same pattern covers configuration, scheduling, and puzzles.
S/V · Lecture 02
01 · The toolkitLecture 02 · The symbolic world

Ontologies and expert rules

Two practical languages.

Description logic

Concepts denote sets, roles denote relations. TBox: Parent ⊑ Person; ABox: Parent(alice). OWL is the standard.

EL is PTIME; ALC is ExpTime-complete. Decidable by design.

Production rules

IF fever AND rash THEN consider measles. A working memory, a match–conflict–execute cycle, and a rule base.

Deployable; the maintenance cost is the model.

The pattern: choose the weakest language that expresses the domain. A stronger language buys expressivity and costs decidability, maintenance, or both.
S/V · Lecture 02
02 · InferenceLecture 02 · The symbolic world
02 / 08

How a conclusion is forced.

Two directions, one operation, and a ladder of complexity.

S/V · Lecture 02
02 · InferenceLecture 02 · The symbolic world

Data-driven or goal-driven

Two directions to the same proof.

Forward

Start from facts; fire every rule whose body is satisfied; add conclusions; repeat to the fixpoint.

Computes every consequence. Good when facts change and many queries share them.

Backward

Start from the query; find rules whose head matches; recursively prove the body. Prolog's SLD resolution.

Computes only what the query needs. Good when the query is rare and the database is large.

ForwardBackward
Starts fromthe factsthe query
Computesall consequencesonly what the query needs
Good whenfacts change; many queries share workqueries are rare; the database is large
CanonicalDatalog fixpointProlog SLD resolution
The same logic, different cost. Direction is an engineering choice; the semantics is shared.
S/V · Lecture 02
02 · InferenceLecture 02 · The symbolic world

The operation under the hood

Bind, then resolve.

query ancestor(alice, dave) rule ancestor(X, Y) :- parent(X, Z), ancestor(Z, Y). unify X = alice, Y = dave body parent(alice, Z), ancestor(Z, dave) candidate Z = bob
C1 ∨ l,   C2 ∨ ¬l   ⟹   C1 ∨ C2
(2)

Resolution is sound and refutation-complete. It is not a decision procedure: the search space can be infinite.

S/V · Lecture 02
02 · InferenceLecture 02 · The symbolic world

What “no” means

The assumption behind a negative answer.

Closed world

If it cannot be derived, it is false. The default for databases and Datalog.

Negation as failure; stratification keeps the fixpoint unique.

Open world

If it is not known, it is unknown. The default for ontologies and medicine.

A missing fact is not a negative fact. The logic of the web is open.

QueryClosed worldOpen world
parent(alice, zed)?false — not derivableunknown — not recorded
eligible(carol)?false unless a rule derives itunknown unless a rule derives it
Ask this first. The same query can return “false” or “unknown” depending on an assumption that is often left implicit.
S/V · Lecture 02
02 · InferenceLecture 02 · The symbolic world

The honest price list

What you can decide.

LanguageQuestionComplexityWhat it means
PropositionalSatisfiable?NP-completeSearch, but a finite one.
First-orderEntailed?UndecidableA proof may exist; finding it may not terminate.
DatalogDerivable?PTIME (data)Recursion, with a guaranteed fixpoint.
ASPAnswer set?NP-completeDeclarative search over candidates.
ALCSubsumption?ExpTime-completeOntology reasoning, decidable by design.
STRIPSPlan ≤ k?PSPACE-completePlanning is harder than SAT in the worst case.

Worst case, not typical case. Modern solvers and planners are fast on real instances; the ladder explains why there is no free lunch.

S/V · Lecture 02
03 · Search & planningLecture 02 · The symbolic world
03 / 08

Reasoning as a path.

A proof is a path through clauses; a plan is a path through states.

S/V · Lecture 02
03 · Search & planningLecture 02 · The symbolic world

The workhorse

A*: the heuristic is the model.

f(n) = g(n) + h(n)
(3)

g is the cost so far; h estimates the rest. Expand the smallest f.

If h never overestimates, A* is optimal. If h is consistent, graph search never reopens a closed node.

start goal
A relaxed problem gives an admissible heuristic: ignore the obstacles, count the grid steps.
A heuristic is a tiny symbolic model. The abstraction you choose determines what the search can prove.
S/V · Lecture 02
03 · Search & planningLecture 02 · The symbolic world

The action schema

State, precondition, effect.

; STRIPS action stack(x, y) Pre: clear(x), holding(x), clear(y) Add: on(x, y), clear(x) Del: holding(x), clear(y) ; a state is a set of atoms { on(c, a), clear(b), clear(c), holding(none), ... }

Forward search: from the initial state, apply actions, test the goal.

Backward search: from the goal, regress over actions, test the initial state.

Partial order: a plan as actions plus ordering constraints and causal links; leave irrelevant actions unordered.

The frame assumption is built into the representation: everything not in Del persists. That is convenient — and exactly the assumption that breaks in an open world.
S/V · Lecture 02
03 · Search & planningLecture 02 · The symbolic world

The representational bill

Frame, ramification, qualification.

Frame

What stays the same? The model must account for persistence, not just change.

Ramification

What follows indirectly? The plan moves a cup; the water spills; the table is wet.

Qualification

What else must be true? The list of conditions is never complete.

ProblemA concrete caseWhat the model must say
FrameMove the cup: it is still on the table next to it.Everything not deleted persists.
RamificationThe cup moves; the water spills; the table is wet.The indirect effects, not just the direct one.
QualificationThe cup is open, not glued down, not already full.Which conditions are assumed, and which are checked.

A planner that ignores them is fast and wrong. A planner that encodes them all is correct and unmaintainable. The middle is an engineering choice.

S/V · Lecture 02
03 · Search & planningLecture 02 · The symbolic world

Modern planners, modern caveats

Heuristics, compilation, and LLMs.

Delete relaxation: assume deletes do not happen; the relaxed plan is a lower bound. hadd sums costs; hmax takes the max.

Landmarks: facts that every plan must achieve; they prune the search.

SATPlan: compile a bounded plan to SAT; a satisfying assignment is a plan.

LLM + planner: the model proposes; the planner checks and repairs. The guarantee comes from the planner, not the model.

Bounded STRIPS planning is PSPACE-complete. The worst case explains why planning is a service, not a free function call. The benchmarks are task-specific; read them.
S/V · Lecture 02
04 · Knowledge & expertsLecture 02 · The symbolic world
04 / 08

The model is the bottleneck.

The inference engine is the easy part; someone has to write the world down.

S/V · Lecture 02
04 · Knowledge & expertsLecture 02 · The symbolic world

The expert-system template

Rules, certainty, and a benchmark.

; MYCIN-style rule IF the organism is gram-negative AND the patient has a fever THEN there is suggestive evidence (0.6) that the organism is E. coli

Forward chaining over a few hundred rules. The certainty factor is not a probability; it is an ad hoc number with a combination formula.

MYCIN matched specialists on its benchmark. It also exposed the maintenance problem: a rule base is a program that the domain expert cannot debug.

The certainty factor is the warning. A confidence number that is not calibrated can look like a probability and behave like a guess.
S/V · Lecture 02
04 · Knowledge & expertsLecture 02 · The symbolic world

The long tail

Common sense is not a list.

Cyc is a decades-long attempt to encode common sense as an ontology and a rule base. The artifact is enormous; the coverage is uneven.

ConceptNet is a lighter, crowd-built graph of everyday relations. Broad, noisy, useful.

The problem is not storage. It is defaults, exceptions, and context: birds fly, except penguins; a cup holds water, unless it is upside down; “near” depends on the task.

The bottleneck is the model, not the engine. A faster inference engine does not tell you that a penguin is a bird that does not fly.
S/V · Lecture 02
05 · The balanceLecture 02 · The symbolic world

The honest scorecard

Strong where the world is discrete.

DimensionStrengthWeakness
RepresentationCompositional, inspectableHand-built vocabulary and model
InferenceSoundness/completeness guaranteesBrittle under uncertainty; intractable
DataLearns from rules, not examplesCannot acquire rules from pixels
PerceptionClean interface to symbolsCannot ground its own symbols
MaintenanceEvery rule is reviewableEvery rule must be maintained

Not “symbols lost.” The verdict is that symbols alone cannot perceive, and networks alone cannot verify.

S/V · Lecture 02
06 · The bridgeLecture 02 · The symbolic world
06 / 08

Symbols as a language for constraints.

Not a rival to learning — a contract around it.

S/V · Lecture 02
06 · The bridgeLecture 02 · The symbolic world

The same logic, five jobs

Where the symbol goes.

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 searchProposal plus symbolic searchAlphaGeometry's auxiliary constructions
Logic as verifierA monitor that checks a candidateA planner validating an LLM's plan

The question is not “symbols or vectors?”. It is “which job is the symbol doing, and what does it guarantee?”.

S/V · Lecture 02
06 · The bridgeLecture 02 · The symbolic world

Interactive · watch the fixpoint

Recursion, one round at a time.

alice bob carol dave eve frank parent parent parent parent parent

Press “Given” to see the base facts. Each round adds ancestors that follow from the previous round.

S/V · Lecture 02
07 · Six systemsLecture 02 · The symbolic world

One tradition, six lessons

The gallery, in miniature.

None of these has a neural component. Each is a clean instance of a mechanism that neurosymbolic systems reuse.

S/V · Lecture 02
08 · RecapLecture 02 · The symbolic world

The four moves

What to carry forward.

01 · Place

Put the language on the ladder. Expressivity buys power; decidability buys guarantees.

02 · Trace

Unify, resolve, or chain. The substitution is the explanation; the proof is the answer.

03 · Price

Frame, ramification, qualification. The model is the bottleneck, not the engine.

04 · Contract

Use the symbol as a loss, architecture, data, search, or verifier — and say what it guarantees.

The model is the bottleneck.

S/V · Lecture 02
08 · RecapLecture 02 · The symbolic world

Next · hands-on

Run the engine.

Open the Datalog lab. Step the fixpoint. Break the stratification. Read the proof tree: every answer comes with its reason.

Lab 02 · Datalog → open the lab

S/V · Lecture 02
Speaker notes