|Teaching Fellow:||Claudia Chirita|
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.
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:
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 before the tutorial. Students who have not prepared in advance may be excluded.
There also will be a tutorial in week 1 designed to get everyone familiar with the procedure.
Connectives, rules, truth tables, Karnaugh maps, CNF, Boolean Algebra
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.
Informatics Forum, 10 Crichton Street, Edinburgh, EH8 9AB, Scotland, UK
Tel: +44 131 651 5661, Fax: +44 131 651 1426, E-mail: email@example.com
Please contact our webadmin with any comments or corrections. Logging and Cookies
Unless explicitly stated otherwise, all material is copyright © The University of Edinburgh