**CHHATTISGARH SWAMI VIVEKANAND TECHNICAL UNIVERSITY, BHILAI (C. G.)**

**Semester: B.E. IV Sem. Branch: Information Technology**

**Subject: Discrete Mathematical Structures**

UNIT – 1 MATHEMATICAL LOGIC & BOOLEAN ALGEBRA (No. of periods 8+2)

Basic concept of mathematical logic, Statements, Connectives, Conditional and biconditional statements,

Logical equivalence, Logical implication & quantifiers, Basic concept of Boolean Algebra, Properties of

Boolean Algebra, Boolean functions, Disjunctive & conjunctive normal forms of Boolean functions,

Applications of Boolean Algebra in switching circuits & logic circuits.

UNIT – 2 SET THEORY, RELATIONS, FUNCTIONS (No. of periods 8+2)

Basic concept of set theory, Relations, Properties of relation in a set, Equivalence relation, Composition of

relations, Partial order & total order relations, Lattices & Hasse diagram, Introduction to function, Inverse,

Identity, Injective, Surjective & Bijective functions, Composition of functions and some special functions.

UNIT – 3 ALGEBRAIC STRUCTURES (No. of periods 8+2)

Groups, Subgroups, Cosets, Lagrange’s theorem, Isomorphism, Automorphism, Homomorphism, Codes &

group codes, Rings, Integral domains and Fields.

UNIT – 4 GRAPH THEORY (No. of periods 8+2)

Introduction to graph theory, Walks, Paths & Circuits, Types of graphs, Shortest path problems, Eulerian and

Hamiltonian graphs, Basic concept of tree: spanning tree, minimum spanning tree, search tree, rooted binary

tree, Cut sets, Network flow, Matrix representation of graphs.

UNIT – 5 COMBINATORICS (No. of periods 8+2)

Permutation and combination, Pigeon-hole principle, Mathematical induction, Principle of Inclusion and

Exclusion, Generating function, Recurrence relation.

TEXT BOOKS: –

1. Elements of discrete mathematics by C.L. Liu, Tata McGraw-Hill, publications.

2. Discrete Mathematical structures, by Bernard Kolman, Robert C. Busby and Sharon Cutler Ross, Pearson

Education.

REFERENCE BOOKS: –

1. A Text Book of Discrete Mathematics, Swapan Kumar Sarkar, S. Chand & Compeny Ltd.

2. Graph theory with applications to engineering and computer science, by Narsingh Deo, Prentice Hall of India.

3. Discrete mathematics for computer scientists and mathematicians, by J.L. Mott, A. Kandel and T.P. Baker,

Prentice Hall of India.

4. Discrete Mathematical Structures with applications to computer science, by J.P. Tremblay and R. Manohar,

Tata McGraw-Hill.