CSL105: Discrete Mathematical Structures

I semester: 2006-07

Basic logic: Propositional logic: logical connectives; truth tables; normal forms (conjunctive and disjunctive); validity; predicate logic; limitations of predicate logic, universal and existential quantification; modus ponens and modus tollens. Proof techniques: Notions of implication, converse, inverse, contrapositive, negation, and contradiction; the structure of formal proofs; direct proofs; proof by couunterexample; proof by contraposition; proof by contradiction; mathematical induction; strong induction; recursive mathematical definitions; well orderings.
Fundamental structures; Functions (surjections, injections, inverses, composition); relations (reflexivity, symmetry, transitivity, equivalence relations); sets (Venn diagrams, complements, Cartesian products, power sets); pigeonhole principle; cardinality and countability.
Basics of counting: Counting arguments; pigeonhole principle; permutations and combinations; inclusion-exclusion, recurrence relations, generating functions.
Introduction to graph theory.

A list of useful reference texts (students are not required to own or consult these.)

C. L. Liu. Elements of Discrete Mathematics.
Alan Tucker. Applied Combinatorics.
R. L. Graham, D. E. Knuth, O. Patashnik. Concrete Mathematics.
K. Bogart, S. Drysdale, C. Stein. Discrete Math for Computer Science Students.
Available online.

For the purposes of this class the book has been mirrored locally. You can either download the entire book or you can choose to download it chapterwise:

For Graph Theory, an excellent text available free online (though in unprintable format) is Graph Theory by Reinhard Diestel.

For topics not covered in this text, notes or references will be provided in the Additional Notes section below.

S. Arun-Kumar's notes on sets, relations and functions. (ps, pdf.)
Notes on propositional calculus and Hilbert systems. (ps, pdf.) Posted 16th August 2006.
(Based on Michael Ben-Ari's book Mathematical Logic for Computer Science. )
The lectures on basic counting (7th and 8th September) were based on Chapter 1 of Bogart, Drysdale and Stein's book, linked above. However not all the class discussion is found in that chapter so please supplement that reading with class notes (especially the part about upper and lower bounds.)
The proof of Vizing's theorem discussed in class is available online.

Tutorial Sheet 1. Sets, relations and functions. (ps, pdf.) Posted 26th July 2006.
Tutorial Sheet 2. Sets/Mathematical induction. (ps, pdf.) Posted 6th August 2006.
Tutorial Sheet 3. Propositional calculus and Hilbert systems. (ps, pdf.) Posted 10th August 2006.
Tutorial Sheet 4. Predicate logic etc. (ps, pdf.) Posted 17th August 2006.
Tutorial Sheet 5. Group theory. (ps, pdf.) Posted 30th August 2006.
Tutorial Sheet 6. Counting. (ps, pdf.) Posted 10th September 2006.
Tutorial Sheet 7. Recurrences. (ps, pdf.) Posted 14th September 2006.
Tutorial Sheet 8. Pigeonhole Principle. (ps, pdf.) Posted 23rd September 2006.
Tutorial Sheet 9. Graph Theory: Paths and Cycles. (ps, pdf.) Posted 28th September 2006.
Tutorial Sheet 10. Graph Theory continued. (ps, pdf.) Posted 8th October 2006.
Tutorial Sheet 11. Graph Theory: Matchings. (ps, pdf.) Posted 2nd November 2006.
Tutorial Sheet 12. Graph Theory: Connectivity. (ps, pdf.) Posted 9th November 2006.
Tutorial Sheet 13. Semester review. (ps, pdf.) Posted 19th November 2006.

Homework 1. (ps, pdf.) Posted 28th July 2006. Due: 4th August 2005 at the start of class.
Homework 2. (ps, pdf.) Posted 3rd August 2006. Due: 11th August 2005 at the start of class.
Homework 3. (ps, pdf.) Posted 10th August 2006. Due: 18th August 2005 at the start of class.
Note: Notes which can help with this homework have been posted.
Also there will be a tutorial at 1PM on Thursday the 17th of August in VI 401.
Homework 4. (ps, pdf.) Posted 17th August 2006. Due: 25th August 2006 at the start of class.
Homework 5. (ps, pdf.) Posted 10th September 2006. Due: 14th September 2006 at the start of class.
Homework 6. (ps, pdf.) Posted 14th September 2006. Due: 21st September 2006 at the start of class.
Homework 7. (ps, pdf.) Posted 23rd September 2006. Due: 29th September 2006 at the start of class.
Homework 8. (ps, pdf.) Posted 28th September 2006. Due: 6th October 2006 at the start of class.
Homework 9. (ps, pdf.) Posted 8th October 2006. Due: 20th October 2006 at the start of class.
Homework 10. (ps, pdf.) Posted 2nd November 2006. Due: 10th November 2006 at the start of class.
Homework 11. (ps, pdf.) Posted 9th November 2006. Due: 17th November 2006 at the start of class.
Homework 12. (ps, pdf.) Posted 15th November 2006. Due: 24th November 2006 at the start of class.
Homework 13. (ps, pdf.) Posted 24th November 2006. Due: 2nd December 2006 before the major exam begins.