



Next: Foundations of Computer Science Up: Michaelmas Term 2007: Part Previous: Digital Electronics Contents
Discrete Mathematics
This course is taken by Part IA (50% Option) students.
Lecturer: Professor G. Winskel
No. of lectures and mini-seminars: 12 + 4
This course is a prerequisite for all theory courses as well as Security (Part IB and Part II), Artificial Intelligence (Part IB and Part II), Information Theory and Coding (Part II).
Aims
This course will develop the theory of sets and their uses in Computer Science.
Associated with this course is a series of four mini-seminars (in the Lent Term) involving the active participation of students. These are tickable, so every 50% Option student must attend all four seminars, and deliver a mini-seminar at one of them.
Lectures
- Sets and constructions on sets.
Basic sets, comprehension, indexed sets, unions, intersections,
products, disjoint unions, powersets. Russell's paradox.
- Relations, functions and partial functions.
Composition and identity relations. Lambda notation for functions.
Direct and inverse image of a relation.
Equivalence relations and partitions.
Cardinality especially countability, Cantor's diagonal argument.
- Sets and logic.
Powersets as boolean algebras.
Characteristic functions.
Venn diagrams.
- Induction.
Mathematical induction and related induction principles.
Well-founded relations and well-founded induction.
Applications.
- Introduction to inductive definitions.
Using rules to define sets.
Reasoning principles: the inductively defined set is the least set
closed under the rules; induction on derivations.
Simple applications.
Objectives
On completing this part of the course, students should be able to
- understand and use the language of set theory; prove and
disprove assertions using a variety of techniques
- understand boolean operations as operations on sets and
formulate statements using boolean logic
- apply principles of induction
- define sets inductively using rules, and prove properties about
them
Recommended reading
Comprehensive notes will be provided.
Devlin, K. (2003). Sets, functions, and logic: an introduction to abstract mathematics. Chapman and Hall/CRC Mathematics (3rd ed.).
Biggs, N.L. (1989). Discrete mathematics. Oxford University Press.
Mattson, H.F. Jr (1993). Discrete mathematics. Wiley.
Nissanke, N. (1999). Introductory logic and sets for computer scientists. Addison-Wesley.
Pólya, G. (1980). How to solve it. Penguin.




Next: Foundations of Computer Science Up: Michaelmas Term 2007: Part Previous: Digital Electronics Contents