Discrete Mathematics


Course outlines:

Introduction to propositional logic: Motivation, Discrete objects, Proposition, Connectives, Truth table, Compound statement, Propositional equivalence, Tautology, Contradiction, Contingency, Laws of proposition, Dual of proposition, Argument and its validity, Predicates or Propositional function, Quantifiers: universal and existential quantifiers.

Introduction, Sets & Functions: Sets, Operations on sets, Power set, Inclusion and exclusion principle, Multi set, Operations on multi sets, Cartesian product, Binary relation, Domain and range of relation, Complement of relation, Inverse of relation, Composition of relation, Types of relation, Equivalence relation, Partial order relation, Partially ordered set, Well ordered set, Maximal and minimal element, Infimum and Supremum, Order completeness axiom, Similar sets, Countable set, Uncountable set.

Proof Techniques: Direct proof, Proof by contradiction, Proof by contrapositive, Proof by cases, Proof by counter example, Proof by mathematical induction: Various form of mathematical induction Deductions, Resolution, Mathematical proofs.

Counting & Combinatorics: Counting, Sum and product rule, Principle of inclusion exclusion, Pigeon hole principal, Counting by bijection, Linear recurrence relation-method of solutions, Generating functions, Permutations and counting.

Basic graph theory: Graph, Subgraphs, Constructions of new graphs from existing graphs, Connected graph, Isomorphism, Walks, Paths, Cycle, Tree, Euler graph, Hamiltonian graph, Planar graph, Graph homeomorphism, Kuratowski’s Theorem.

Algebraic structures: Group, Subgroups, Lagrange theorem, Rings and Fields.

Text book: Kenneth H. Rosen, Discrete mathematics and its application, Tata McGraw Hill.

Reference books: 1: Eric Lehman, F Thomson Leighton, Albert R Meyer, Mathematics for computer science.
                              2: Huth and Ryan, Logic in computer science, Cambridge University Press.

DMS Lectures

Lectures Link
Lecture 0 (Motivation) PDF
Lecture 1 (Proposition and its equivalence) PDF
Lecture 2 (Predicates and Quantifiers) PDF
Lecture 3 (Basics of Set Theory) PDF
Lecture 4 (Relations and Equivalence Relation) PDF
Lecture 5 (Partial Order Relation) PDF
Lecture 6 (Equivalent Sets) PDF
Lecture 7 (Countable and uncountable Sets) PDF
Lecture 8 (Proof Techniques) PDF
Lecture 9 (Counting Techniques) PDF
Lecture 10 (Recurrence Relation) PDF
Lecture 11 (Generating function) PDF

DMS Tutorials

Tutorial Sheet Link
Tutorial Sheet 1 PDF
Tutorial Sheet 2 PDF
Tutorial Sheet 3 PDF
Tutorial Sheet 4 PDF
Tutorial Sheet 5 PDF