Stanford CS221 | Autumn 2025 | Lecture 15: Logic I — Annotated Lecture Notes & Key Takeaways

Course Information

Institution: Stanford

Original Course: Stanford CS221 | Autumn 2025 | Lecture 15: Logic I

Instructor Bio: This lecture is delivered by Percy Liang, Associate Professor of Computer Science at Stanford University and core faculty of the Stanford Institute for Human-Centered Artificial Intelligence (HAI). Percy Liang leads the Stanford Natural Language Processing Group and the Center for Research on Foundation Models (CRFM). His research spans the theoretical foundations and practical systems of artificial intelligence, including machine learning, natural language processing, AI alignment, and rigorous model evaluation. He received his PhD in Computer Science from the University of California, Berkeley and his BA in Mathematics from Harvard University. His work has been recognized with the NSF CAREER Award, Google Faculty Research Award, and multiple best paper awards at top-tier AI conferences. He has taught CS 221 at Stanford for over a decade, shaping foundational AI education for thousands of students.

Course Description: This lecture opens the logical reasoning module, introducing formal logic as a framework for symbolic knowledge representation and deductive reasoning. It covers propositional logic syntax and semantics, logical entailment, and the boolean satisfiability (SAT) problem. The lecture also explains resolution theorem proving and the DPLL algorithm for solving SAT problems, and discusses how logical reasoning enables AI systems to draw sound conclusions from explicit knowledge bases.

If you skipped the last technical lecture before CS221's AI-and-society section, here's the honest summary: the course spends an hour and change building propositional logic​ from the ground up, and it does so in a way that's less about truth tables than you'd expect. The lecturer's framing is that logic is best understood as a language, and that the interesting part isn't the symbols — it's the three-way split between what you're allowed to write, what those strings mean, and what you can derive from them. He also spends a surprising amount of time connecting this material back to the Bayesian networks unit that came before it. A lot of the lecture is definitions, and he says so up front: each individual term is simple, but there are many of them.
 

Logic arrives last, and the lecturer knows that's strange

 

He opens by acknowledging the awkward placement. Logic was, as he puts it, the dominant paradigm in AI before the 1990s — the thing people pictured when John McCarthy coined the term "AI" — and the course is only getting to it now, right when you'd expect a unit on language models. The reason it fell out of favor gets stated plainly: logic is deterministic, so it has no native way to handle uncertainty, and it never really learned to leverage data. Machine learning solved both problems, which is why the field moved on.
 

The defense he offers is narrow but sharp. Logic buys you expressivity in a compact form. His illustration is a piece of elementary algebra: if a + b = 10 and a − b = 4, what is a? Someone shouts seven (1:26), and the point isn't the answer — it's the method. Nobody enumerated candidate values for a and b. You added the equations, got 2a = 14, divided by two. That's symbolic manipulation solving a problem with infinitely many candidate assignments in your head, and it's nothing like the search-based reasoning the course spent its first weeks on.
 

Then comes the argument for why not just use natural language. Two inferences get put side by side. A dime is better than a nickel, a nickel is better than a penny, therefore a dime is better than a penny (4:21) — obviously fine. But a penny is better than nothing, nothing is better than world peace, therefore a penny is better than world peace. Equally valid on the surface, obviously absurd. Natural language, he says, is slippery: you can't just substitute words and hope for the best.
 

I wanted more here. He throws the second example out and moves on without diagnosing it, and I think the lesson lands harder if you name the trap — "nothing" is doing two completely different jobs in the two premises, and once you see that you also see why a formal language with fixed symbols is worth the trouble. The joke does the work of an argument, and the argument was the more interesting thing.
 

The taxonomy that follows is quick: natural languages are informal, programming languages like Python and C++ are formal, and logical languages are formal too. What I appreciated was the aside that there isn't one logic. He mentions description logics purely as an example of a family member the course won't cover, which quietly sets up the idea that choosing a logic is a design decision with trade-offs.
 

Propositional logic: syntax is not meaning

 

Every logic, in his account, has three ingredients (5:52): syntax, which defines legal formulas; semantics, which says what those formulas mean; and inference rules, which let you produce new formulas from old ones. He admits this won't make sense yet and promises it will by the end of the hour.
 

The syntax/semantics distinction gets the clearest treatment of the whole lecture. Syntax asks what counts as a valid expression; semantics asks what it denotes. Two examples carry it. First, 2 + 3 and 3 + 2 are different syntax with identical meaning. Second, the string 3 / 2 means 1 under Python 2.7 semantics and 1.5 under Python 3 — same syntax, different meaning, and a reliable source of bugs. The takeaway he draws is slightly philosophical: nothing inside the characters "3 / 2" determines what they mean. Meaning has to be supplied from outside.
 

