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
-
How to think like a mathematician a companion to undergraduate mathematics
Cambridge University Press
Discrete Mathematic - supplementary reading
-
Discrete mathematics and its applications
Eighth edition., McGraw-Hill Education
-
Mathematical structures for computer science : discrete mathematics and its applications
7th edition., W.H. Freeman and Company, a Macmillian Higher Education Company
-
Discrete mathematics for computer scientists
2nd edition., Addison-Wesley
-
Discrete Mathematics, Global Edition
-
Discrete mathematics
Eighth edition.; Global edition., Pearson
-
Chapter zero : fundamental notions of abstract mathematics
2nd ed., Addison-Wesley
Logic - supplementary reading
-
The logic manual
Oxford University Press
-
Logic in computer science : modelling and reasoning about systems
Second edition., Cambridge University Press
-
A mathematical introduction to logic
Second edition., Academic Press, a Harcourt Science and Technology Company
-
Logic
Second edition., Penguin Books
-
Logic : techniques of formal reasoning
2nd ed., Harcourt Brace Javanich
Reasoning about Programs - supplementary reading
-
Reasoned programming
Prentice Hall
Module leaders
Dr Dalal AlrajehDr Mark Wheelhouse
Dr Steffen van Bakel
Professor Sophia Drossopoulou