Inf1: Computation and Logic 2014


  1. People
  2. Course description
  3. Lecture slides and notes
  4. Tutorial Exercises
  5. Assignments
  6. General Information & Other Resources

1. People

Teaching Assistants:??????

2. Course description

2a. Aims and Objectives

The goal of this course is to introduce you to computational thinking — using computational models to describe and reason about 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.

2b. Syllabus

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


The main reference for this course 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. The second half of the course will follow Kozen quite closely. Although you will only be using the first 50 pages or so for this course, this book is also used in Inf2.

2c. Context

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.

3. Lecture materials

3a. Logic

3b. Finite State Machines

Revision Lecture

4. 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.

5. Assignment

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.

6. 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.

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