CSL105: Discrete Mathematical Structures
I semester: 2006-07
Amitabha Bagchi
Topics
- 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.
Course Texts
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.
Additional Notes
- 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 Sheets
- 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 Assignments
- 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.
Evaluation
- 35%: homework assignments. Only the best seven will be counted.
- 20%: quizzes. Only the best four will be counted.
- 10%: I Minor Exam.
- 10%: II Minor Exam.
- 25%: Major Exam.
Amitabha Bagchi