Propositional syntax is then defined in about two minutes. You start with atomic symbols — any identifier, he suggests P, Q, rain, wet — and deliberately postpone assigning them meaning. You get five connectives: negation, conjunction, disjunction, implication, and equivalence. Formulas are built recursively, and the closure clause matters: nothing else is a formula. So a bare juxtaposition with no connective isn't legal, "+" isn't a connective, and there are no parentheses in this particular logic. Those strings might be fine in some other logic, which is his way of reinforcing that the rules are a choice.
 

Semantics starts with the model (13:17), and he stops to flag the terminology collision: a model here is not a machine learning model. It's a complete assignment of truth values to every propositional symbol, also written as a world. Three symbols give you eight possible worlds, and the mental picture to hold is that the full set of models is every way the world could be.
 

Linking the two is the interpretation function, which takes a formula and a world and returns a boolean. He walks a concrete case: the formula (¬a ∧ b) = c evaluated in a world where a and b are true and c is false. Because formulas are built recursively, you can take them apart recursively — the evaluation unfolds as a tree, with atomic symbols as base cases that just look up their value in the world. The example returns true. He shows the same thing implemented as code, and what the code makes obvious is that the evaluator is just a recursive case split — one branch per connective, each recursing into sub-expressions and then applying a boolean operation on the way back up. If you've written an interpreter or a compiler pass, this is familiar territory; he explicitly acknowledges the parallel. It also leads to the claim I found most interesting in this stretch: you could define whatever language you like with whatever symbols you like, and as long as you also define an interpretation function, you have a logic.
 

The object he actually wants to work with, though, isn't the interpretation function — it's the set of worlds where a formula comes out true (20:47). That's the semantics of a formula, in his sense. The formula rain ∨ wet picks out three of the four worlds; rain ∧ wet picks out one. This is where the compactness point pays off: two symbols give four worlds, a hundred symbols give 2¹⁰⁰, and a very short formula can still carve out an astronomical set of possibilities.
 

Knowledge bases and the three ways a new fact can land

 

A knowledge base is just a set of formulas (25:43) — a growing list of things you take to be true. Its semantics is the set of worlds satisfying every formula in it, which you can compute either by intersecting the model sets of the individual formulas or by conjoining them into one big formula. With the KB {rain, rain → wet}, the result is a single surviving world: raining and wet. He works through the implication case carefully, because it's where people slip — rain → wet rules out exactly one world, the one where it's raining and not wet. It says nothing about whether it's actually raining.
 

From there the organizing idea is that adding facts can only shrink your set of possible worlds. More facts, fewer candidate worlds, more certainty. A knowledge base behaves like a bundle of constraints, and the question he poses is how much the set shrinks when you add a formula.
 

Three answers (31:41). If the model set doesn't shrink at all, the KB entails the formula — in every world consistent with what you know, the formula already holds. If it shrinks all the way to the empty set, you have a contradiction. Anything in between is contingency: you learned something, but you haven't broken anything. He also notes the tidy duality that KB contradicting f is the same as KB entailing ¬f, and makes a point I liked: when a contradiction shows up, the logic takes no position on whether the KB or the new formula is at fault. Sets of worlds don't have opinions.
 

The payoff is an interface with two operations (39:23). Ask poses a yes/no question and returns yes, no, or I don't know — mapping exactly onto entailment, contradiction, and contingency. Tell adds a formula and reports back in one of three registers — that the fact was already implied, that it flatly conflicts with what's stored, or that it's genuinely new. Under the hood both operations do the same comparison; the difference is which verdict gets surfaced and whether the KB gets updated.
 

Someone also asks why ask and tell are separate operations at all if they perform the same comparison. The answer is unglamorous: it's an interface choice. Sometimes you want to interrogate a knowledge base, sometimes you want to add to it, and the only real behavioral difference is that tell commits the change when the verdict is contingency.
 

The fiction aside is worth remembering for the exam. A tell that succeeds doesn't certify the new fact as true — it only certifies consistency. Start from an empty knowledge base and you can add anything you like, which, as he says, is more or less how fiction works.
 

Two student questions produce the best material in this stretch. Asked whether a KB is basically a database, he agrees, then gets a follow-up about what happens when a contradiction means the KB itself is wrong. His answer is refreshingly candid: the implementation assumes the KB is correct, and if you drop that assumption you have real work to do, because you don't know which formulas to retract and there may be several minimal sets you could remove. Propositional logic has no notion of time, and it's monotonic (49:22) — the model set only ever shrinks, unlike probabilities, where adding evidence can move a number up or down. His practical suggestion is to surface the conflicting formulas to a user and let them decide. The analogy he reaches for is failing unit tests: the code could be wrong, or the test could be outdated, and nothing in the artifact itself tells you which.
 

