Course schedule
Syllabus
References
Tutorial exercises
Tests

Course schedule
Time: Slot D (M 11:3012:25, Tu 09:3011:25, Th 07:3008:25)
Syllabus
Propositional logic 
Syntax, semantics, valid, satisfiable and unsatisfiable
formulas, encoding and examining the validity of some logical arguments.
 Proof techniques 
Forward proof, proof by contradiction, contrapositive proofs,
proof of necessity and sufficiency.
 Sets, relations and functions 
Operations on sets, relations and functions, binary relations,
partial ordering relations, equivalence relations, principles of mathematical induction.
 Size of a set 
Finite and infinite sets, countable and uncountable sets,
Cantor's diagonal argument and the power set theorem, SchröderBernstein theorem.
 Combinatorics 
Basic counting techniques: inclusion and exclusion,
pigeonhole principle, permutation, combination, summations. Introduction to recurrence
relations and generating functions.
 Algebraic structures and morphisms 
Algebraic structures with one binary operation 
semigroups, monoids and groups, congruence relation and quotient structures.
Free and cyclic monoids and groups, permutation groups, substructures, normal
subgroups. Algebraic structures with two binary operations  rings, integral
domains and fields. Boolean algebra and Boolean ring.
 Graphs and trees 
Graphs and their basic properties  degree, path, cycle,
subgraphs, isomorphism, Eulerian and Hamiltonian walks, graph coloring, planar graphs,
trees.

References
The following is the main textbook for the course. This book provides a comprehensive and modern treatment
of the subject and would be an extremely handy reference for all your years to come. Unfortunately, the
book omits many proofs and has no exercises. This means that attending the lectures regularly would be a
must for every student.
Kenneth H Rosen (Editorinchief), Handbook of Discrete and Combinatorial Mathematics, CRC Press, 2000.
Some other books that can be used as references are:
C L Liu, Elements of Discrete Mathematics, Second Edition, Tata McGrawHill.
Bernard Kolman, Robert C Busby, and Sharon Cutler Ross, Discrete Mathematical Structures, fifth edition, PrenticeHall of India.
Ralph P Grimaldi, Discrete and Combinatorial Mathematics, Pearson Education Asia.
Norman L Biggs, Discrete Mathematics, Oxford University Press.
J P Tremblay and R Manohar, Discrete mathematical structures with applications to Computer Science, Tata McGrawHill.
Augmenting handouts
 Size of a set
Note that this document was prepared in the last year when 0 was not
a natural number. Now that 0 is a natural number, please incorporate
the relevant changes.
Course pages of previous years
Tutorial exercises
 Tutorial 1 (July 26, 2007)
 Tutorial 2 (August 02, 2007)
 Tutorial 3 (August 09, 2007)
 Tutorial 4 (August 16, 2007)
 Tutorial 5 (August 23, 2007)
 Tutorial 6 (August 30, 2007)
 Tutorial 7 (September 06, 2007)
 Tutorial 8 (September 27, 2007)
 Tutorial 9 (October 04 and 11, 2007)
 Tutorial 10 (November 01 and 08, 2007) [Not proofchecked]
Tests
