**Requirements/prerequisites:**
None

**Duration:**
22 weeks

**Number of lectures per week:**
1

**Assessment:**

**End-of-year Examination:**
This course forms half of one 3-hour end of year exam.

**
Description: **

**Objectives:**

The aim of this course is to study mathematical topics relevant to a formal approach to computing, including logic, sets, functions, and relations and proof with a discussion of their applications to computing.

Expected Learning Outcomes:

Students having completed this course should understand and have mastered:

- Logic and its application to computer programming and Logic Programming.
- Sets, relations and concept of function as an input and output process and the relationship between mathematical and programming concepts of a function.
- Recursive algorithms and proof by induction.

**Logic**- (a) Propositional logic: Propositions and well-formed formula. Truth tables, logical equivalence, tautologies and valid arguments. Derivation rules for propositional logic.
- (b) Predicate logic: Existential and universal quantifiers. Rules of inference and reasoning with quantified predicates. Application of logic to Proof of correctness of computer programs and to Logic Programming.
- (c) Methods of proof: Direct proof, proof by contradiction and contrapositive, proof by induction with application to testing validity of recursive algorithms.

**Set Theory**Algebra of sets, power set. Cartesian product. Computer representation of sets.**Relations**Partial orderings, equivalence relations and partition of a set. Application to databases.**Functions**Composition of functions, inverse functions. Application of concept of function to computer programming.**Matrices**Algrebra of matrices. Application of matrices to storage and manipulation of data, computer representation of relations and their use in computer graphics.

**Course Format:** 1 lecture per week for 22 weeks

**Method of Evaluating and Grading:** Half of one 3-hour end of year examination for 50

**Course Texts: (i) Mathematical Structures for Computer Science-J,**, L. Gerstring. Pubs; W.H. Freeman and Company, 1999, Fourth Edition. ISBN 0-7167-8306-1.

**Further Readings: Discrete mathematics - Richard Johnsonbaugh**
Third Edition-Macmillion Publishing Company
ISBN 0-02-360721-1, 1999

Discrete Mathematics for Computer Science, Peter Grossman.
Publisher: Macmillan 1995. ISBN 0-7329-2779 X

Discrete Mathematics 4th ed, Richard Johnsonbaugh. Prentice Hall. ISBN 0-13-571191-6

Nov 14, 2001

File translated from T

On 14 Nov 2001, 17:21.