Computer Laboratory

Course material 2010–11


Paper 2: Discrete Mathematics II

This course is not taken by NST or PPST students.

Lecturer: Professor G. Winskel

No. of lectures: 12

Prerequisite course: Discrete Mathematics I

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.


Lectures


  • Sets and logic. The basic set operations (union, intersection and complement) on subsets of a fixed set. The Boolean laws. Propositional logic and its models. Validity, entailment, and equivalence of propositions revisited. Structural induction illustrated on propositions. [2 lectures]

  • Relations and functions. Product of sets. Relations, functions and partial functions. Composition and identity relations. Injective, surjective and bijective functions. Direct and inverse image of a set under a relation. Equivalence relations and partitions; modular arithmetic as an example. Directed graphs and partial orders. Size of sets (cardinality), especially countability. Cantor’s diagonal argument to show the reals are uncountable. [3 lectures]

  • Constructions on sets. Russell’s paradox. Basic sets, comprehension, indexed sets, unions, intersections, products, disjoint unions, powersets. Characteristic functions. Sets of functions. Lambda notation for functions. Cantor’s diagonal argument to show power set strictly increases size. [2 lectures]

  • Introduction to inductive definitions. Using rules to define sets; examples. Reasoning principles: rule induction and its instances; induction on derivations briefly. Simple applications, including transitive closure of a relation. [3 lectures]

  • Well-founded induction. Well-founded relations and well-founded induction. Other induction principles as instances of well-founded induction. Product and lexicographic product of well-founded relations. Examples and applications, including to Euclid’s algorithm for HCF/GCD. Informal understanding of definition by well-founded recursion. [2 lectures]

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 the principle of well-founded 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.