Course schedule
Syllabus
References
Tutorial exercises
Tests
|
Course schedule
Time: Slot D (M 11:30-12:25, Tu 09:30-11:25, Th 07:30-08: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öder-Bernstein theorem.
| | Combinatorics |
Basic counting techniques: inclusion and exclusion,
pigeon-hole 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 text-book 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 (Editor-in-chief), 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 McGraw-Hill.
Bernard Kolman, Robert C Busby, and Sharon Cutler Ross, Discrete Mathematical Structures, fifth edition, Prentice-Hall 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 McGraw-Hill.
Augmenting hand-outs
- 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
|