CHHATTISGARH SWAMI VIVEKANAND TECHNICAL UNIVERSITY, BHILAI (C. G.)
Semester: B.E. 4th Sem. Branch: Computer Science & Engg.
Subject: Discrete 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
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,
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 c