**Next:**Paper 2: Digital Electronics

**Up:**Michaelmas Term 2009: Part

**Previous:**Paper 1: Foundations of

**Contents**

##

Paper 1: Discrete Mathematics I

*Lecturer: Dr P.M. Sewell*

*No. of lectures:* 8

*This course is a prerequisite for all theory courses as well as
Discrete Mathematics II, Algorithms I, 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 intuition for discrete mathematics reasoning involving numbers and sets.

**Lectures**

**Logic.**Propositional and predicate logic formulas and their relationship to informal reasoning, truth tables, validity, proof. [4 lectures]**Sets.**Basic set constructions. [2 lectures]**Induction.**Proof by induction, including proofs about total functional programs over natural numbers and lists. [2 lectures]

**Objectives**

On completing the course, students should be able to

- write a clear statement of a problem as a theorem in
mathematical notation;
- prove and disprove assertions using a variety
of techniques.

**Recommended reading**

* Velleman, D.J. (1994). *How to prove it (a structured approach).* Cambridge University Press.

* Rosen, K.H. (1999). *Discrete mathematics and its applications*. McGraw-Hill (6th ed.).

Biggs, N.L. (1989). *Discrete mathematics.* Oxford University Press.

Bornat, R. (2005). *Proof and disproof in formal logic.* Oxford University Press.

Devlin, K. (2003). *Sets, functions, and logic: an introduction to abstract mathematics.* Chapman and Hall/CRC Mathematics (3rd ed.).

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:**Paper 2: Digital Electronics

**Up:**Michaelmas Term 2009: Part

**Previous:**Paper 1: Foundations of

**Contents**