From enumerating worlds to SAT solvers — and back to symbols

 

The bridge back to Bayesian networks (51:29) is the most satisfying part of the lecture. Random variables map onto propositional symbols. Assignments map onto models. A joint distribution is then just a probability distribution over possible worlds, evidence plays the role of the knowledge base, and the query plays the role of the asked formula. Conditional probability becomes: sum the probability of every world where both KB and f hold, divide by the sum over worlds where KB holds.
 

Two differences matter. In a Bayesian network, evidence and queries are always of the form variable = value; in propositional logic they can be arbitrary formulas, so you can condition on a disjunction like rain-or-snow without inventing a new variable. And probabilities replace the hard yes/no/I-don't-know with a graded number — 90% instead of a shrug. He gestures at the whole research line on probabilistic logics and explicitly declines to go there.
 

One small thing that helped me: the rain and wet pair is used as the running example for essentially every concept in the lecture, from atomic symbols through knowledge bases to the SAT encoding. Once you notice that, the material is much easier to hold in your head, because each new definition is a new operation on the same two symbols rather than a new scenario.
 

The efficiency problem then arrives on schedule. Everything so far has been implemented by enumerating every possible world, which is exponential by construction. So he reframes all three outcomes in terms of satisfiability (57:44): a KB is satisfiable if it has at least one model. Checking KB ∪ {¬f} for satisfiability tells you whether KB entails f — if assuming the negation produces no surviving worlds, f must already follow, which is just proof by contradiction in a different costume. You need a second call on KB ∪ {f} because satisfiability returns one bit and there are three possible verdicts.
 

This is where the lecture quietly pulls a bait-and-switch that I think is worth naming. Nearly an hour is spent building intuition by enumerating worlds, and then he says the enumeration is only a proof of concept and that nobody implements it that way. Real systems hand the formula to a model checker (1:01:13) — he uses Z3, an SMT solver — which answers satisfiable or not, and hands back a witness assignment as an existence proof when the answer is yes. SAT solving is NP-complete in the worst case, but decades of engineering have produced heuristics that routinely handle instances with hundreds of thousands of variables. Both halves of that statement are true and they pull against each other, and he doesn't really reconcile them.
 

The last stretch returns to symbols. Inference rules are purely syntactic: premises in, conclusion out, no meaning consulted. Modus ponens (1:05:27) is the example — from P and P → Q derive Q — and you apply rules repeatedly until the knowledge base stops changing, which lets derived facts feed into further derivations. He chains rain, rain → wet, and wet → slippery to get slippery.
 

Soundness and completeness (1:09:45) connect that syntactic game back to the semantic one, and the image he uses is a glass filling with water. Truth is the glass; everything inside it is true. Soundness means everything you derive stays inside — nothing but the truth. Completeness means you eventually fill the glass — the whole truth. His unsound example is the classic blunder of reversing an implication: from wet and rain → wet, inferring rain (1:12:16). Checking the model sets shows the intersection isn't contained in the conclusion, so the rule leaks outside the glass.
 

Where the lecture felt thin, and what actually sticks

 

The weakest moment for me was the natural-language opening. The penny example is funny, and it does establish that informal inference is unreliable, but it's doing the work of a much stronger claim — that we need formal languages — without ever arguing it. A skeptic could reply that language models handle the second inference perfectly well, and the lecture never engages that objection, even though it raises the language-model question itself two minutes earlier.
 

I'd also flag the tell() design as under-defended. Assuming the knowledge base is always right is a big assumption, and while he admits belief revision gets complicated, the honest version of that problem is a whole subfield. If you're taking this for credit, that's the seam where an exam question is most likely to be hiding.
 

The through-line is that triangle again: syntax, semantics, inference rules. Entailment is a semantic relation, derivation is a syntactic one, and soundness and completeness are the two bridges between them — neither of which you get for free. He closes by insisting that none of the vocabulary is specific to propositional logic; it all generalizes, and the next lecture takes it to first-order logic.
 

If there's a single sentence worth writing on your hand, it's this one: in propositional logic a formula is only a piece of syntax, and its meaning is the set of possible worlds it leaves standing. Everything else in the hour — models, entailment, satisfiability, the yes/no/I-don't-know responses — is machinery built on top of that one idea.
 

Content Disclaimer:

This article is for general reference only and does not constitute professional R&D guidance, production process advice or quality certification. All material performance data has specific test premises; readers should verify parameters against actual equipment and working conditions.