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, Algebra of 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, Functions, Types of functions. 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,
Double counting, Linear recurrence relation-method of solutions, Generating functions, Permutations and counting.

Basic graph theory: Graph, Subgraphs, Isomorphism, Walks, Paths, Circuits, Euler graph, Hamiltonian graph, Planar graph.

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.


Lecture & Tutorial schedule


DMS Lectures

Lectures Link
Lecture 0 PDF
Lecture 1 PDF
Lecture 2 PDF
Lecture 3 PDF
Lecture 4 PDF
Lecture 5 PDF
Lecture 6 PDF
Lecture 7 PDF
Lecture 8 PDF
Lecture 9 PDF
Lecture 10 PDF
Lecture 11 PDF
Lecture 12 PDF
Lecture 13 PDF
Lecture 14 PDF
Lecture 15 PDF
Lecture 16 PDF
Lecture 17 PDF
Lecture 18 PDF
Lecture 19 PDF
Lecture 20 PDF