ÐÂÏã¸ÛÁùºÏ²Ê¿ª½±½á¹û

This BASc module is meant to be an introduction to the theoretical concepts required for Year 2 computer science courses. However, the course also provides a stand-alone introduction for students interested in the theory of computation and its links with logic and language theory. The first part of the course will focus on mathematical logic and the second part will address the fundamentals of computation, automata, and language theory.

Teaching Delivery

This module will be taught in one two-hour lecture per week followed by a one-hour seminar.Ìý

Indicative Topics

The module will cover the following topics, which may be subject to variation depending on developments in academic research and the interests of the class:

• What is logic: Syntax and semantics of propositional logic;
• Logical equivalence, logical interpretation, and algebraic reasoning;
• Boolean Algebra and Induction;
• Language theory and syntax;
• Automata;
• Fundamentals of Computation (classes of languages, models of computation, computability, complexity).

Module aims and objectives

1. Understand the main concepts in propositional logicÌý
2. Understand the main concepts in first order logicÌý
3. Understand the concept of computabilityÌý
4. Being able to evaluate and decide simple logical formulaeÌý
5. Being able to evaluate complex first order formulae and proof systemsÌý
6. Understand the concept of proof systemÌý
7. Being able to solve problems involving a mix of propositional, first order logic and proof systemsÌý
8. Being able to discuss the main points in computability, decidability and undecidabilityÌý
9. Being able to recognise computations on a Turing Machine, and being able to define simple recursive functionsÌý