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:

1. Logic and its application to computer programming and Logic Programming.

2. Sets, relations and concept of function as an input and output process and the relationship between mathematical and programming concepts of a function.

3. Recursive algorithms and proof by induction.

1. 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.

2. Set Theory Algebra of sets, power set. Cartesian product. Computer representation of sets.
3. Relations Partial orderings, equivalence relations and partition of a set. Application to databases.
4. Functions Composition of functions, inverse functions. Application of concept of function to computer programming.
5. 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