COMP4412 Introduction to Modal Logic

This course for senior (fourth year) or graduate students is an introduction to the syntax and semantics of modal logic. It is also a NICTA co-listed graduate course. Modal logic is useful in many application areas in CS such as artificial intelligence, computer security, correctness of network protocols, agent technology, and language understanding. However, the course will only provide the common core needed for these applications without going into specifics.

It begins with motivations for modality, a quick tour of Kripke structures and typical axioms like K, T, 4 and 5, especially in the settings pertinent to computer science, e.g., in AI, programming languages, and temporal reasoning. Then in a second pass rigorous versions of the intuitive notions are introduced, proceeding to soundess and completeness via the canonical model theorem. Filtrations are introduced, and questions of decidabilty and complexity are discussed. Applications to logics of programs, belief and knowledge are then considered. If time permits, first-order modal logic is briefly examined.

Assumed Knowledge

An acquaintance with propositional logic (or its equivalent in switching logic in EE) is assumed, and the ability to do mathematical proofs involving induction, contradiction, etc., which feature in standard discrete mathematics courses at the second year (sophomore) level. Distinction-level junior (third year) students may also enroll with the permission of the instructor. Mail the course instructor Norman Foo (norman at for permission to enroll.

Course Format S2 2004

This year (S2, 2004) the course will be run as a guided reading course, with lectures being a tour of the text. The content will be stipulated by sections of the text that you have to read, and assignments you have to hand in. I will follow the text closely, and use transparencies of pages in it for the lecture commentary, but also write on the board when I have to explain technicalities. You may have to make presentations to us all from time to time about the material you read.

During the periods that I am out of town or busy, someone else (a faculty member, a postdoctoral fellow, or a NICTA scientist) will take my place.

Class meetings are 2-5pm Wed in EE222. This is also in the time-table on the School home page.

Assessment is principally by open-book assignment, possibly augmented by an in-class examination. The text is Hughes: A New Introduction to Modal Logic.

The Australian Logic Summer School in Dec 2004 is series of lectures held in the Australian National University in Canberra for advanced undergraduates and beginning graduate students who wish to understand logic and/or use it in their work. NICTA's Knowledge Representation and Reasoning Program (follow the Research/Intelligent Systems links to get to this program) is supporting a small number of students who wish to attend the Logic Summer School. Fees, accommodation, travel by bus/train will be covered. If you are interested (and have not already contacted Dr Maurice Pagnucco, Prof Norman Foo or Prof Michael Maher), please e-mail one of us (id: morri, norman, mmaher) to say you want to be considered.


Hand in assignments at the begining of each class meeting on the due date. Unless otherwse specified, the questions refer to the ones in the textbook. Note that there are answers to some questions (not usually the ones assigned!) at the back of the text, and they provide good examples of how to solve related questions.

Assignment 1, due 4 Aug.

Assignment 2, due 18 Aug.

Assignment 3, due 25 Aug.

Assignment 4, due 8 Sep.

Assignment 5, due 15 Sep.

Assignment 6, due 6 Oct. Have a good break, happy reading about Canonical Models and Frames!

Assignment 7, due 13 Oct.

Assignment 8, due 3 Nov.

This is the last assignment. Assignment 9, due 12 Nov.
Please hand in all assignments by then so that they can be graded in time. Hand in at the School Office, ask them to put in my pigeon hole.

A related logic course given in this school is COMP4415 First-Order Logic.

Two great sources of all things philosophical, and links from there to mathematical logic, AI logics, logic in language, metaphysics, etc are the Guide to Philosophy and the Stanford Encyclopedia of Philosophy. The particular section on Modal Logic is worth a brief visit for an overview.
The most comprehensive link to mathematical logic is Mathematical Logic around the world.

This page is maintained by Norman Foo.