Discrete Mathematical Structures

Discrete Mathematical Structures

by U.S. Gupta
Released January 2014
Publisher(s): Pearson Education India
ISBN: 9789332537415

Read it now on the O’Reilly learning platform with a 10-day free trial.

O’Reilly members get unlimited access to books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.

Start your free trial

Book description

Discrete Mathematical Structures provides comprehensive, reasonably rigorous and simple explanation of the concepts with the help of numerous applications from computer science and engineering. Every chapter is equipped with a good number of solved examples that elucidates the definitions and theorems discussed. Chapter-end exercises are graded, with the easier ones in the beginning and then the complex ones, to help students for easy solving.

Table of contents

  1. Cover
  2. Title Page
  3. Contents
  4. Dedication
  5. Preface
  6. Acknowledgements
  7. About the Author
  8. 1. Set Theory
    1. 1.1 Introduction
    2. 1.2 Sets
      1. 1.2.1 Types of Sets
      2. 1.2.2 Subset
      3. 1.2.3 Proper Subset
      4. 1.2.4 Power Set
      5. 1.2.5 Venn Diagram
      6. 1.2.6 Set Operations
      7. 1.2.7 Disjoint Sets
      8. 1.2.8 Complement of a Set
      9. 1.2.9 Laws of Sets
      10. 1.2.10 Symmetric Difference of Two Sets
      11. 1.2.11 The Inclusion and Exclusion Principle
      12. 1.2.12 Some Simple Results on Cardinality of Sets
    3. 1.3 Cartesian Product of Sets
    4. 1.4 Multiset
      1. 1.4.1 Operations on Multisets
    5. Exercises
  9. 2. Relations and Digraphs
    1. 2.1 Introduction
    2. 2.2 Binary Relation
      1. 2.2.1 Domain and Range of Relation
      2. 2.2.2 Types of Relations
      3. 2.2.3 Properties of Relation on a Set
      4. 2.2.4 Equivalence Relation
      5. 2.2.5 Complementary Relation R
      6. 2.2.6 Closure of Relation
      7. 2.2.7 Reflexive Closure
      8. 2.2.8 Symmetric Closure
      9. 2.2.9 Composition of Relations
      10. 2.2.10 Transitive Closure
    3. 2.3 Equivalence Class
      1. 2.3.1 Properties of Equivalence Classes
    4. 2.4 Partition of a Set
    5. 2.5 Congruence Modulo Relation
    6. 2.6 Pictorial Representation of Relation
    7. 2.7 Digraphs
      1. 2.7.1 In-degree and Out-degree of Vertices
    8. 2.8 Power of Relation
    9. 2.9 Paths in Relations and Digraphs
    10. 2.10 Matrix Representation of Composite Relations
    11. 2.11 Connectivity Relation
    12. Exercises
  10. 3. Functions
    1. 3.1 Introduction
    2. 3.2 Definition
    3. 3.3 Domain and Range of a Function
    4. 3.4 Difference Between Relation and Function
    5. 3.5 Different Types of Functions (or Mappings) Constant Function
      1. 3.5.1 Identity Function
      2. 3.5.2 One–One and Many–One Function
      3. 3.5.3 INTO and ONTO (Surjective) Functions (or Mappings)
      4. 3.5.4 Invertible Functions
      5. 3.5.5 Some Illustrative Examples
      6. 3.5.6 Equality of Functions
    6. 3.6 Composition of Functions
    7. 3.7 Functions for Computer Science
      1. 3.7.1 Absolute Value Function
      2. 3.7.2 Floor Function
      3. 3.7.3 Ceiling Function
      4. 3.7.4 Mod and Div Functions
      5. 3.7.5 Integer Value Function
    8. 3.8 Some Special Functions Used in Discrete Mathematics
      1. 3.8.1 Polynomial Function
      2. 3.8.2 Exponential Functions
      3. 3.8.3 Logarithmic Function
      4. 3.8.4 Recursively Defined Functions
      5. 3.8.5 Sequence (or Discrete) Functions
      6. 3.8.6 Strings
      7. 3.8.7 Characteristic Function
      8. 3.8.8 Computer Representation of Sets
    9. 3.9 Some Important Theorems and Problems
    10. 3.10 Ackermann’s Function
    11. 3.11 Fuzzy Sets
      1. 3.11.1 Some Definitions
      2. 3.11.2 Operations on Fuzzy Sets
    12. 3.12 Time Complexity of Algorithm
      1. 3.12.1 Rate of Growth of Functions
      2. 3.12.2 Determination of Growth Function
      3. 3.12.3 Complexity of Well-known Algorithms
      4. 3.12.4 Some Properties of Time Complexity Functions
      5. 3.12.5 The Big-Omega Ω (Lower Bound) and Big-Theta Θ (Tight Bound) Notations
      6. 3.12.6 Little Oh (o) and Little Omega (ω)
    13. 3.13 Connectivity Relation
    14. Exercise – A
    15. Exercise – B
  11. 4. Mathematical Logic and Methods of Proofs
    1. 4.1 Introduction
    2. 4.2 Statement (Proposition)
    3. 4.3 Propositional Variables, Simple and Compound Propositions (or Statements)
      1. 4.3.1 Simple Propositions
      2. 4.3.2 Compound Proposition
    4. 4.4 Basic Logical Operations
      1. 4.4.1 Negation
      2. 4.4.2 Conjunction
      3. 4.4.3 Disjunction
      4. 4.4.4 Negation of Compound Statements
      5. 4.4.5 Conditional Statements
      6. 4.4.6 Converse, Contrapositive and Inverse
      7. 4.4.7 NAND, NOR, and XOR Operators
      8. 4.4.8 Biconditional Statements
      9. 4.4.9 Negation of Biconditional Statement
    5. 4.5 Tautology and Contradiction
      1. 4.5.1 Contingency
    6. 4.6 Logically Equivalent or Equivalent Propositions
    7. 4.7 Logical Arguments
      1. 4.7.1 Validity of an Argument
      2. 4.7.2 Law of Syllogism
      3. 4.7.3 Methods to Test the Validity of an Argument
    8. 4.8 Predicates
      1. 4.8.1 Propositional Functions and Quantifiers
      2. 4.8.2 Universal Quantifier
      3. 4.8.3 Existential Quantifier
    9. 4.9 Methods of Proof
      1. 4.9.1 Direct Proof
      2. 4.9.2 Indirect Proof
      3. 4.9.3 Proof by Counter Example
      4. 4.9.4 Principle of Mathematical Induction
    10. Exercise – A
    11. Exercise – B
  12. 5. Combinatorics
    1. 5.1 Introduction
    2. 5.2 Basic Principle of Counting
      1. 5.2.1 Addition Principle
      2. 5.2.2 Multiplication Principle
    3. 5.3 Permutations
      1. 5.3.1 Permutation with Repetitions
    4. 5.4 Ordered and Unordered Partitions
      1. 5.4.1 Ordered Partitions
      2. 5.4.2 Unordered Partitions
    5. 5.5 Circular Permutations
    6. 5.6 Combinations
      1. 5.6.1 Combinations of Objects not all Different
    7. 5.7 Derangements
    8. 5.8 The Pigeonhole Principle
      1. 5.8.1 Generalized Pigeonhole Principle
      2. 5.8.2 Extended Pigeonhole Principle
    9. 5.9 Elements of Probability
      1. 5.9.1 Definition
      2. 5.9.2 Notations
      3. 5.9.3 Emperical or Statistical Definition of Probability
      4. 5.9.4 Axiomatic Definition of Probability
      5. 5.9.5 Multiplication Theorem for Probability
      6. 5.9.6 Independent Events
    10. 5.10 Multiplication Theorem (Independent Events)
    11. 5.11 Baye’s Theorem
    12. 5.12 Concept of a Random Variable
      1. 5.12.1 Probability Distribution
    13. 5.13 Binomial Distribution
      1. 5.13.1 Repeated Independent Trials with Two Outcomes
      2. 5.13.2 Mean and Variance
    14. 5.14 Poisson Distribution
      1. 5.14.1 Mean and Variance
      2. 5.14.2 Another Approach to Poisson Distribution
    15. Exercise – A
    16. Exercise – B
    17. Exercise – C
    18. Exercise – D
  13. 6. Recurrence Relations and Generating Functions
    1. 6.1 Introduction
    2. 6.2 Sequences
      1. 6.2.1 Recurrence Relation
    3. 6.3 Linear Recurrence Relation with Constant Coefficients
      1. 6.3.1 Characteristic Root Method
      2. 6.3.2 Non-homogeneous Recurrence Relation
    4. 6.4 E and Δ Operators Method
      1. 6.4.1 Interrelation Between Operators E and Δ
      2. 6.4.2 Differences of a Polynomial Function
      3. 6.4.3 Factorial Notation
    5. 6.5 Method of Generating Functions
      1. 6.5.1 Properties of Generating Functions
      2. 6.5.2 Closed Form for Generating Function
      3. 6.5.3 Combinatorial Method
      4. 6.5.4 Linear Diophantine Equations
    6. Exercises
  14. 7. Algebraic Structures
    1. 7.1 Introduction
    2. 7.2 Binary Operation
    3. 7.3 Algebraic Structures
      1. 7.3.1 Semi-Group
      2. 7.3.2 Monoid
      3. 7.3.3 Group
      4. 7.3.4 Modulo (m) Operations
    4. 7.4 Congruences
      1. 7.4.1 Residue Classes
      2. 7.4.2 Addition and Multiplication of Residue Classes
    5. 7.5 Permutations
      1. 7.5.1 Cyclic Permutation
      2. 7.5.2 Powers of Cycle
      3. 7.5.3 Transposition
      4. 7.5.4 Even and Odd Permutations
    6. 7.6 Integral Powers of an Element
    7. 7.7 Cyclic Group
    8. 7.8 Subgroups
    9. 7.9 Coset Decomposition
      1. 7.9.1 Congruence Relation in Groups
      2. 7.9.2 Normal Subgroups
    10. 7.10 Isomorphism and Homomorphism of Groups
    11. 7.11 Algebraic Systems with Two Binary Operations
      1. 7.11.1 Rings
      2. 7.11.2 Elementary Properties of a Ring
      3. 7.11.3 Polynomial Ring
      4. 7.11.4 Morphism of Rings
      5. 7.11.5 Boolean Ring
    12. 7.12 Ring, Subring and Ideals
      1. 7.12.1 Ideal
      2. 7.12.2 Quotient Ring or Ring of Residue Classes
    13. 7.13 Integral Domain
    14. 7.14 Field
    15. Exercises
  15. 8. Ordered Sets and Lattices
    1. 8.1 Introduction
    2. 8.2 Partially Ordered Set
      1. 8.2.1 Linearly Ordered or Totally Ordered Set
    3. 8.3 Product of Two Posets
    4. 8.4 Hasse Diagram
    5. 8.5 Lexicographic Ordering
    6. 8.6 Upper and Lower Bounds
      1. 8.6.1 Extremal Elements of Partially Ordered Sets
      2. 8.6.2 Least Upper Bound or Supremum
      3. 8.6.3 Greatest Lower Bound or Infimum
    7. 8.7 Dual of a Poset
    8. 8.8 Isomorphism of Posets
    9. 8.9 Well-ordered Set
    10. 8.10 Properties of Well-ordered Sets
    11. 8.11 Lattices
    12. 8.12 Lattice in Terms of Algebraic Structures
    13. 8.13 Sublattices
    14. 8.14 Bounded Lattices
    15. 8.15 Duality
    16. 8.16 Complete Lattice
    17. 8.17 Isomorphic Lattices
    18. 8.18 Complimented Lattice
    19. 8.19 Chain and Antichain
    20. 8.20 Distributive Lattices
    21. 8.21 Modular Lattice
    22. 8.22 Boolean Lattice
    23. Exercises
  16. 9. Boolean Algebra
    1. 9.1 Introduction
    2. 9.2 Definition: Boolean Algebra
      1. 9.2.1 Boolean Variables
      2. 9.2.2 Boolean Expression
      3. 9.2.3 Boolean Function
      4. 9.2.4 Minterm and Maxterm
    3. 9.3 Disjunctive and Conjunctive Normal Forms (Canonical Forms)
      1. 9.3.1 Complete Canonical Form
    4. 9.4 Switching Network from Boolean Expression
    5. 9.5 Karnaugh Map
      1. 9.5.1 Looping
      2. 9.5.2 Three-variable K-Map
      3. 9.5.3 Four-Variable K-Map
    6. Exercises
  17. 10. Topics in Graph Theory
    1. 10.1 Introduction
    2. 10.2 Graph Definition
      1. 10.2.1 Finite and Infinite Graphs
      2. 10.2.2 Directed and Undirected Graph
      3. 10.2.3 Weighted Graph
      4. 10.2.4 Incidence and Degree
      5. 10.2.5 Complete Graph
      6. 10.2.6 Regular Graph
      7. 10.2.7 Degree Sequence of Graph
      8. 10.2.8 Isolated and Pendant Vertex
    3. 10.3 Planar and Non-planar Graphs
      1. 10.3.1 Kuratowski’s Two Graphs
    4. 10.4 Region
    5. 10.5 Operations on Graphs
      1. 10.5.1 Sum of Two Graphs
      2. 10.5.2 Cut-Sets and Cut-Vertices
    6. 10.6 Bipartite Graph
      1. 10.6.1 Complete Bipartite Graph
    7. 10.7 Isomorphism
    8. 10.8 Representation of Graphs in Computer Memory
      1. 10.8.1 Adjacency Matrix of Undirected Graph
      2. 10.8.2 Incidence Matrix
      3. 10.8.3 Matrix Representation of Directed Graph: The Adjacency Matrix
    9. 10.9 Representation of Multi Graph
    10. 10.10 Walk in a Graph
      1. 10.10.1 Circuit
    11. 10.11 Sub-Graph
      1. 10.11.1 Spanning Sub-Graph
    12. 10.12 Connected and Disconnected Graphs
      1. 10.12.1 Eulerian and Hamiltonian Graphs
      2. 10.12.2 Königsberg Bridge Problem
      3. 10.12.3 Fleury’s Algorithm
      4. 10.12.4 Unicursal Graph
      5. 10.12.5 Hamiltonian Paths and Circuits
    13. 10.13 Graph Colouring
      1. 10.13.1 Welch and Powell Algorithm
    14. 10.14 Chromatic Polynomial
    15. 10.15 Shortest Path Problems
      1. 10.15.1 Shortest Path in a Graph without Weights
      2. 10.15.2 Algorithm for BFS
      3. 10.15.3 BTS Algorithm
    16. 10.16 Shortest Path in a Weighted Graph
      1. 10.16.1 Single-source Shortest Path Problem
      2. 10.16.2 Dijkstra’s Algorithm
    17. 10.17 Travelling Salesman Problem
    18. 10.18 Network Flows
      1. 10.18.1 Cut-Set and Capacity
      2. 10.18.2 Ford–Fulkerson Algorithm
      3. 10.18.3 Ford–Fulkerson Algorithm for Maximum Flow
    19. 10.19 Matchings
      1. 10.19.1 Assignment Problem
    20. Exercise – A
    21. Exercise – B
  18. 11. Trees
    1. 11.1 Introduction
      1. 11.1.1 Definition
      2. 11.1.2 Properties of Tree
      3. 11.1.3 Directed and Undirected Trees
    2. 11.2 Rooted Structure
      1. 11.2.1 Binary and Ternary Trees
      2. 11.2.2 Complete Binary Tree
      3. 11.2.3 Ordered Rooted Tree
    3. 11.3 Binary Tree of an Algebraic Expression
      1. 11.3.1 Infix, Prefix, and Postfix Notations
    4. 11.4 Tree Searching or Tree Traversal
      1. 11.4.1 Binary Tree Travel
    5. 11.5 Binary Search Tree
    6. 11.6 Spanning Trees
      1. 11.6.1 Definition
      2. 11.6.2 Branch and Chord of a Spanning Tree
      3. 11.6.3 Methods for Finding Spanning Trees
      4. 11.6.4 Depth-first Search Algorithm
    7. 11.7 Minimal Spanning Trees
      1. 11.7.1 Kruskal’s Algorithm
      2. 11.7.2 Prim’s Algorithm
    8. Exercises
  19. 12. Vector Spaces
    1. 12.1 Introduction
    2. 12.2 Definition
      1. 12.2.1 Some Simple Properties of a Vector Space
    3. 12.3 Vector Subspace
    4. 12.4 Calculus of Subspaces
      1. 12.4.1 Linear Sum of Two Subspaces
    5. 12.5 Linear Dependence and Indepence of Vectors
      1. 12.5.1 Definition of Linear Dependence
      2. 12.5.2 Method for Testing Linear Dependence of Vectors
      3. 12.5.3 Echelon form of a Matrix
      4. 12.5.4 Definition of Wronskian
    6. 12.6 Dimension and Basis
      1. 12.6.1 Coordinates
    7. 12.7 Linear Transformation
      1. 12.7.1 Properties of Linear Transformation
      2. 12.7.2 Matrix Representation of a Linear Transformation
      3. 12.7.3 Change of Basis-transition Matrix
      4. 12.7.4 Range and Kernel of Linear Transformation
      5. 12.7.5 Rank-nullity Theorem
    8. 12.8 Normed and Inner Product Spaces
      1. 12.8.1 Norm
      2. 12.8.2 Inner Product
      3. 12.8.3 Inner Product Norm
      4. 12.8.4 Cauchy–Schwarz Inequality
      5. 12.8.5 Orthogonal Vectors
      6. 12.8.6 Gram–Schmidt Orthogonalization Process
    9. Exercise – A
    10. Exercise – B
  20. Answers to Exercises
  21. References
  22. Copyright

Product information

  • Title: Discrete Mathematical Structures
  • Author(s): U.S. Gupta
  • Release date: January 2014
  • Publisher(s): Pearson Education India
  • ISBN: 9789332537415