Reading Stanford CS103 Mathematical Foundations of Computing
A lecture-by-lecture reading of Stanford CS103: discrete mathematics, logic, proofs, sets, computability, and the shared language they provide for later CS courses.
CS103 is Stanford's mathematical foundations of computing course: the first half teaches proof writing through sets, logic, graphs and induction, and the second half covers finite automata, Turing machines, decidability and P vs NP. Slides, problem sets, starter files and the homegrown handouts are all public, and the autograded problems can be checked locally; solutions, practice exams and lecture recordings sit behind Stanford login.
This lecture identifies exactly when an implication is false, then turns quantified negation, contraposition, and contradiction into checkable proof tools.
Propositional logic abstracts English statements into Boolean variables, then uses truth tables to check connectives, translation direction, and equivalences.
This lecture extends propositional logic into a language about objects: distinguish constants, predicates, functions, and propositions, then express some and every with existential and universal quantifiers.
Translate natural language one layer at a time: identify universal and existential forms, then handle quantifier order, negation, restricted quantifiers, and uniqueness.
A function is more than a formula: domain, codomain, totality, and determinism are essential, while the quantifiers defining involutions, injections, and surjections dictate their proofs.
This lecture uses surjections and a proof about birds to separate assuming from proving, then shows that involutions are injective and surjective and carries those ideas into function composition.
Two sets have equal cardinality when a bijection pairs their elements; Cantor's diagonal set defeats every function from S to its power set by constructing a value it misses.
Starting with walks, paths, cycles, and components, this lecture proves that a graph or its complement is connected and develops the pigeonhole principle through degrees and monochromatic triangles.
Use the generalized pigeonhole principle to force a monochromatic triangle at a six-person party, then solve a movie-preference puzzle through average load and contradiction.
Induction is not a list of checked examples: establish a true starting point, prove that an arbitrary true case transmits truth to the next case, and invoke the induction principle.
This lecture connects why begin with a weak computer to from device behavior to a state machine, following the official examples and proof obligations.
This lecture connects the dfa definition connects the first half of cs103 to regular means that some dfa exists, following the official examples and proof obligations.
This lecture connects the automata ladder measures power with languages to dfa transition tables, following the official examples and proof obligations.
This lecture connects from closure properties to a language syntax to regex is mathematics, not one library, following the official examples and proof obligations.
This lecture connects four equivalent descriptions of regularity to the precise finite-memory intuition, following the official examples and proof obligations.
This lecture connects a quick quantifier audit for recognizers and deciders to why every decision problem can be represented as a language, following the official examples and proof obligations.
This lecture connects the lava diagram's two classification tasks to the deck's operational reading of rice's theorem, following the official examples and proof obligations.
This lecture connects decidable does not mean feasible to efficiency requires choosing a resource, following the official examples and proof obligations.