**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**