Discrete Mathematics

Module aims

In this module you will have the opportunity to study the discrete mathematics that underpins formal aspects of Computation. Central to this is how to prove properties of systems, so the module begins with an introduction to different proof methods and how to construct a proof both informally and formally. You will then study fundamental discrete structures such as sets, relations and functions and their associated properties. The module ends with an overview of induction, which will prepare you for a follow-on module on program reasoning.                

Learning outcomes

Upon successful completion of this module you will be able to:

  • construct mathematical proofs using informal and formal reasoning
  • show properties over sets
  • establish the character of a relation between sets
  • determine whether two sets have the same cardinality
  • understand the fundamental difference between natural numbers and reals
  • recognise an inductive definition and be able to construct an inductive proof with it   

Module syllabus

  • Proof methods: The relation between human thinking and allowed steps in mathematical proofs, and how to formalise proofs.
  • Sets: equality, set construction (intersection, union, powerset, product), and partitions  
  • Relations: relation construction (inverse, intersection, union, complement), equivalences, and transitive closure
  • Peano arithmetic: axiomatisation of natural numbers, and the principle of induction
  • Function: properties of functions (injection, surjection, bijection), composition, inverse
  • Cardinality: finite v infinite sets, equivalence between sets through bijective functions, Cantor's theorem
  • Inifinities: countability, Cantor's diagonalisation argument, uncountable sets, comparing inifity of rationals v that of reals
  • Orderings: partial orders, irreflexivity, total orders
  • Induction: generalisation of Peano's principle of induction

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, algorithm design and program reasoning. The remaining exercises are intended for you to use for self-study.

The Piazza Q&A web service will be used as an open online discussion forum for the module.    

Assessments

There will be one assessed test that contributes 15% of the mark for the module. There will be a final written exam, which counts for the remaining 85% 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 previously unseen problems.       

Detailed feedback, both written and verbal, will be given on the exercises covered in the PMT tutorials. These exercises will be issued approximately every two weeks and written feedback will be returned the week after submission. You will receive written feedback on the assessed coursework exercise, which counts for 15% of the module mark. There will also be opportunity for you to receive feedback during the in-class problem solving sessions.          

Reading list

Supplementary reading

Module leaders

Dr Steffen van Bakel