# Discrete Structures

Below is the syllabus for Discrete Structures:-

## Unit 1

Set Theory & Logic

Fundamentals – Sets and subsets, Venn Diagrams, Operations on sets, Laws of Set Theory, Power Sets and Products, Partition of sets, The Principle of Inclusion-Exclusion.

Logic: Propositions and Logical operations, Truth tables, Equivalence, Implications, Laws of Logic, Normal forms, Predicates and quantifiers, Mathematical Induction.

## Unit 2

Relations, diagraphs, and lattices

Product sets and partitions, relations and diagraphs, paths in relations and digraphs, properties of relations, equivalence and partially ordered relations, a computer representation of relations and diagraphs, manipulation of relations, Transitive closure, and Warshall’s algorithm, Posets and Hasse Diagrams, Lattice.

## Unit 3

Functions and Combinatorics

Definitions and types of functions: injective, subjective and bijective, Composition, identity and inverse, Review of Permutation and combination-Mathematical Induction, Pigeon hole principle, Principle of inclusion and exclusion, Generating function-Recurrence relations.

## Unit 4

Algebraic Structures

Algebraic structures with one binary operation – semigroups, monoids and groups, Product and quotient of algebraic structures, Isomorphism, homomorphism, automorphism, Cyclic groups, Normal sub-group, codes and group codes, Ring homomorphism, and Isomorphism.

## Books:

• Elements of Discrete Mathematics C.L Liu, 1985, Reprinted 2000, McGraw Hill
• Discrete mathematical structures by B Kolman RC Busby, S Ross PHI Pvt.
• Discrete Mathematics by Bisht & Dhami, Oxford University Press,2015

## Reference:

• Discrete Mathematical Structures with Applications to Computer Science, by Tremblay P, and Manohar R., McGraw Hill Book Company, 1975, International Edition, 1987.
• Discrete and Combinatorial mathematics “, Ralph, Grimaldi, Addison-Wesley Publishing Company, Reprinted in 1985.
• Discrete Mathematics and its Applications “, Kenneth H.Rosen, McGraw Hill Book Company, 1999. Sections: 7.1 to 7.5.
• Discrete Mathematics for computer scientists and Mathematicians, Joe L. Mott, Abraham