Stanford CS221 | Autumn 2025 | Lecture 16: Logic II

Scalability breakdown with generalizations

Representing "all students know arithmetic" requires manually listing every student (Alice, Bob, etc.), creating exponentially large formulas that are impractical for real-world domains.

Missing structural elements

Propositional logic treats statements like "Alice knows arithmetic" as monolithic symbols, lacking the machinery to represent internal objects, relationships, or variables needed for abstraction.

Terms denote objects, formulas denote truth

Terms (constants like Alice, variables like x, functions like father(x)) represent objects, while formulas (predicates applied to terms) evaluate to true or false.

Predicates vs. functions

Functions map terms to other terms (father(Alice) returns an object), whereas predicates map terms to boolean values (Student(Alice) returns true/false).

Strict type conventions

Lowercase conventions indicate terms representing objects, while uppercase indicates predicates and formulas representing truth values, preventing ill-formed expressions like Student(Arithmetic).

Universal and existential quantification

Quantifiers (∀ for all, ∃ for exists) allow expressing general rules like "for all x, Student(x) implies Person(x)" without enumerating every individual in the domain.

Compact complex representations

First order logic enables concise encoding of mathematical conjectures and real-world facts (e.g., Goldbach's conjecture) that would require infinite propositional symbols otherwise.

Inference foundations remain consistent

First order logic maintains the same semantic framework as propositional logic—models, interpretation functions, entailment, and satisfiability—while extending representational capacity.