- People
- Course description
- Lecture slides and notes
- Tutorial Exercises
- Assignments
- General Information & Other Resources

Lecturer: | Rahul Santhanam | rsanthan@inf.ed.ac.uk |

Teaching Assistants: | Areti Manataki | A.Manataki@ed.ac.uk |

- 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.
- Logic in use: Basic introduction to propositional modal logic, satisfaction, validity, proof, model checking. Examples of how such logics have wide applicability in expressing properties of computational systems.
- Tools: examples of logic/FSM based tools in system building.

- 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 (30 September - 4 October) Tutorial 1: Propositional Logic: An Introduction [Solutions]
- Week 4 (7 - 11 October) Tutorial 2: Propositional Logic: Truth Tables [Solutions]
- Week 5 (14 - 18 October) Tutorial 3: Propositional Logic: Sequent Calculus [Solutions]
- Week 6 (21 - 25 October) Tutorial 4: Propositional Logic: Resolution [Solutions]
- Week 7 (28 October - 1 November) Tutorial 5: Computation: Introduction to Finite State Machines [Solutions]
- Week 8 (4 - 8 November) Tutorial 6: Computation: Non-Deterministic FSMs and FSM Composition [Solutions]
- Week 9 (11 - 15 November) Tutorial 7: Computation: Regular Expressions [Solutions]
- Week 10 (18 - 22 November) Tutorial 8: Computation: Subset Procedure [Solutions]
- Week 11 (25 - 29 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!

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

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 |