Course material 2010–11

##

Paper 1: Discrete Mathematics I

*Lecturer: Dr S. Staton*

*No. of lectures:* 9 (Continued into Lent Term)

*This course is a prerequisite for all theory courses as well as
Discrete Mathematics II, Algorithms I, Security (Parts IB and II), Artificial Intelligence (Parts IB and 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.