Unit 0: Admin & Proof Techniques

This is an archived version of this module from Spring 2022.
Click here for the current iteration.

This unit covers:

• organization of the module (administrative part)
• 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 on administrativa
• slides on proof techniques
• lecture notes on administrativa

• lecture notes on proof techniques

• Video 0-1 (2022-01-31): Welcome, teaching mode, overview, assessment, Campuswire, video presentation, prior knowledge survey

• Video 0-2 (2022-02-03): §0.1 Proof templates

• Video 0-3 (2022-02-03): §0.2 Mathematical induction

• Video 0-4 (2022-02-03): §0.3 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

---

Syllabus  ⋅  Unit 1