Discrete Mathematics, Logic & Reasoning

Module aims

In this module you will learn how discrete mathematics and logic can be used to describe and reason about computational structures and systems.  The module provides an important  foundation for many core topics in Computing, such as computer hardware design, algorithm analysis, and program reasoning. Central to this module are proof techniques, which are important when establishing whether or not a program or system behaves according to its specification. The ability to use mathematics and logic to formalise such specifications is also a key learning outcome.

Learning outcomes

Upon successful completion of this module you will be able to:
- construct various types of mathematical proof using informal and formal reasoning
- define properties of fundamential discrete structures, such as sets, relations and functions
- read, parse and evaluate logical formulas
- formalise English statements into logic
- use logic to specify the desired properties of a system, program or algorithm
- use induction to reason about the correctness of recursive programs and data structures
- provide suitable pre, post and mid conditions and invariants for imperative program fragments
- use logic to reason about the correctness of imperative programs

Module syllabus

Logical connectives
Proof methods
Sets, relations and functions
Countability
Orderings
Induction
Inductive reasoning applied to recursive programs and data types
Formalisation of logic syntax and semantics
Validity and satisfiability
Equivalence
Logical proof systems
Soundeness and completeness
Specification of pre-, post- and mid-conditions
Loop invariants and variants
Logical reasoning applied to imperative programs

Teaching methods

The material will be taught through traditional lectures, backed up by formative exercises designed to reinforce the material as it is taught. Classroom sessions will comprise traditional lecture material interspersed with problem solving, using selected formative exercises as examples. Some of the other exercises will be covered in small-group tutorials, Personal Maths Tutorials (PMTs), which are weekly one-hour tutorials run by academic tutors and Undergraduate Teaching Assistants (UTAs). These tutorials encourage group discussions and group problem solving designed to reinforce your understanding of key topics in logic, discrete mathematics and program reasoning. The remaining exercises are intended for you to use for self-study.    

An online service will be used as a discussion forum for the module. 

Assessments

There will be a small number of assessed tests (typically two or three) that contribute 20% of the mark for the module. There will be a final written exam, which counts for the remaining 80% of the marks. The exercises selected for the PMT tutorials will be assessed by your academic tutor and UTA. This assessment does not count to your final degree mark, but is intended to give you an indication of how you well you are assimilating the material taught and how effectively you are applying that material to solving  unseen problems.   

Detailed feedback, both written and verbal, will be given on the exercises covered in the PMT tutorials. These exercises will be issued weekly and written feedback will be returned at the following PMT session. You will receive written feedback on the assessed coursework exercises, which counts for 20% of the module mark. There will also be opportunity for you to receive feedback during the in-class problem solving sessions.

Reading list

Core reading

Discrete Mathematic - supplementary reading

Logic - supplementary reading

Reasoning about Programs - supplementary reading

Module leaders

Dr Dalal Alrajeh
Dr Mark Wheelhouse
Dr Steffen van Bakel
Professor Sophia Drossopoulou

View the module reading list (Leganto)