Discrete Mathematics

CHAPTER 1: SET RELATION FUNCTION 1.1: INTRODUCTION 1.2: SETS 1.2.1: Representation of a Set 1.2.2: Sets of Special Status 1.2.3: Universal Set and Empty Set 1.2.4: Subsets 1.2.5: Power set 1.2.6: Cardinality of a Set 1.3: ORDERED PAIRS 1.3.1: Cartesian Product of Sets 1.3.2: Properties of Cartesian Product 1.4: VENN DIAGRAMS 1.5: OPERATIONS ON SETS 1.5.1: Union of Sets 1.5.2: Intersections of Set 1.5.3: Complements 1.5.4: Symmetric Difference 1.6: COUNTABLE AND UNCOUNTABLE SETS 1.7: ALGEBRA OF SETS 1.8: MULTISET 1.8.1: Operations on Multisets 1.9: FUZZY SET 1.9.1: Operations on Fuzzy Set 1.10: GROWTH OF FUNCTION 1.11: COMPUTER REPRESENTATION OF SETS 1.12: INTRODUCTION 1.13: BINARY RELATION 1.14: CLASSIFICATION OF RELATIONS 1.14.1: Reflexive Relation 1.14.2: Symmetric Relation 1.14.3: Antisymmetric Relation 1.14.4: Transitive Relation 1.14.5: Equivalence Relation 1.14.6: Associative Relation 1.15: COMPOSITION OF RELATIONS 1.16: INVERSE OF A RELATION 1.17: REPRESENTATION OF RELATIONS ON A SET 1.18: CLOSURE OPERATION ON RELATIONS 1.18.1: Reflexive Closure 1.18.2: Symmetric Closure 1.19: MATRIX REPRESENTATION OF RELATION 1.20: DIGRAPHS 1.20.1: Transitive Closure 1.20.2: Warshall's Algorithm 1.21: PARTIAL ORDERING RELATION 1.22: n-ARY RELATIONS AND THEIR APPLICATIONS 1.23: RELATIONAL MODEL FOR DATABASES 1.24: INTRODUCTION 1.25: ADDITION AND MULTIPLICATION OF FUNCTIONS 1.26: CLASSIFICATION OF FUNCTIONS 1.26.1: One-to-one (Injective) Function 1.26.2: Onto (Surjective) Functions 1.26.3: One-to-one, Onto (Bijective) Function 1.26.4: Identity Function 1.26.5: Constant Function 1.27: COMPOSITION OF FUNCTION 1.27.1: Associativity of Composition of Functions 1.28: INVERSE FUNCTION 1.28.1: Invertible Function 1.28.2: Image of a Subset 1.29: HASH FUNCTION 1.30: RECURSIVELY DEFINED FUNCTIONS 1.31: SOME SPECIAL FUNCTIONS 1.31.1: Floor and Ceiling Functions 1.31.2: Integer and Absolute Value Functions 1.31.3: Remainder Function 1.32: FUNCTIONS OF COMPUTER SCIENCE 1.32.1: Partial and Total Functions 1.32.2: Primitive Recursive Function 1.32.3: Ackermann Function 1.33: THE INCLUSION-EXCLUSION PRINCIPLE 1.33.1: Applications of Inclusion - Exclusion Principle 1.34: SEQUENCE AND SUMMATION 1.34.1: Sequence 1.34.2: Summation Summary Exercise 1 CHAPTER 2 COMBINATORICS 2.1: INTRODUCTION 2.2: BASIC PRINCIPLES OF COUNTING 2.2.1: Multiplication Principle (The Principles of Sequential Counting) 2.2.2: Addition Rule ( The Principle of Disjunctive Counting) 2.3: FACTORIAL NOTATION 2.4: BINOMIAL THEOREM 2.4.1: Pascal's Triangle 2.4.2: Multinomial Theorem 2.5: PERMUTATIONS (Arrangements of Objects) 2.5.1: Permutations with Repetitions 2.5.2: Circular Permutations 2.6: COMBINATIONS (Selection of Objects) 2.6.1: Combinations of n Different Objects 2.6.2: Combinations with Repetitions 2.7: DISCRETE PROBABILITY 2.7.1: Terminology (Basic Concepts) 2.8: FINITE PROBABILITY SPACES 2.9: PROBABILITY OF AN EVENT 2.9.1: Axioms of Probability 2.9.2: Odds in favour and Odds against an Event 2.9.3: Addition Principle 2.10: CONDITIONAL PROBABILITY 2.10.1: Multiplication Rule 2.11: INDEPENDENT REPEATED TRIALS, BINOMIAL DISTRIBUTION 2.11.1: Repeated Trials with Two Outcomes, Bernoulli Trials 2.12: RANDOM VARIABLES 2.12.1: Probability Distribution of a Random Variable 2.12.2: Expectation of a Random Variable 2.12.3: Variance and Standard Deviation of a Random Variable 2.12.4: Binomial Distribution 2.13: RECURSION 2.13.1: Recursively Defined Sequences 2.13.2: Recursive Definitions 2.13.3: Recursively Defined Sets 2.13.4: Recursively Defined Functions 2.14: RECURENCE RELATION 2.14.1: Order and Degree of Recurrence Relation 2.14.2: Linear Homogenous and Non-homogeneous Recurrence Relations 2.14.3: Solution of Linear Recurrence Relation with Constant Coefficients 2.14.4: Homogenous Solution 2.14.5: Particular Solution 2.15: GENERATING FUNCTIONS 2.16: COUNTING (COMBINATORIAL) METHOD 2.17: THE PIGEONHOLE PRINCPLE 2.17.1: Generalized Pigeonhole Principle Summary Exercise 2 CHAPTER 3 MATHEMATICAL LOGIC 3.1: INTRODUCTION 3.2: STATEMENT (PROPOSITIONS) 3.3: LAWS OF FORMAL LOGIC 3.3.1: Law of Contradiction 3.3.2: Law of Intermediate Exclusion 3.4: BASIC SET OF LOGICAL OPERATORS /OPERATIONS 3.4.1: Conjunction (AND, ) 3.4.2: Disjunction (OR, ) 3.4.3: Negation (NOT, ~ ) 3.5: PROPOSITIONS AND TRUTH TABLES 3.5.1: Connectives 3.5.2: Compound Propositions 3.5.3: Conditional Statement 3.5.4: Converse, Contrapositive, and Inverse 3.5.5: Biconditional Statement 3.6: ALGEBRA OF PROPOSITIONS 3.7: PROPOSITIONAL FUNCTIONS 3.8: TAUTOLOGIES AND CONTRADICTIONS 3.9: LOGICAL EQUIVALENCE 3.9.1: De Morgan Laws 3.10: LOGICAL IMPLICATION 3.11: NORMAL FORMS 3.11.1: Disjunctive Normal Form (dnf) 3.11.2: Conjunctive Normal Form (cnf) 3.12: ARGUMENTS 3.13: RULES OF INFERENCE 3.13.1: Law of Detachment (or Modus Pones) 3.13.2: Law of Contraposition (Modus tollens) 3.13.3: Disjunctive Syllogism 3.13.4: Hypothetical Syllogism 3.14: WELL FORMED FORMULAE 3.15: PREDICATE CALCULUS 3.16: QUANTIFIER 3.16.1: Universal Quantifier 3.16.2: Existential Quantifier 3.17: INTRODUCTION TO PROOFS 3.17.1: Brief Status of Terminology 3.17.2: Methods of Proof 3.17.3: Direct Proof 3.17.4: Consistency 3.17.5: Method of Proof by Contraposition 3.17.6: Proof by Contradiction (reduction ad absurdum) 3.17.7: Proof by Mathematical Induction 3.17.8: Proof by Cases Summary Exercise 3 CHAPTER 4 ALGEBRAIC STRUCTURE 4.1: INTRODUCTION 4.2: BINARY OPERATIONS 4.2.1: Properties of Binary Operations 4.3: GROUPS 4.3.1: Abelian Group 4.3.2: Properties of Groups 4.3.3: Products and Quotients of Groups 4.4: SEMIGROUPS 4.4.1: Isomorphism and Homomorphism 4.4.2: Products and Quotients of Semigroups 4.5: SUBGROUP 4.6: CYCLIC GROUP 4.7: PERMUTATION GROUPS 4.7.1: Equality of Permutations 4.7.2: Permutation Identity 4.7.3: Composition of Permutations (or, Product of Permutations) 4.7.4: Inverse Permutation 4.7.5: Cyclic Permutations 4.7.6: Transposition 4.7.7: Even and Odd Permutations 4.8: SYMMETRIC GROUP 4.9: COSETS 4.9.1: Properties of Cosets 4.10: NORMAL SUBGROUP 4.11: LAGRANGE'S THEOREM 4.12: GROUP CODES 4.12.1: Coding of Binary Information 4.12.2: Parity and Generator Matrices 4.12.3: Decoding and Error Correction 4.13: ALGEBRAIC SYSTEMS WITH TWO BINARY OPERATIONS 4.13.1: Rings 4.13.2: Elementary Properties of a Ring 4.13.3: Special kinds of Rings 4.13.4: Integral Domain 4.13.5: Field 4.14: SUBRING 4.14.1: Ideal 4.14.2: Quotient Ring 4.14.3: Morphisms of Rings 4.14.4: Properties of Homomorphism of Ring Summary Exercise 4 Chapter 5 MATRIX ALGEBRA 5.1: INTRODUCTION 5.2: DEFINITION OF A MATRIX 5.3: TYPES OF MATRICES 5.3.1: Rectangular and Square Matrices 5.3.2: Row matrix or a row vector 5.3.3: Column matrix or a column vector 5.3.4: Zero or Null matrix 5.3.5: Diagonal elements of a matrix 5.3.6: Diagonal matrix 5.3.7: Scalar matrix 5.3.8: Unit Matrix or Identity Matrix 5.3.9: Comparable Matrices 5.3.10: Equal Matrices 5.3.11: Upper Triangular Matrix 5.3.12: Lower Triangular Matrix 5.4: OPERATIONS ON MATRICES 5.4.1: Addition of Matrices 5.4.2: Subtraction of Matrices 5.4.3: Scalar Multiple of a Matrix 5.4.4: Multiplication of Matrices 5.4.5: Properties of Matrix Multiplication 5.4.6: Positive Integral Powers of Matrices 5.4.7: Sub Matrix 5.4.8: Partition of Matrices 5.5: RELATED MATRICES 5.5.1: Transpose of a Matrix 5.5.2: Symmetric and Skew-Symmetric Matrix 5.5.3: Complex Matrices 5.5.4: Conjugate of a Matrix 5.5.5: Conjugate Transpose of a Matrix 5.5.6: Hermitian and Skew-Hermitian Matrices 5.6: DETERMINANT OF A MATRIX 5.6.1: Minor and Co-factor 5.6.2: Expansion of the determinant ( ) 5.6.3: Difference between a Matrix and a Determinant 5.7: TYPICAL SQUARE MATRICES 5.7.1: Orthogonal Matrix 5.7.2: Unitary Matrix 5.7.3: Involutory Matrix 5.7.4: Idempotent Matrix 5.7.5: Nilpotent Matrix 5.8: ADJOINT AND INVERSE OF A MATRIX 5.8.1: Singular and Non-singular Matrices 5.8.2: Adjoint of a Square Matrix 5.8.3: Properties of Adjoint of a Matrix 5.9: INVERSE OF A MATRIX 5.9.1: Properties of Inverse of a Matrix 5.10: RANK OF A MATRIX 5.10.1: Elementary transformations (operations) of a matrix 5.11: BOOLEAN MATRIX OR A ZERO-ONE MATRIX 5.11.1: Operations on Zero-one Matrices 5.11.2: Boolean product of matrices 5.11.3: Echelon Matrix (Row Reduced Echelon Form) 5.11.4: Normal form of a Matrix 5.11.5: Procedure of reduction of a matrix A to its normal form 5.12: SOLUTION OF LINEAR AL GEBRAIC EQUATIONS 5.12.1: Linear Homogenous Equations (Ax = 0) 5.12.2: Linear Non-homogenous Equations (Ax = b) 5.12.3: Consistent and Inconsistent Equations 5.13: EIGEN VALUES AND EIGEN VECTORS 5.13.1: Determination of Eigen values and Eigen vectors 5.13.2: Linear Transformations 5.13.3: Properties of Eigen values and Eigen vectors 5.14: CAYLEY - HAMILTON THOREM 5.14.1: Inverse of the Matrix Summary Exercise 5 Chapter 6 ORDER RELATION AND LATTICE 6.1: INTRODUCTION 6.2: PARTIALLY ORDERED SET 6.2.1: Comparability of Elements 6.2.2: Linearly ordered set 6.3: HASSE DIAGRAM 6.3.1: Topological Sorting 6.3.2: Chain 6.3.3: Antichain 6.4: ISOMORPHISM 6.4.1: Isomorphic Ordered Sets 6.5: LEXICOGRAPHIC ORDERING 6.6: EXTREMAL ELEMENTS OF POSETS 6.6.1: Maximal Element 6.6.2: Minimal Element 6.6.3: Greatest and Least Elements 6.6.4: Upper and Lower Bounds 6.6.5: Least Upper Bound (Supremum) 6.6.6: Greatest Lower Bound (Infimum) 6.7: WELL-ORDERED SET 6.8: CONSISTENT ENUMERATIONS 6.9: LATTICES 6.9.1: Principle of Duality 6.9.2: Isotonocity Property 6.10: SUB LATTICES 6.11: DIRECT PRODUCT OF LATTICES 6.12: SOME SPECIAL CLASS OF LATTICES 6.12.1: Complete Lattice 6.12.2: Bounded Lattice 6.12.3: Properties of Bounded Lattice 6.12.4: Distributive Lattice 6.12.5: Modular Lattice 6.12.6: Complemented Lattices 6.12.7: Isomorphic Lattices 6.12.8: Join-irreducible 6.12.9: Meet-irreducible 6.13: LATTICE HOMOMORPHISM Summary Exercise 6 CHAPTER-7 BOOLEAN ALGEBRA 7.1: INTRODUCTION 7.2: LAWS ON BOOLEAN ALGEBRA 7.3: TRUTH TABLES ON BOOLEAN OPERATIONS 7.4: UNIQUE FEATURES OF BOOLEAN ALGEBRA 7.5: MINTERM AND MAXTERM 7.5.1: Boolean Expression in Sum of Products(SOP) and Product of 7.5.2: Sums(POS) Form or Normal Form 7.6: BOOLEAN FUNCTION 7.7: SWITICHING NETWORK FROM BOOLEAN EXPRESSION USING LOGIC GATES 7.8: KARNAUGH MAP 7.8.1: Rules used by K-map for simplification 7.8.2: Labeling of K-map Squares Summary Exercise 7 CHAPTER-8 COMPLEXITY 8.1: INTRODUCTION 8.2: ALGORITHM 8.2.1: Basic Criteria of Algorithm 8.3: DATA STRUCTURE 8.3.1: Operations on Data Structure 8.3.2: Categorizations of Data structure 8.3.2.1: Array as Non-primitive Data Structure 8.3.2.2: Structure as Non-primitive Data Structure 8.3.3: Abstract Data Type 8.3.4: Linear and Non-linear Data Structure 8.4: COMPLEXITY 8.4.1: Idea on Complexity Function of any Algorithm 8.4.2: Asymptote and Its Behavior 8.4.3: Why Asymptotic Notations to Express Inexact Running Time ? 8.4.4: Counting Strategy for Operations in Algorithm 8.4.5: Discussion on Order of Complexity 8.4.6: Mathematical Definitions of Some Useful Asymptotic Notations 8.4.6.1: Big oh 8.4.6.2: Big Omega 8.4.6.3: Theta 8.4.6.4: Little Oh and Little Omega 8.4.7: Standard Cases 8.4.8: Some Properties of Time Complexity Functions 8.4.9: Complexity of Recursive Procedures 8.4.10: Solving Recurrence Relation T(n) = aT(n/b) +f(n) , a ? 1 , b > 0 8.4.11: Comparison of Complexity 8.5: SEARCHING AND SORTING 8.5.1: Searching 8.5.1.1: Linear Search 8.5.1.2: Binary Search 8.5.2: Sorting 8.5.2.1: Merge Sorting 8.5.2.2: Bubble Sorting Summary Exercise 8 CHAPTER -9 GRAPH 9.1: INTRODUCTION 9.2: GRAPH AND BASIC TERMINOLOGIES 9.3: TYPES OF GRAPH 9.4: SUB-GRAPH AND ISOMORPHIC GRAPH 9.5: OPERATIONS ON GRAPH 9.6: REPRESENTATION OF GRAPH 9.6.1: Matrix Representation 9.6.2: Adjacency List Representation 9.6.3: Advantages and Disadvantages of Matrix and Linked list representations 9.6.4: Incidence Matrix Representation of Graph 9.7: GRAPH ALGORITHMS 9.7.1: BFS 9.7.2: DFS 9.7.3: Single Source Shortest Path Problem, Dijkstra's Algorithm 9.8: EULER GRAPH FLEURY'S ALGORITHM 9.8.1: Some Useful Results on Euler Graph 9.9: HAMILTONIAN GRAPH 9.9.1: Useful Hints on Hamiltonian circuit 9.10: PLANAR GRAPH 9.11: COLOURING OF GRAPH 9.12: COMPONENT 9.13: CUT VERTEX 9.14: FLOW NETWORK 9.14.1: Ford-Fulkerson Algorithm Summary Exercise 9 CHAPTER -10 TREE 10.1: INTRODUCTION 10.2: TREE 10.2.1: Common Terminologies on Tree 10.2.2: Labeled Tree 10.2.3: Some Diagrams of Directed and Undirected Trees 10.2.4: Summary of the Basic Properties of Tree 10.2.5: m-ary Tree, Complete Binary Tree, Full Binary Tree 10.2.6: Why skewed tree are considered as binary tree? 10.3: SOME IMPORTANT RESULTS ON TREE 10.4: SEQUENTIAL REPRESENTATION OF BINARY TREE 10.5: OPERATIONS ON TREE 10.5.1: Tree Traversal 10.5.2: More Discussions on Tree Traversals 10.5.3: Construction of unique Binary Tree when Pre-order and In-order 10.5.4: Traversal Sequences are given 10.5.5: Algorithm to Construct Unique Binary Tree using Pre-order and In-order Sequences 10.6: BINARY SEARCH TREE (BST) 10.6.1: Linked List Representation of Binary Tree 10.6.2: Construction of Binary Search Tree 10.6.3. Useful Results from Binary Search Tree: 10.7: RECURSIVE PROCEDURE FOR BINARY TREE TRAVERSAL 10.7.1: Analysis of Time Complexities for Some Operations on Binary Tree 10.8: PREDECESSOR AND SUCCESSOR NODE 10.9: EXPRESSION TREE 10.10: AVL TREE 10.11: SPANNING TREE 10.11.1: Minimum Spanning Tree(MST), Prim's and Kruskal's algorithm 10.12: GENERAL TREE 10.12.1: Conversion of General Tree to Binary Tree 10.12.2: Pre- order Traversal for General Tree 10.13: SOME IMPORTANT APPLICATIONS OF TREE Summary Exercise 10 CHAPTER-11 FORMAL LANGUAGE AND AUTOMATA 11.1: INTRODUCTION 11. 2: MATHEMATICAL PRELIMINARIES 11. 3: AUTOMATA 11.3.1: Basic Categories of Automata 11.3.1.1: State Transition Graph 11.3.2: Finite Automaton and Its Types 11.3.2.1: Deterministic Finite Automaton(DFA) 11.3.2.2: Non-deterministic Finite Automaton(NDFA) 11.3.3: Importance of NDFA 11.3.4: Graphical Notations Used in this Chapter in Drawing Finite Automata 11.3.5: Discussion on Designing of Some Basic FA's 11.3.6: Some Basic Tips to Design FA 11.3.7: Conversion Strategy from NDFA to DFA 11.3.8: Finite Automaton with Output 11.3.8.1: Transformation of Moore m/c to Mealy m/c 11.3.8.2: Transformation of Mealy m/c to Moore m/c 11.4: REGULAR EXPRESSION 11.4.1: Minimization of FA 11.4.2: Brief Discussion to Derive R.Es 11.4.3: Solved Problems on R.E. 11. 4. 4: The Identities on Regular Expression 11. 4. 5: Rules for Constructing NDFA from Regular Expression 11. 4. 6: Tips to Get Quick Answer of Some Special Problems on FA and R.E. 11.4.7: Pumping Lemma for Regular Language 11. 4. 8: Applications of Finite Automata and Regular Expression 11.5: GRAMMAR 11. 5. 1: Formal Defination of Grammar 11. 5. 2: The Chomsky Hierarchy 11. 5. 3: Derivation(Parsing) 11. 5. 4: Parsing Techniques 11. 5. 5: Ambiguous Grammar 11. 5. 5.1: Demerits of Ambiguous Grammar 11. 5. 5.2: Making Disambiguous Grammar 11. 6: PUSHDOWN AUTOMATON (PDA) 11.6.1: Types of PDA 11. 7: TURING MACHINE (TM) 11.7.1: Improvement in TM 11.7.2: Variations of TMs 11.7.3: Halting Problem 11.7.4: Turing Acceptable Language 11.7.5: Properties of Recursive and Recursively Enumerable Languages 11.7.6: Church Thesis 11.8: POST CORRESPONDENCE PROBLEM(PCP) 11.9: CLASSES OF PROBLEMS 11.10: WHAT IS CELLULAR AUTOMATA ? 11.11: FUZZY SETS AND LOGIC 11.12: RUSSELL'S PARADOX 11.12.1: History of the paradox Summary Exercise 11 Appendix 1 References