Stanford CS221 | Autumn 2025 | Lecture 15: Logic I
TL;DR
This lecture introduces logic as a formal language for knowledge representation and reasoning, contrasting it with probabilistic methods and natural language. It establishes the foundational framework of syntax, semantics, and inference rules, then dives into propositional logic's mechanics including formulas, models, and interpretation functions.
🧠 Logic in AI Context 3 insights
Historical dominance before machine learning
Logic dominated AI research before the 1990s starting when John McCarthy coined the term AI, but declined due to its inability to handle uncertainty or leverage large datasets.
Irreplaceable expressivity advantage
Unlike search or probabilistic reasoning, logic provides uniquely compact and expressive knowledge representation that enables powerful symbolic manipulation similar to algebra.
Natural language ambiguity problems
Natural language proves too slippery for reliable automated reasoning, as demonstrated by logical fallacies where transitivity fails due to linguistic ambiguity.
⚙️ Three Components of Logic 3 insights
Syntax defines valid formulas
Syntax specifies the formal rules for constructing valid expressions or sentences within the logical language, independent of their meaning.
Semantics provides interpretation
Semantics assigns meaning to syntactic expressions, determining truth values and distinguishing cases like Python 2.7 versus Python 3 evaluating 3/2 differently.
Inference rules enable derivation
Inference rules allow generation of new valid formulas from existing ones, creating a mechanism for logical reasoning and proof construction.
🔣 Propositional Logic Structure 2 insights
Atomic propositions as variables
Propositional logic builds from atomic formulas or symbols like P, Q, rain, or wet that act as variable names without inherent meaning until interpreted.
Recursive formula construction
Complex formulas are built recursively using five connectives: negation, conjunction, disjunction, implication, and biconditional equivalence.
🌍 Semantics and Models 3 insights
Models represent possible worlds
In logic, a model is a complete assignment of truth values to all propositional symbols, representing one possible state of the world among exponentially many possibilities.
Interpretation function bridges syntax and semantics
The interpretation function I(f,w) recursively evaluates a formula's parse tree against a specific model to return true or false.
Formula models define truth sets
M(f) denotes the set of all models where a formula evaluates to true, demonstrating how compact logical expressions can represent vast sets of possible world states.
Bottom Line
Logic provides a formal language for knowledge representation through three core components—syntax for structure, semantics for meaning via models and interpretation functions, and inference rules for reasoning—enabling compact expression of complex world states that natural language cannot reliably capture.
More from Stanford Online
View all
Stanford MS&E435 Economics of the AI Supercycle | Spring 2026 | Applications, Coding AI
Vercel founder Guillermo Rauch explains how AI coding agents have expanded the software development market by 10-100x, driving a fundamental shift from traditional web services to 'agentic infrastructure' where tokens replace pixels as the primary commodity and deployment becomes the critical value creator.
Stanford MS&E435 Economics of the AI Supercycle | Spring 2026 | Building AI Factories
Crusoe Energy CEO Chase Lockmiller explains how AI data centers represent history's second-largest infrastructure investment, driven by the economic potential of scalable 'digital labor.' He reveals Crusoe's strategy of building massive AI factories in stranded-power locations like Abilene, Texas, to overcome the industry's critical bottleneck: energized data center capacity.
AI in Healthcare Series: Inside the Rise of AI in Healthcare, Open Evidence and Cyber Risks
Former U.S. Chief Data Scientist DJ Patil warns that healthcare systems are dangerously unprepared for AI-enabled cyberattacks from nation states, while simultaneously seeing rapid democratization of medical knowledge through tools like Open Evidence that are fundamentally reshaping the doctor-patient relationship.
Stanford CS153 Frontier Systems | Scale, AGI, and the Future of Everything
Sam Altman explains how AI has fundamentally altered startup economics, enabling small teams to achieve unprecedented scale, while sharing OpenAI's journey from research lab to product company and arguing that pushing systems beyond conventional scaling limits often reveals emergent properties that consensus thinking misses.