Logical Foundations of Programming, Spring 2004

Prerequisites

• college algebra
• basic imperative programming skills

Knowledge and skills that should be acquired in this course

Mastery

1. understanding the syntax and semantics of first-order logic, with propositional logic as an important special case
2. understanding what it means for a sentence to be a tautology, and what it means for a sentence to be a consequence of other sentences (thereby understanding what constitutes a logically valid argument)
3. understanding the notion of a counterexample
4. employing basic methods of proof, including proof by cases, proof by contradiction, and (not least) proof by induction
5. constructing proofs in the natural deduction calculus
6. converting a propositional logic formula into equivalent but more handy formulas (such as conjunctive normal form)
7. verifying the correctness of simple while-programs

Familiarity

• appreciating issues that arise when attempting to translate natural language into first-order logic
• computing invariants for while-statements
• being exposed to a case study of algorithm design and verification