Theory 1: Mathematical Foundations of Computer Science - COM00013C
Module summary
Mathematical Foundations of Computer Science
Module will run
| Occurrence | Teaching period |
|---|---|
| A | Semester 1 2026-27 |
Module aims
Students will be introduced to the key discrete mathematics concepts that are the foundation of computer science. Topics covered include (i) propositional and predicate logic; (ii) proof and natural deduction; (iii) set theory; (iv) combinatorics; (v) graphs; and (vi) relations on sets. After studying the module, students will be able to apply the learnt concepts, theories and formulae in real-world examples of computational problems.
Module learning outcomes
1. Explain why application of the mathematical foundations of computer science is necessary to develop systems that are demonstrably safe and secure.
2. Define, read and apply mathematical notations for the purpose of describing mathematical concepts from across discrete mathematics.
3. Understand propositional and predicate logic, including its syntax, the truth-table semantics, natural deduction proofs, key properties of formulae such as satisfiability, and use of formulae to model real-world problems.
4. Understand how to construct sets of elements, calculate cardinalities and combinations, and apply formal set theoretic relations and operations.
5. Formally define and illustrate by example graphs of different graph classes, such as simple, undirected, directed, weighted, directed acyclic, connected, disconnected and trees - with an understanding of how they may be used in real-world computational problems.
6. Construct binary relations to encode knowledge, and identify useful subclasses such as functions and injections.
7. Understand how discrete mathematics can be applied to describe basic models of computation, such as finite state machines.
8. Understand how mathematical concepts, such as logic and set theory, are implemented in programming languages.
Indicative assessment
| Task | % of module mark |
|---|---|
| Closed/in-person Exam (Centrally scheduled) | 100.0 |
Special assessment rules
None
Indicative reassessment
| Task | % of module mark |
|---|---|
| Closed/in-person Exam (Centrally scheduled) | 100.0 |
Module feedback
Feedback is provided through work in practical sessions, and after the final assessment as per normal University guidelines.
Indicative reading
** Dean N., The Essence of Discrete Mathematics, Prentice Hall, 1997
** Haggarty R., Discrete Mathematics for Computing, Addison Wesley, 2002
** Truss J., Discrete Mathematics for Computer Scientists, Addison Wesley, 1999
** Gordon H., Discrete Probability, Springer, 1997
* Solow D., How to Read and Do Proofs, Wiley, 2005