# Computer Laboratory

Course pages 2012–13

# Discrete Mathematics I

Principal lecturer: Dr Samuel Staton
Taken by: Part IA CST, Part IA NST, Part I PPS
Past exam questions: Discrete Mathematics I, Discrete Mathematics
Information for supervisors (contact lecturer for access permission)

No. of lectures: 9 (Continued into Lent Term)
Suggested hours of supervisions: 3
This course is a prerequisite for all theory courses as well as Probability, 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. [3 lectures]

• Proof. Proving propositional and predicate formulas in a structured way. Introduction and elimination rules. [2 lectures]

• Sets. Basic set theory. Relations, graphs, and orders. [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.
Cullinane, M.J. (2012). A transition to mathematics with proofs. Jones & Bartlett.
Devlin, K. (2003). Sets, functions, and logic: an introduction to abstract mathematics. Chapman and Hall/CRC Mathematics (3rd ed.).
Pólya, G. (1980). How to solve it. Penguin.

• © 2012 Computer Laboratory, University of Cambridge
Information provided by Dr Samuel Staton