People

Overview

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.

Logic

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.

Computation

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.

Syllabus

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

Context

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.

Tutorials, Quizzes, and Tests

Tutorials

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.

Quizzes

Tests

• 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

Assessment

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.

General Information & Other Resources

1. inf1.hgs.club
2. Past papers for all Informatics courses and modules, organised by year. Search through each year to find available Inf1 Computation and Logic past papers.
3. Wikipedia is a good source for many topics, such as,
   • Functional programming and Haskell
   • Logic, Propositional logic and Predicate logic
   • Finite State Machines, Regular expressions