Unit 1: Proof Techniques

This is an archived version of this module from Winter 2024-25.

This unit covers:

• strategies for mathematical proofs
• mathematical induction
• loop invariants

Learning outcomes

1. Know logical proof strategies for proving implications, set inclusions, set equality, and quantified statements.
2. Be able to use mathematical induction in simple proofs.
3. Know techniques for proving termination and correctness of procedures.

Material

• slides

• lecture notes

• Video 0-1 (2024-10-15): §1.1 Random shuffle motivation

• Video 0-2 (2024-10-15): §1.2 Proof templates, random shuffle motivation

• Video 0-3 (2024-10-15): §1.3 Mathematical induction, Towers of Hanoi

• Video 0-4 (2024-10-15): §1.4 Correctness proofs

Further reading and sources

A much more in-depth introduction to proof techniques, with many examples and exercises can be found, e.g., here:

• Velleman: How to Prove It, 2nd ed. (2006), Cambridge University Press

The loop invariants are the center piece of Hoare Logic for program verification. More background on Hoare Logic is given for example here:

• Gordon: Lecture Notes on Hoare Logic

---

Unit 0  ⋅  Syllabus  ⋅  Unit 2