Reading Material

Topic Reference
Propositional Logic [1] Chs: 1.1, 1.2, 1.3 and 1.5
[2] Ch. 3
[3] Ch. 2
[4] Chs 1.1 and 1.2
[5] Chs 2.1, 2.2, 2.3, 2.4, 2.5, and 3.2
Logic as Algebra [1] Chs: 1.4, 1.6, 2.1 and 2.4
[2] Ch. 3
[3] Ch. 2
[4] Chs 1.1 and 1.2
[5] Chs 2.1, 2.2, 2.3, 2.4, 2.5, and 3.2
First Order Logic [1] Chs: 2.2, 2.3, 2.4, 2.5, 3.1, 3.2 and 3.3
[2] Ch. 4
[3] Ch. 3
[4] Chs 1.3 and 1.4
[5] Ch. 2.6
[7] Chs: 12 and 13
All About Induction [1] Ch. 3.1
[2] Ch. 5.1
[3] Chs 5.2, 5.3 and 5.6
[4] Ch. 3.5
[5] Chs 3.4 and 3.5
Induction for DataTypes [1] Chs: 3.3
Hoare Logic (partial) [1] Chs 9.4.1, 9.4.2, 9.4.3 and 9.5
[8] Chs. Hoare Logic, Part I and Hoare Logic, Part II
[9]
Axiomatic Basis for Computer Programming
Assigning meaning to Programs
Hoare Logic (total) [1] Chs 9.4.1, 9.4.2, 9.4.3 and 9.5
[8] Chs. Hoare Logic, Part I and Hoare Logic, Part II
[9]
Axiomatic Basis for Computer Programming
Assigning meaning to Programs
Models of Computation I [6] Chs 2.1, 2.2, 2.3, 2.4, 3.1, 3.2, 4.3 and 4.4
[6] Ch 1: intro to Automata
[7] Chs 9.1 and 9.2
Models of Computation II [1] Ch 10
[6] Chs 5.1, 5.2, 5.4 and 6
[7] Chs 10.1, 10.2, 10.3 and 10.8
Turing Machines [6] Chs 8.2 and 8.6
[7] Ch 6
Halting, NP [6] Chs 9 and 10

[1]: Winfried Karl Grassmann and Jean-Paul Tremblay. 1996. Logic and Discrete Mathematics: A Computer Science Perspective. Prentice Hall Press, Upper Saddle River, NJ, USA.

[2]: Willem Conradie, Valentin Goranko and Claudette Robinson. 2015. Logic and Discrete Mathematics: a concise Introduction. Chichester, West Sussex, United Kingdom : Wiley. (Available online via the ANU library.)

[3]: Susanna S. Epp. 2010. Discrete Mathematics with Applications. Brooks/Cole Publishing Co., Pacific Grove, CA, USA. (Available online via the ANU library.)

[4]: David J. Hunter. 2010. Essentials of Discrete Mathematics (2nd ed.). Jones and Bartlett Publishers, Inc., USA. (Available online via the ANU library.)

[5]: Harris Kwong. 2015. A Spiral Workbook for Discrete Mathematics. Amazon Digital Services LLC. (Available online here.)

[6]: John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman. 2006. Introduction to Automata Theory, Languages, and Computation (3rd Edition). Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA. (Available online via the ANU library.)

[7]: Martin D. Davis, Ron Sigal, and Elaine J. Weyuker. 1994. Computability, Complexity, and Languages (2nd Ed.): Fundamentals of Theoretical Computer Science. Academic Press Prof., Inc., San Diego, CA, USA.

[8]: Benjamin C. Pierce, Arthur Azevedo de Amorim, Chris Casinghino, Marco Gaboardi, Michael Greenberg, Catalin Hritcu, Vilhelm Sjöberg, Andrew Tolmach, and Brent Yorgey. 2018. Programming Language Foundations. Software Foundations series, volume 2. Electronic textbook. (Available here (volume 2).)

[9]: Gordon, “Specification and Verification I”, online.

C. A. R. Hoare. 1969. An axiomatic basis for computer programming. Commun. ACM 12, 10 (October 1969), 576-580. DOI=http://dx.doi.org/10.1145/363235.363259. (Available here.)

Floyd, R. W. 1967. Assigning Meanings to Programs. Proceedings of Symposium on Applied Mathematics, 19, 19-32. (Available here.)

Previous Final Exams

2017

2018

2019

Recap (exercises)

here

Worked Examples

David Quarel (tutor of the course) has produced worked examples for each topic of the course. Worked examples are separated by weeks and you can find them in each week’s web-page (e.g. for week 5). The videos can be found in this YouTube channel, or here.

Fun Stuff

  • Logicomix (web-page) by A. Doxiadis and C. Papadimitriou, Bloomsbury Publishing, 2009. A graphic novel subtitled `An Epic Search for Truth’ starring Russel, Whitehead, Frege, Goedel, Turing and many other great logicians of the 20th century. Highly recommended.

Supplementary Reading Material

The following are recommended references. More may be added as the semester progresses.

  • Haskell: The Craft of Functional Programming (2e) Simon Thompson, (Addison Wesley).

    Many of you will have this book from COMP1100.

  • Discrete Mathematics with Applications (3e) Susanna Epp, (Thomson-Brooks/Cole).

  • The Logic Book Merrie Bergmann, (McGraw-Hill).

  • Discrete Mathematics for Computing John Munro, (Thomas Nelson).

  • Mathematical Logic by Chiswell and Hodges, Oxford University Press, 2007. A very thorough and readable introduction to the topic.

  • *Reasoned Programming by Krysia Broda, Susan Eisenbach, Hessam Khoshnevisan and Steven Vickers, Prentice Hall 1994. The first part is a bit dated by now, but the second part is a very usable introduction to first-order logic. Available electronically via the URL above.

  • forall x by P. D. Magnus. Another gentle introduction to first order logic, available electronically via the link above.

Others

  • On Haskell tips, our tutor Pramo has created this. You might find it useful. It is a quick intro to Haskell. It also contains the Haskell code used in lecture slides and practical sheets with the corresponding explanation.
  • On Haskell tips, our tutor Benjamin Gray has created this. You might find it useful.
  • Some students have suggested this web-side. While it is not an official resource for the course, you might find it useful.

Updated:    18 May 2022 / Responsible Officer:    Head of School / Page Contact:    Victor Rivera