Course Outline


Lecturer: Gerwin Klein
Email: gerwin.klein at
Phone: +61 2 8306 0491
Office: 521, Level 5, Building L5
Consultations: by appointment

Course Goal

To educate students in advanced topics in software verification. Topics include higher order logic, natural deduction, lambda calculus, term rewriting, data types and recursive functions, induction principles, calculational reasoning, mathematical proofs, decision procedures for a variety of logical domains, and proofs about programs.

Parallel Teaching


Course Preequisites

The course is intended of 4th year or post graduate students. Second and third year students can participate with permission of the lecturer.

Course Exclusions



  • Lecture: the lecture will cover the following main topics: higher order logic, natural deduction, lambda calculus, term rewriting, data types and recursive functions, induction principles, mathematical proofs, and proofs about programs.
  • Tutorials: there are no tutorials for this lecture
  • Assignments: there will be three assignments. Penalty for late submission of assignments will be 4% (of the worth of the assignment) subtracted from the raw mark per day of being late. In other words, earned marks will be lost. For example, assume an assignment worth 25 marks is marked as 20, but had been submitted two days late. The late penalty will be 2 marks, resulting in a mark of 18 being awarded. No assignments will be accepted later than one week after the deadline.

Preliminary Course Schedule

Week Topic
1 Introduction and Admin, Lambda Calculus
2 Typed Lambda Calculus, Higer-Order Logic
3 Natural Deduction in HOL and Isabelle
4 Term Rewriting
5 Term Rewriting and Functional Programming in Isabelle
6 Sets and Rule Induction
7 Datatypes and Recursion
8 Calculational and Monadic Reasoning
9 Imperative Program Verification and Hoare Logic
10 Separation Logic
11 Proof Carrying Code, Generated Correctness Proofs
12 Refinement

Course philosophy and teaching strategies

The learning focus in this course is primarily on lectures and assignments. The first two assignments are intended to give early feedback and to test your preparedness for the final exam. While marks are assigned to the assignments, their primary purpose is to give you concrete tasks with deadlines to help you structure your learning.


  • Assignments: There will be three written assignments. Assignment 1 will be due in week 4, assignment 2 in week 7, and assignment 3 in week 10.
  • Exam: The final exam will be a take-home exam with an Isabelle/HOL proof and questions on the lecture material.
  • Final Mark: the class mark consists of the assignments (each 1/3). The arithmetic mean of the class mark and exam mark is used to determine the final mark. To pass the course, a minimum of 40% is necessary in each component. If both the class mark and the exam mark are greater or equal to 40%, the final mark will be (class mark + exam mark) / 2 otherwise minimum ((class mark + exam mark) / 2, 44)

Text and Reference Books

See the page on reading material.

Continual course improvement

Feedback from the last evaluation of this course was positive and we intend to maintain the same style and content. The one not entirely positive aspect of distance education via video link is not part of the course this session.

Further information

  • Students enrolled in this course are expected to attend all classes.
  • Plagiarism policy.
  • The use of School of Computer Science and Engineering computing laboratories is subject to rules described in the Yellow Form, which you acknowledge (electronic) receipt of when you receive your computing account. The Yellow Form also outlines what to do in case illness or misadventure that affects your assessment, and supplementary examinations procedures within the School of Computer Science and Engineering.
  • UNSW Occupational Health and Safety policies and expectations.
  • Equity and Diversity.