Lecturer: | Michael Fourman | mfourman@inf.ed.ac.uk |

Teaching Assistant: | Dave Cochran | dave@robotsquid.net |

Dave will normally be available to answer your questions in infbase (Appleton Tower Room 5.02) on Mondays from 16:00-18:00

A new book recommendation is given below.

- A Traffic Light Controller Lecture Video. Slides with notes and exercises. (3.3 MB pdf)
- Sets of states: Venn Diagrams and Truth Tables Slides with notes and
exercises. (3.5 MB pdf)

This lecture was not recorded, but video of all subsequent lectures should be available. - from Propositions to Quantifiers Lecture Video: Slides with notes and exercises. (1.4 MB pdf)
- Finite Relational Structures Lecture Video: Slides. (3.3MB pdf)
- Circuits and Syntax Lecture Video: Slides. (0.6MB pdf)
- Satisfiability Lecture Video: Slides. (0.5MB pdf)
- Logic by Colouring Lecture Video: Slides. (0.9MB pdf)
- Satisfaction Lecture Video: Slides. (0.2MB pdf)
- Davis-Putnam Lecture Video: Slides. (66KB pdf)
- Watching Variables Lecture Video: Slides. (0.2MB pdf)
- Reprise Lecture Video: Slides. (61KB pdf)
- Inference Lecture Video: Slides. (61KB pdf)
- Machines Lecture Video: Slides. (61KB pdf)
- FSM Lecture Video: Slides. (61KB pdf)
- Machines and Languages Lecture Video: Slides. (61KB pdf)
- NFA and Regular Expressions Lecture Video: Slides. (61KB pdf)
- System Specification using FSMs Lecture Video: Slides Notes
- Applied regex Lecture Video: Slides
- Satisfaction revisited Lecture Video: Slides

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

- (Week 3) Propositional Logic: An Introduction

ANSWERS are now online.

In the first tutorial, please also discuss the exercises appended to the slides for the first lecture. - (Week 4) Propositional Logic: Truth Tables

Please also discuss the exercises appended to the slides for the second and third lectures.

ANSWERS are now online.

- (Week 5) Logic: Switches
and Predicates

ANSWERS are now online.

- (Week 6) Logic by Colouring

ANSWERS are now online. - (Week 7) Resolution

ANSWERS are now online. - (Week 8) Inference

ANSWERS are now online. - (Week 9) Finite
State Machines

ANSWERS are now online. - (Week 10) NFA to DFA

ANSWERS are now online. - (Week 11) Designer FSM

ANSWERS are now online.

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

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.

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 0^{n}1^{n}.

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.

- Informatics looks at the world in terms of information.

Nature is, perhaps, infinitely complicated, but we often use abstract models of natural systems based on a finite amount of information.

The first part of this course deals with such models, how we can speak about the states of such systems, using propositional logic.

For example, a weather report describes the state of the weather by reporting a finite number of attributes. The philosophers have only interpreted the world, in various ways; the point is to change it.

In the second part of the course we model change. Many systems in nature change continuously. Our second abstraction is to consider a discrete series of time steps, and to focus on how the state of our system changes from one step to another, without worrying about the details of what happens in between.

For example, in describing a game of chess we focus on the state of the board before and after each move, but pay no attention to the way the players move their pieces.- A brief introduction of computation as a process and a method of modelling behaviour. Discussion of the advantages of moving to simple models that are appropriate for restricted classes of tasks. Discussion of the importance of correctness of computational procedures, and how logic can be used to reason about correctness.
- Reasoning: Propositional logic, its connectives and the meaning of those connectives in terms of truth tables. The concepts of satisfiability, validity and proof. The relationship between a proof and the validity of an implication in terms of truth tables.
- Computation: the definition as acceptor and transducer, deterministic/non deterministic machines, regular expressions, operations on FSMs, discussion of formal limits, how good are FSMs as a model of interactions.
- Applications/Modelling: simple examples drawn from a number of domains, design issues, using operations on FSMs to structure solutions, more complex examples: dialogue systems, controllers, digital watch, regular expressions and pattern matching. Application areas such as robotic controllers.
- Engineering: how do we specify, test and debug FSM's, design by decomposition, concurrency, size of machines.
- Using Logic to describe change. The Stanford Research Institute Problem Solver (STRIPS) and elementary planning.
- Tools: examples of logic/FSM based tools in system building.

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.

- Past papers for all Informatics courses and modules, organised by year. Search through each year to find available Inf1 Computation and Logic past papers.
- Wikipedia is a good source for many topics, such as,
- 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. - 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.

- Logic notes
- Lecture slides: Lecture 1, Lecture 2, Lecture 3, Lecture 4, Lecture 5, Lecture 6, Lecture 7.
- Logical Equivalences

- FSM notes: Section 1, Section 2, Section 3, Section 4, Section 5, Section 6, Section 7.
- Lecture slides: Lecture 1, Lecture 2, Lecture 3, Lecture 4, Lecture 5, Lecture 6, Lecture 7. Lecture 8.

- Week 3 (29 September - 3 October) Tutorial 1: Propositional Logic: An Introduction [Solutions]
- Week 4 (6 - 10 October) Tutorial 2: Propositional Logic: Truth Tables [Solutions]
- Week 5 (13 - 17 October) Tutorial 3: Propositional Logic: Sequent Calculus [Solutions]
- Week 6 (20 - 24 October) Tutorial 4: Propositional Logic: Resolution [Solutions]
- Week 7 (27 October - 311 October) Tutorial 5: Computation: Introduction to Finite State Machines [Solutions]
- Week 8 (3 - 7 November) Tutorial 6: Computation: Non-Deterministic FSMs and FSM Composition [Solutions]
- Week 9 (10 - 14 November) Tutorial 7: Computation: Regular Expressions [Solutions]
- Week 10 (17 - 21 November) Tutorial 8: Computation: Subset Procedure [Solutions]
- Week 11 (24 - 28 November) Tutorial 9: Revision [Solutions]new!

- The following assignment is due for submission to the Informatics Teaching Organisation (level 4 of Appleton Tower) by noon 15th of November. [Assignment]
- Guide to Standard Answers (and Marking Scheme) [Answers]new!

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