Content
This module is an introduction to logic, languages and computability. At first sight they may appear fairly disconnected but they are in fact all closely related.
The main topics covered are:
- Formal languages (regular, context free, etc.)
- Logic (propositional calculus, first order logic)
- Arithmetic, Gödel's and Tarski's theorems
- Sets (finite, countable, uncountable)
- Idealised machines (finite state automata, pushdown automata, Turing machines)
Text
I will provide lecture notes for all of the material. These are in pdf and html formats. The notes cover more than I can cover in lectures and I will mostly try to present different examples in the notes and in lectures. Unless a topic is explicitly described as not examinable you should assume that you are responsible for the contents of both the notes and the lectures.
I am trying to make them accessible to visually impaired students to the extent that I can but the technology for typesetting mathematics is not particularly screen reader-friendly. If you use a screen reader please contact me since I'm interested in trying to make the experience less awful.
I will ask the library to put A beginner's guide to mathematical logic by Raymond Smullyan on reserve. I won't follow it very closely, but it may be useful if you want to read more about certain topics.
Exams
There will be single exam in the usual exam period, worth 70% of your module mark. I've prepared a sample exam. It's longer than the real exam.
Assignments
There are weekly assignments for this module, worth 30% of your module mark.
They are due on Wednesdays in lecture. Solutions will be posted a few days after they are due. They will be returned on Mondays in tutorial.| Assignment | Due | Problems | Solutions | |
|---|---|---|---|---|
| 1 | 7 February 2024 | |||
| 2 | 14 February 2024 | |||
| 3 | 21 February 2024 | |||
| 4 | 28 February 2024 | |||
| 5 | 13 March 2024 | |||
| 6 | 20 March 2024 | |||
| 7 | 27 March 2024 | |||
| 8 | 3 April 2024 | |||
| 9 | 10 March 2024 |
Tutorials
There are weekly tutorials at 13:00 on Mondays in LTEE2, starting 12 February
Prerecorded lectures
Unfortunately I caught a nasty cold and couldn't give a few lectures in person. Here are the video files and the slides for those.
Blackboard
There is also a Blackboard page for this module. I will try to post everything both here and there but I will occassionally forget. If you notice I've posted something in one place but not the other please let me know.