Inf1: Computation and Logic 2015



  1. People
  2. Learning Materials
  3. Tutorials and Assignments
  4. Course description
  5. General Information & Other Resources



Learning Materials


Normally Thursdays 11:10-12:00 and Fridays 14:10-15:00.


Sometimes we will swap slots with INF1-FP.

Week 3
CL Lecture on Tuesday 29th Sep. Oct.
FP Lectures on Monday 28th Sep., Thursday 2nd Oct., and Friday 3rd Oct.

Note that the Lecture videos do not capture use of the blackboard.

Tutorials and Assignments

Tutorials, assignments, and readings are essential components of this course.


Tutorials: These start in week 3 and take place each week until the end of semester, including week 10. If you are ill or otherwise unable to attend one week then email your tutor, and if possible attend another tutorial group in the same week.

Link: Tutorial group times, places and membership.

If you wish to move to a different tutorial group, please ask the ITO through their online contact form and explain your constraints. Or visit them on level 4 of Appleton Tower.

Students are expected to prepare for each tutorial, which includes completing the tutorial exercises and the reading.

You must attempt the work before the tutorial and bring with you a copy of the work you have done. Tutorials are mandatory, and the only way to learn is to do the work before the tutorial, not at the tutorial. Students who have not done the work in advance will be sent away.


Week 8: Notes on Inference and Deduction

Week 7: you should by now find chapters 4&5 of Computational Logic by Genesereth easy going.

Week 5: To refresh your understanding of basic boolean algebra, logic gates, circuits and switches, I recommend the Boolean Algebra chapter of the Discrete Mathematics book from the Centre for Innovation in Mathematics Teaching at Plymouth University. If you like the style you may find more of their material useful in various parts of INF1.

Week 4: you should by now find chapters 1-3 of Computational Logic by Genesereth easy going. Read them to check your understanding of the basics of Propositional Logic.

Week 3: read pages 642-648 of Chapter 12 of the Aho and Ullman book.

Obligatory Exercise

You should do the takehome exercise and submit it (on paper) to the Informatics Teaching Organisation office on Level 4 of Appleton Tower by noon on Friday 14th of November. The aim of this exercise is to give you practice at tackling exam-style questions.

Class notes from Lecture on 27-11 are now online.

ANSWERS to Q3 and Q4 are now online.

Fun Exercise

You should play with the Turing Machine used as a Google Doodle on 23 June 2012 (the 100th anniversary of Turing's birth). The challenge is to design a machine that will recognise the language that includes all strings of the form 0n1n.

Course description

Aims and Objectives

The goal of this course is to introduce you to computational thinking — using computational models to describe and reason about systems, including systems that change through time. We focus on finite-state systems and propositional logic.

Finite state machines provide a simple model of computation that is widely used, has an interesting meta-theory and has immediate application in a range of situations. They provide an essential underpinning for your future study of more general computational models, across the whole of Informatics.

Propositional logic, is used to describe and reason about finite state systems. It provides a basis for later study of more general logics used to specify and reason about Informatic systems.


This course provides students with experience of theory in practical applications. An unordered list of topics is as follows:


Much of the material we will cover will only be presented in lectures. Copies of the slides, annotated with brief notes, will be available. The slides may be modified and expanded to clarify questions raised during the lecture, so they will normally be published a few days after each lecture.

The brief notes I provide should be supplemented with notes taken by you during the lecture. If you are unable to attend a lecture, you should try to go through the slides with someone who did. Don't be shy about asking someone to do this---explaining things to you will probably help them at least as much as it helps you.

The first 5 chapters of Genesereth, Computational Logic, 2012, provide a good summary of much of the basic technical material on propositional logic covered in this course.

Another reference is Foundations of Computer Science by Aho and Ullman. This book has been taken out of print by W. H. Freeman. You may be lucky and find a used copy, e.g. on Amazon, but it is freely available for download on the web :-)

As a secondary reference, I suggest you purchase Kozen's Automata and Computability. Kozen will provide useful further reading for some of the material in the second half of the course. Although at most the first 50 pages or so are relevant for this course, this book is also used in Inf2.


This course supplies foundational knowledge for Informatics courses taken in subsequent years of study. It runs alongside the Informatics 1 Functional Programming course, which provides complementary experience in programming.

General Information & Other Resources

  1. Past papers for all Informatics courses and modules, organised by year. Search through each year to find available Inf1 Computation and Logic past papers.
  2. Wikipedia is a good source for many topics, such as,
  3. Click here for Matt Chapman's Finite State Machine animator.
    This is a Java Applet that allows you to draw FSMs in a window and experiment with them.
  4. There is no need for a text book for this course, but those who are interested in more reading can see the following books: Computation: "An introduction to formal languages and automata" by Peter Linz. Logic: "The essence of Logic", John Kelly, 1997. if you still want to read more on logic: "Logic for computer science", Steve Reeves, 1990.

Notes from 2013 delivery of this course.


Finite State Machines

Revision Lecture

Tutorial Exercises

You can find your tutorial group at Informatics Theon Portal, where times, locations, tutor and student lists are provided. Tutorial exercise solutions will be released after the appropriate tutorials have been held.


There is a single assignment for Computation and Logic. It does not count toward your final mark for the course but it is a course requirement that you complete it, and it will be assessed to provide feedback for your benefit.

Home : Teaching : Courses : Inf1 

Informatics Forum, 10 Crichton Street, Edinburgh, EH8 9AB, Scotland, UK
Tel: +44 131 651 5661, Fax: +44 131 651 1426, E-mail:
Please contact our webadmin with any comments or corrections. Logging and Cookies
Unless explicitly stated otherwise, all material is copyright © The University of Edinburgh