Discrete Mathematics

Unit 1

Set Theory: Introduction, Size of sets and Cardinals, Venn diagrams, Combination of sets, Multisets, Ordered pairs and Set Identities. Relation: 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.

Unit 2

Posets, Hasse Diagram and Lattices: Introduction, Partial ordered sets, Combination of Partial ordered 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.

Unit 3

Propositional: Propositions, Truth tables, Tautology, Contradiction, Algebra of Propositions, Theory of Inference and Natural Detection. Predicate Logic: Theory of Predicates, First order predicate, Predicate formulas, Quantifiers, Inference theory of predicate logic.

Unit 4

Algebraic Structures: Introduction to algebraic Structures and properties. Types of algebraic structures: Semi group, Monoid, Group, Abelian group and Properties of group. Subgroup, Cyclic group, Cosets, Permutation groups, Homomorphism and Isomorphism of groups. Rings and Fields: Definition and elementary properties of Rings and Fields.

Unit 5

Natural Numbers: Introduction, Piano’s axioms, Mathematical Induction, Strong Induction and Induction with Nonzero Base cases. Recurrence Relation & Generating functions: Introduction and properties of Generating Functions. Simple Recurrence relation with constant coefficients and Linear recurrence relation without constant coefficients. Methods of solving recurrences. Combinatorics: Introduction, Counting techniques and Pigeonhole principle, Polya’s Counting theorem.