- 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 group theory.
- Introduction to graph theory.

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:

- Contents and Chapter 1 (
**Counting**) - Chapter 2 (
**Cryptography and Number Theory**) - Chapter 3 (
**Reflections on Logic and Proof**) - Chapter 4 (
**Induction, Recursion and Recurrences**) - Chapter 5 (
**Probability**) - Chapter 6 (
**Graphs**) and Index

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

- Notes on cardinality and infinite
sets (ps, pdf.) Lecture 2 from Christian Scheideler's 2001
class on Complexity Theory.
**Note**: Additional notes on Set Theory including the proof of Zorn's Lemma have been photocopied and given to the SCOOPs xerox shop. Please collect them from there. - Notes on partial orders, well orders and the principle of well ordered induction (ps, pdf.) Lecture 38 from Jonathan Pila's 2004-05 class on Discrete Mathematics.
- Intro to probability theory. (ps, pdf.)

*C. L. Liu.***Elements of Discrete Mathematics**.*Alan Tucker.***Applied Combinatorics**.*R. L. Graham, D. E. Knuth, O. Patashnik.***Concrete Mathematics**.

- Tutorial Sheet 1. Propositional Logic. (ps,
pdf.) Posted 1st August 2005.
- Tutorial Sheet 2. Sets and Mathematical Induction. (ps, pdf.) Posted 7th August
2005.
- Tutorial Sheet 3. Set Theory. (ps, pdf.) Posted 15th August 2005.
**Important:**I have posted a**major clarification**to the statement of Zorn's Lemma and the solution to Problem 1 (ps, pdf.) Please take a look at this, it will help you solve problem 1 of homework 3. Posted 21st August 2005. - Tutorial Sheet 4. Pigeonhole Principle. (ps, pdf.) Posted 23rd August
2005.
- Tutorial Sheet 5. Generating Functions. (ps, pdf.) Posted 29th August
2005.
- Tutorial Sheet 6. Recurrences. (ps, pdf.) Posted 13th September
2005.
- Tutorial Sheet 7. Graph Theory: Paths and Cycles. (ps, pdf.) Posted 20th September
2005.
- Tutorial Sheet 8. Graph Theory: continued. (ps, pdf.) Posted 27th September
2005.
**Correction**: In the first line of Problem 3 "smallest" has been replaced by "largest." Posted 1st October 2005.**Note**: The proof of Vizing's theorem discussed in class is available online. - Tutorial Sheet 9. Graph Theory: Matchings. (ps, pdf.) Posted 25th October
2005.
- Tutorial Sheet 10. Graph Theory: Connectivity. (ps, pdf.) Posted 7th November
2005.
- Tutorial Sheet 11. Discrete Probability: Sudoku. (ps, pdf.) Posted 14th November
2005. New version posted on 15th November 2005 after Rohit
pointed out an error in the earlier version.
- Tutorial Sheet 12. Discrete Probability. (ps, pdf.) Posted 21st November 2005.

- Homework 1. (ps, pdf.) Posted 5th August 2005. Due:
**12th August 2005**at the start of class.

- Homework 2. (ps, pdf.) Posted 12th August 2005. Due:
**19th August 2005**at the start of class. Modified 19th August 2005. - Homework 3. (ps, pdf.) Posted 19th August 2005. Due:
**26th August 2005**at the start of class. - Homework 4. (ps, pdf.)
Posted 9th September 2005. Due:
**15th September 2005**at the start of class. - Homework 5. (ps, pdf.)
Posted 15th September 2005. Due:
**22nd September 2005**at the start of class. - Homework 6. (ps, pdf.)
Posted 27th September 2005. Due:
**4th October 2005**at the start of class. - Homework 7. Solve Minor II. Write all proofs completely and in a
well organized manner. Homeworks will be graded on understanding
**and**presentation. Posted 21st October 2005. Due:**28th October 2005**at the start of class. - Homework 8. (ps, pdf.)
Posted 27th October 2005. Due:
**8th November 2005**at the start of class. - Homework 9. (ps, pdf.)
Posted 10th November 2005. Due:
**18th November 2005**at the start of class. - Homework 10 and 11. (ps, pdf.)
Posted 20th November 2005. Due:
**29th November 2005**before 11 AM. Slip it under my office door if there is no class that day.

The marks obtained in this homework will be divided up into two as follows.- Case 1. If you score
*k*>= 5 out of 10: Your two homework scores will be 5 and*k*-5. - Case 2. If you score
*k*< 5 out of 10: Your two homework scores will be*k*and 0.

- Case 1. If you score

- 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