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


Tutorial discription

Topics Tutorial Sheet
Tutorial Sheet-1 PDF
Tutorial Sheet-2 PDF
Tutorial Sheet 3 PDF
Tutorial Sheet 4 PDF
Tutorial Sheet 5 PDF
Tutorial Sheet 6 PDF


Tentative Assesment Schedule

Component Assesment Date
C-1 C1 Quiz 6th April
C1 Review Test 24th April
C-2 C2 Quiz 17th May
C2 Review Test 31st May
C-3 C3 Review test 12th June



Marking Schemes

Exams Marking Scheme
Quiz-1 PDF
Review Test-1 PDF
Quiz-2 PDF
Review Test-2 PDF
Review Test-3 PDF







DMS Marks: Jan - July, 2023

    Log-In using your LDAP credentials