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

Teaching Assistant: | Dave Cochran | dcochra2@inf.ed.ac.uk |

InfBase provides drop-in help, in the person of our course tutor, Dave, for all first- and second-year courses in Informatics. It meets as follows:

Mondays | 15:00-16:00 | FH 1.B19 |

Tuesdays | 12:00-13:00 | FH 1.B10 |

Wednesdays | 12:00-13:00 | FH 1.B10 |

Thursdays | 17:00-18:00 | FH 1.B19 |

Fridays | 16:00-17:00 | FH 1.B19 |

The Piazza page for Inf1-CL provides an online forum for Inf1-FP in which you can post questions and answers on anything related to the course. The course lecturer, teaching assistant, tutors and demonstrators will also read and answer questions.

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

- A Traffic Light Controller.

Slides with notes and exercises: 1-up 2-up - Sets of states: Venn Diagrams and Truth Tables.

Slides with notes and exercises:1-up 2-up - Boolean Algebra

Video

Slides with notes and exercises:1-up 2-up 3-up - Boolean Algebra CNF DNF

Video

Slides with notes and exercises:1-up 2-up 3-up - Entailment

Slides with notes and exercises:1-up 3-up

Additional notes on Inference and Deduction (read the first four pages, for now). - Satisfiability

Slides with notes and exercises: 1-up 3-up - Resolution

Slides with notes and exercises: 1-up 3-up - Resolution continued

Slides with notes and exercises: 1-up 3-up - Satisfaction

Slides with notes and exercises: 1-up 3-up - Searching for Satisfaction

Slides with notes and exercises: 1-up - Machines

Slides with notes and exercises: 1-up - FSM

Slides with notes and exercises: 1-up

Notes on Automata (part 1) - Languages

Slides with notes and exercises: 1-up - NFA and regular expressions

Slides with notes and exercises: 1-up - Applied regular expressions

Slides with notes and exercises: 1-up - Inference

Slides with notes and exercises: 1-up - System Specification

Slides with notes and exercises: 1-up - Satisfaction revisited

Slides with notes and exercises: 1-up - Logic: the Big Ideas

Slides with notes and exercises: 1-up - Computation: the Big Ideas

Slides with notes and exercises: 1-up

Recordings of most lectures are available online. Please note that these recordings supplement lectures by allowing you to review the material presented and revise for the exam. They are not intended as a substitute for attending and participating in the lectures themselves.

For reasons beyond our control, some lectures have not been recorded, and you should not rely on the recording of future lectures. Moreover, the Lecture videos do not capture use of the blackboard.

Last year's lecture videos are also available.

The Single Watched Literal Explorer is designed to help you explore the single watched literal algorithm.

Sometimes we will swap slots with INF1-FP.

Week | Monday 14:10-15:00 LT4 AT | Tuesday 11:10-12:00 LT4 AT | Thursday 11.10-12:00 LT5 AT | Friday 14:10-15:00 LT5 AT |
---|---|---|---|---|

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

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

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

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

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

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

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

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

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

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

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

- (Week 3) Propositional Logic: An Introduction

ANSWERS are now online.

- (Week 4) Propositional
Logic: Truth Tables and Boolean Algebra

ANSWERS are now online.

- (Week 5) Satisfiability and Resolution

Now with Answers - (Week 6) Propositional
Logic: Resolution

Now with Answers - (Week 7) DPLL and
Watched Literals

Now with Answers - (Week 8) Computation:
Introduction to Finite State Machines

Now with Answers - (Week 9) Computation:
Subset Construction

Again with Answers - (Week 10) Propositional Logic: Sequent Calculus Now with Answers
- (Week 11) Takehome sample exam

**Tutorials:** These start in week 3 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 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 in Forrest Hill.

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 3: read pages 642-648 of Chapter 12 of the Aho and Ullman book.

A take-home exercise was provided on Thursday 26th of November. The aim of this exercise is to give you practice at tackling exam-style questions.

You should do the takehome exercise and bring it to class in the final week of term. The marking scheme will be explained, you will mark your answers, and you will have the opportunity to get feedback on any questions or misunderstandings you may have.

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.

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

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