Computation and Logic resources

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

Teaching Fellow: | Claudia Chirita | `cchirita@ed.ac.uk` |

Informatics is the study of systems that store, process, and communicate information. The logic and computation strand of INF1A introduces ideas you will use, in many future courses, to describe and reason about such systems.

We begin by introducing some mathematical tools that help us to talk clearly and unambiguously. 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 in 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.

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.

In the programming strand of INF1A you will learn to program in Haskell. Haskell is designed to make it easy to represent sets, properties, relations and, above all, functions. It will allow us to implement many of the constructions we discuss.

We often describe things in terms of their properties: big red balloon; small green triangle. We also use properties to make statements about the world: all men are mortal; some swans are black.

We can reason about such staments: All men are mortal; Socrates is a man; therefore, Socrates is mortal. We begin our study of logic by developing the theory of such syllogistic reasoning.

Many different logical systems are used for specifying and reasoning about informatic systems. We focus on the simplest example, propositional logic, and explore some fundamental ideas that will provides a basis for your later study of more expressive logics.

Many statements about finite systems can be expressed in propositional logic. We introduce computational procedures for reasoning in propositional logic, and show that these can be used to solve many combinatorial problems.

One 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 will focus on one deceptively simple example.

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. This fundamental computational model is routinely used in the design and implementation of software and hardware systems, across the whole of Informatics.

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

- use sets, properties, relations, and functions, to talk about logic and computation;
- use logical connectives and quantifiers informally to make clear and unambigous statements;
- use models based on states, transitions, and logic to describe the computational behaviour of simple systems;
- communicate effectively to collaborate with other students and your teachers.

- Finite-state systems: deterministic and non-deterministic automata, transducers, acceptors, regular expressions.
- Propositional logic: syllogisms, truth tables, Venn diagrams, Karnaugh maps, CNF, satisfiability, deduction, reduction; soundness, completeness.

Feedback and assessment: Each week we will highlight the skills you should have learnt, and provide online quizzes you can use to check that you have mastered them. You make take and retake the quizzes as often as you choose.

For example, by the end of week 2 you should have mastered the following skills:

- Analyse an argument as a succession of syllogistic steps.
- Use Venn diagrams to justify the validity of a valid syllogism.
- Determine the validity of a purported syllogistic argument.
- Use counterexamples to refute a fllacious argument.
- Use contraposition to relate the validity of two syllogisms.

This course supplies foundational knowledge for Informatics courses taken in subsequent years of study. It provides students with experience of theory in a practical context, develops their abilities to reason and communicate, and also introduces a variety of 'professional issues' including software IP, verification, correctness, best practice and liability.

Each week (2-11) includes a tutorial assignment that
*you must attempt and submit* before the tutorial. You
should then be prepared to share and discuss your work during the
tutorial. Tutorials are mandatory, and only effective if you do the
assigned work

There also will be a tutorial in week 1 designed to get everyone familiar with the procedure.

# Logic

# Predicates and Syllogisms

Features and predicates, Venn diagrams, counterexamples, contraposition.# Boolean Logic

Connectives, rules, truth tables, Karnaugh maps, CNF, Boolean Algebra

# Satisfiability

Constraints, DPLL, Tseytin

# Computation

# DFA

# NFA

Credit is given for tutorial assignment submissions (2 x 10), the section tests (12 * 5), and a final major test (20). Thesemarks are summed to give a final mark for the computation and logic component of the course.

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

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 |