|Pre-requisites: Fundamental of Mathematics||3||0||0||3|
The Ideas of Discrete Mathematics are the fundamental to the science and technology specific to the computer age. This subject provides an introduction to some fundamental concepts in Discrete Mathematics for the students. The topics covered include: mathematical logic, proof techniques, especially mathematical induction, set theory, functions, and relations, procedures, recursion, and operation counts, recurrence relations, analysis of algorithms, counting methods, permutations and combinations, graphs and trees.
The objective of this course is to:
- develop a foundation of set theory concepts and notation
- explore a variety of various mathematical structures by focusing on mathematical objects, operations, and resulting properties
- develop formal logical reasoning techniques and notation
- demonstrate the application of logic to analyzing and writing proofs
- develop techniques for counting, permutations and combinations
- develop the concept of relation through various representations (digraphs, matrices, lists).
At the end of the course student will be able to:
- construct proofs using direct proof, proof by contraposition, proof by contradiction, proof by cases
- construct mathematical arguments using logical connectives and quantifiers and verify the correctness of an argument using propositional and predicate logic and truth tables.
- demonstrate the ability to solve problems using counting techniques and combinatory in the context of discrete probability.
- solve problems involving recurrence relations and generating functions.
- perform operations on discrete structures such as sets, functions, relations and sequence
Unit I: Set Theory
Introduction, Combination of sets, Multisets, Ordered pairs. Proofs of some general identities on sets. Relations: Definition, Operations on relations, Properties of relations, Composite Relations, Equality of relations, Recursive definition of relation, Order of relations. Functions: Definition, Classification of functions, Operations on functions, Recursively defined functions, Growth of Functions, Natural Numbers: Introduction, Mathematical Induction, Variants of Induction, Induction with Nonzero Base cases. Proof Methods, Proof by counter – example, Proof by contradiction.
Unit II: Algebraic Structures
Definition, Groups, Subgroups and order, Cyclic Groups, Cosets, Lagrange’s theorem, Normal Subgroups, Permutation and Symmetric groups, Group Homomorphisms, Definition and elementary properties of Rings and Fields, Integers Modulo n.
Unit III: Partial order sets
Definition, Partial order sets, Combination of partial order sets, Hasse diagram. Lattices: Definition, Properties of lattices – Bounded, Complemented, Modular and Complete lattice. Boolean Algebra: Introduction, Axioms and Theorems of Boolean algebra, Algebraic manipulation of Boolean expressions. Simplification of Boolean Functions, Karnaugh maps, Logic gates, Digital circuits and Boolean algebra.
Unit IV: Propositional Logic
Proposition, well-formed formula, Truth tables, Tautology, Satisfiability, Contradiction, Algebra of proposition, Theory of Inference Predicate Logic: First order predicate, well-formed formula of predicate, quantifiers, Inference theory of predicate logic.
Unit V: Trees
Definition, Binary tree, Binary tree traversal, Binary search tree. Graphs: Definition and terminology, Representation of graphs, Multigraphs, Bipartite graphs, Planar graphs, Isomorphism and Homeomorphism of graphs, Euler and Hamiltonian paths, Graph coloring Recurrence Relation & Generating function: Recursive definition of functions, Recursive algorithms, Method of solving recurrences. Combinatory, Introduction, Counting Techniques, Pigeonhole Principle
- Elements of Distcrete Mathematics – Liu and Mohapatra, McGraw Hill Publications
- Discrete Mathematical Structures – B. Kolman, R.C. Busby, and S.C. Ross, PHI Publications
- Discrete Mathematical Structures with Application to Computer Science – Jean Paul Trembley and R Manohar, McGraw-Hill Publications
- Discrete and Combinatorial Mathematics – R.P. Grimaldi, Addison Wesley
- Discrete Mathematics and Its Applications – Kenneth H. Rosen, McGraw-Hill