Discrete Mathematics (BTCS 401-18)

Detailed Contents

Module 1: Sets, Relation and Function

• Operations and Laws of Sets
• Cartesian Products
• Binary Relation
• Partial Ordering Relation
• Equivalence Relation
• Image of a Set
• Sum and Product of Functions
• Bijective functions
• Inverse and Composite Function
• Size of a Set
• Finite and infinite Sets
• Countable and uncountable Sets
• Cantor's diagonal argument and The Power Set theorem
• Schroeder-Bernstein theorem

Principles of Mathematical Induction

• The Well-Ordering Principle
• Recursive definition
• The Division algorithm: Prime Numbers
• The Greatest Common Divisor: Euclidean Algorithm
• The Fundamental Theorem of Arithmetic

Module 2: Basic Counting Techniques

• Inclusion and exclusion
• Pigeon-hole principle
• Permutation and combination

Module 3: Propositional Logic & Proof Techniques

Propositional Logic

• Syntax, Semantics, Validity and Satisfiability
• Basic Connectives and Truth Tables
• Logical Equivalence: The Laws of Logic
• Logical Implication
• Rules of Inference
• The use of Quantifiers

Proof Techniques

• Some Terminology
• Proof Methods and Strategies
• Forward Proof
• Proof by Contradiction
• Proof by Contraposition
• Proof of Necessity and Sufficiency

Module 4: Algebraic Structures and Morphism

• Algebraic Structures with one Binary Operation
• Semi Groups, Monoids, Groups
• Congruence Relation and Quotient Structures
• Free and Cyclic Monoids and Groups
• Permutation Groups
• Substructures, Normal Subgroups
• Algebraic Structures with two Binary Operation
• Rings, Integral Domain and Fields
• Boolean Algebra and Boolean Ring
• Identities of Boolean Algebra, Duality
• Representation of Boolean Function
• Disjunctive and Conjunctive Normal Form

Module 5: Graphs and Trees

• Graphs and their properties, Degree, Connectivity, Path, Cycle, Sub Graph, Isomorphism
• Eulerian and Hamiltonian Walks
• Graph Colouring, Colouring maps and Planar Graphs, Colouring Vertices, Colouring Edges, List Colouring, Perfect Graph
• Definition, properties and Example, rooted trees, trees and sorting, weighted trees and prefix codes
• Biconnected component and Articulation Points
• Shortest distances

Suggested Books

• Kenneth H. Rosen, Discrete Mathematics and its Applications, Tata McGraw – Hill
• Susanna S. Epp, Discrete Mathematics with Applications, 4th edition, Wadsworth Publishing Co. Inc.
• C L Liu and D P Mohapatra, Elements of Discrete Mathematics A Computer Oriented Approach, 3rd Edition by, Tata McGraw – Hill.

Suggested Reference Books

• J.P. Tremblay and R. Manohar, Discrete Mathematical Structure and Its Application to Computer Science”, TMG Edition, TataMcgraw-Hill
• Norman L. Biggs, Discrete Mathematics, 2nd Edition, Oxford University Press.
• Schaum’s Outlines Series, Seymour Lipschutz, Marc Lipson, Discrete Mathematics, Tata McGraw - Hill

Course Outcomes

1. To be able to express logical sentence in terms of predicates, quantifiers, and logical connectives
2. To derive the solution for a given problem using deductive logic and prove the solution based on logical inference
3. For a given a mathematical problem, classify its algebraic structure
4. To evaluate Boolean functions and simplify expressions using the properties of Boolean algebra
5. To develop the given problem as graph networks and solve with techniques of graph theory.