# Discrete Mathematics

Set Theory:  Introduction, Size of sets and cardinals, Venn diagrams, Combination of sets, Multisets, Ordered pairs and Set identities.
Relations & Functions: Relations - Definition, Operations on relations, Composite relations, Properties of
relations, Equality of relations, Partial order relation. Functions - Definition, Classification of functions,
Operations on functions, Recursively defined functions.
Notion of Proof:  Introduction, Mathematical Induction, Strong Induction and Induction with Nonzero base
cases.

Unit-II
Algebraic Structures:  Definition, Properties, Types: Semi  Groups, Monoid, Groups, Abelian Groups.
Subgroups and order, Cyclic Groups, Cosets, Normal Subgroups, Permutation and Symmetric groups,
Homomorphisms and isomorphism of Groups, Definition and elementary properties of Rings and Fields:
definition and standard results.

Unit-III
Lattices: Introduction, Partial order sets, Combination of partial order sets, Hasse diagram, Introduction of
lattices, Properties of lattices – Bounded, Complemented, Modular and Complete lattice.

Boolean Algebra:  Introduction, Axioms and Theorems of Boolean algebra, Boolean functions.
Simplification of Boolean Functions, Karnaugh maps, Logic gates, Digital circuits and Boolean algebra.

Unit-IV
Propositional & Predicate Logic:  Propositions, Truth tables, Tautology, Contradiction, Algebra of
propositions, Theory of Inference and Natural Deduction. Theory of predicates, First order predicate,
Predicate formulas, quantifiers, Inference theory of predicate logic.
Unit-V
Trees & Graphs:  Trees - Definition, Binary trees, Binary tree  traversal, Binary search trees. Graphs -
Definition and terminology, Representation of graphs, Bipartite graphs, Planar graphs, Isomorphism and
Homeomorphism of graphs, Multigraphs, Euler and Hamiltonian paths, Graph coloring.

Recurrence Relations:  Introduction, Growth of functions, Recurrences from algorithms, Methods of
solving recurrences.
Combinatorics: Introduction, Counting Techniques, Pigeonhole Principle, Pólya’s Counting Theory.

Paper Code: