**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

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 c