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

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 begin by introducing some mathematical tools that help us to talk clearly and unambiguously. We then use these tools to study finite-state systems and propositional logic. These provide examples of the logical ideas of syntax and semantics and the computational ideas of structure and behaviour.

We will use sets, properties, relations, and functions to think and talk about computational systems.

Talking is all well-and-good, but talking in English, or any other natural language, is notoriously ambiguous, and we are often imprecise. We introduce a logical notation to make precise and unambiguous statements about computational systems.

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 are used as basic computational models across the whole of Informatics and at the same time are used successfully in many widely used applications and components.

In future courses you will study more-general models of computation.

Various logics are used for specifying and reasoning about informatic systems. Statements about finite systems can be expressed in propositional logic. We introduce two procedures for reasoning in propositional logic, and show that these can be used to solve many combinatorial problems. This provides a basis for later study of more general logics used to specify and reason about Informatic systems.

- Sets, properties, relations and functions, used to model situations.
- Making clear and unambigous statements about situations, using logic.
- Describing the computational behaviour of physical systems, using states.
- Finite-state systems: a basic model of computation; deterministic and non-deterministic automata; regular expressions; acceptors; structured design of finite state machines.
- Propositional logic: truth tables, satisfiability; natural deduction, resolution; soundness, completeness.

This course provides students with experience of theory in a practical context. It also introduces a variety of 'professional issues' including software IP, verification, correctness, best practice and liability.

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

- Sets
- Logic
- Set Theory
- VennDiagrams-TruthTables
- Boolean Algebra
- CNF and Karnaugh maps
- Satisfiability - 2-SAT
- CNF via BooleanAlgebra
- Resolution
- Change

A video from last year (when I introduced this material in the first lecture):

- Traffic Lights
- Machines
- NFA as delivered (late) on Friday 3 Nov

NFA-regex (revised version for delivered Thursday 9 November) - Automata: Arden's Rule & Subset Construction
- Inference
- Gentzen's Rules
- The Big Ideas
- Review: NFA, DFA, regex
- Review: Inference and Entailment
- Review: Resolution
- Takehome review
- Takehome review

Sometimes we will swop slots with INF1-FP. These swops are shewn in
**bold**.

Week | Monday 14:10-15:00 George Square LT | Tuesday 11:10-12:00 LTA DHT | Thursday 11.10-12:00 LTA DHT | Friday 14:10-15:00 LTA DHT |
---|---|---|---|---|

1 | INF1-FP | INF1-FP | INF1-CL | INF1-CL |

2 | INF1-CL |
INF1-CL |
INF1-CL | INF1-CL |

3 | INF1-FP | INF1-FP | INF1-CL | INF1-FP |

4 | INF1-FP | INF1-FP | INF1-FP |
INF1-FP |

5 | INF1-FP | INF1-FP | INF1-CL | INF1-CL |

6 | INF1-FP | INF1-FP | INF1-CL | INF1-CL |

7 | INF1-FP | INF1-FP | INF1-CL | INF1-CL |

8 | INF1-FP | INF1-FP | INF1-CL | INF1-CL |

9 | INF1-FP | INF1-FP | INF1-CL | INF1-CL |

10 | INF1-CL |
INF1-CL |
INF1-CL | INF1-CL |

11 | INF1-FP | INF1-FP | INF1-CL | INF1-CL |

InfBase is in room 7.03 of Appleton tower, and is staffed from 11am-3pm on Monday through Friday during the normal semester (Weeks 3-11) and during Revision weeks. See the detailed schedule for when tutors with specific expertise will be present.

The course TA, Dave Cochran will be available in InfBase 1400-1500 on Wednesdays.

**Tutorials:** These start in week 2 and
take place each week until the end of semester, including week 11.
If you are ill or otherwise unable to attend one week then if possible
you attend another tutorial 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 in Appleton Tower (level 6).

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 2) Forty Questions — now with Solutions
- (Week 3) Propositional Logic: Venn Diagrams and Truth Tables — now with Solutions
- (Week 4) Propositional Logic: Karnaugh Maps — now with Solutions
- (Week 5) Counting — now with Solutions
- (Week 6) Satisfiability & Resolution — now with Solutions
- (Week 7) Resolution & Entailment — now with Solutions and some slides discussing the traffic light example.
- (Week 8) Computation: Introduction to Finite State Machines — now with Solutions
- (Week 9) Computation: Non-Deterministic FSMs and Regular Expressions — now with Solutions
- (Week 10) Propositional Logic: Entailment and Resolution — now with Solutions

- Week 1:
- MML Sections 1.1-1.7.
- Week 2:
- MML Sections 2.1-2.3 (to check your understanding, try exercises 1 & 2 on page 36).
- Week 3:
- MML Sections 6.1-6.4 (to check your understanding, try exercises 1 to 8 on pp 128-31).
- Week 6:
- Here are some online resources that present resolution. None of these covers
2-SAT as a special case, so you will be able to use the arrow rule
to solve some of their examples of resolution. Earlier chapters of
these books review much of the Propositional
Logic
material we have covered (and more besides).
- Chapter 5 of
*Introduction to Logic*by Michael Genesereth and Eric Kao. - Chapters 5 of
*Computational Logic*by Genesereth. (an earlier version of the Intro to Logic book, in html format). - Chapter 12 of
*Foundations of Computer Science*by Al Aho and Jeff Ullman.

- Chapter 5 of
- Week 7:
- Read the first two sections, and the section on applications, of the Wikipedia article on Finite State machines Sections 1.1-1.7.
- Week 8:
- MML Chapter 17 on Finite Automata and Regular Languages, up to and including most of page 468, presents most of the material we will cover on these topics. (The main exception is Arden's rule, which we will cover on Friday this week.)
- Week 9:
- The Wikipedia article provides a useful summary of the NFA to DFA Powerset construction.
- Week 10:
- The Wikipedia article provides a useful summary of the Sequent Calculus. Beware that in the "Reduction trees" section of that article proof trees grow downwards, whereas we grow our trees upwards. This means that the rules are presented upside-down (from our perspective). Confusingly, the example derivations in the following section on the system LK use our convention.

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. We model states of such systems using sets, functions, and relations.

For example, a marine weather report describes the state of the weather by reporting a finite number of attributes. Visibility is Good, Moderate, Poor, or Very Poor; Sea State has eight values, ranging from Smooth to Phenomenal.

A mariner may decide never to go out is the visibility is too poor or the wind is too strong, or the sea is too rough. Propositional logic can be used to express such conditions.

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 common theme is the analysis of complex systems using compositional descriptions. Complex truth tables are built using a few boolean operations. Complex machines are composed using primitives for sequential composition, alternation, and repetition.

- A brief introduction of computation as a process, and computational models as 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, inference and truth. The relationship between a proof and the validity of an implication in terms of truth tables. Searching for satisfaction: algorithms for finding models for systems of propositional constraints.
- 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 the design, analysis and construction of complex systems.

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 re-published a few days after each lecture.

Mathematical Methods in Linguistics, by Robert Wall, Alice Ter Meulen, and Barbara Hall Partee, ISBN-10: 9027722455 ISBN-13: 978-9027722454 (Part 1 of which you can download freely) provide a good reference for the basic mathematical tools we will use. It also covers a lot of material that goes beyond this course, much of which will be useful to you in future.

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 :-)

- inf1.hgs.club
- 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. - 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 |