# Discrete Structures and Graph Theory for UPTU ( III-CSE/IT-2013 course )

Set theory
Algebraic structures
Partial order sets
Propositional logic
Trees
1st edition, by Deena nath Gupta

## Book Details

Set theory : Introduction, Combination of sets, Multisets, Ordered pairs, Set identities. Relations : Definition, Operations on relations, Properties of relations, Composite relations, Equality of relations, Order of relations. Functions : Definition, Classification of functions, Operations on functions, Recursively defined functions. Natural numbers : Introduction, Mathematical induction, Variants of induction, Induction with nonzero base cases. Algebraic structures : Definition, Groups, Subgroups and order, Cyclic groups, Cosets, Lagrange's theorem, Normal subgroups, Permutation and symmetric groups, Group homomorphisms, Definition and elementary properties of rings and fields, Integers modulo n. Partial order sets : Definition, Partial order sets, Combination of partial order sets, Hasse diagram. Lattices : Definition, Properties of lattices - Bounded, Complemented, Modular and complete lattice. Morphisms of lattices. Boolean algebra : Introduction, Axioms and theorems of Boolean algebra, Algebraic manipulation of Boolean expressions. Simplification of Boolean functions, Karnaugh maps, Logic gates, Digital circuits and Boolean algebra. Combinational and sequential circuits. Propositional logic : Proposition, Well formed formula, Truth tables, Tautology, Satisfiability, Contradiction, Algebra of proposition, Theory of inference, Natural deduction. Predicate logic : First order predicate, Well formed formula of predicate, Quantifiers, Inference theory of predicate logic. Trees : Definition, Binary tree, Binary tree traversal, Binary search tree. Graphs : Definition and terminology, Representation of graphs, Multigraphs, Bipartite graphs, Planar graphs, Isomorphism and homeomorphism of graphs, Euler and Hamitonian paths, Graph coloring. Recurrence relation and generating function : Recursive definition of functions, Recursive algorithms, Method of solving recurrences. Combinatorics : Introduction, Counting techniques, Pigeonhole principle.