Discrete Mathematical Structures by Pearson

Book description

About The Author –
Uma Shanker Gupta joined the department of mathematics, the University of Roorkee (presently IIT-Roorkee), in 1967, after teaching for five years at Ewing Christian Degree College, Allahabad. He was awarded PhD (Mathematics) by the University of Roorkee in 1971. He joined the Department of Applied Science and Humanities, ABES Engineering College, Ghaziabad, as professor in 2006 and subsequently held positions of Professor and Head, Applied Science and Humanities, Professor and Head MCA Dept and Director, MCA Institute.
He was a visiting faculty of Mathematics in the School of Vocational Studies and Applied Science, Gautam Buddha University, UP, in the autumn semester of 2010–2011. He has been a reviewer of many International journals like Journal of Applied Mechanics, Journal of Sound and Vibration to name a few. He became EMERITUS FELLOW in 2004 and held this position till 2006.

Book Contents –
1. Set Theory
2. Relations and Digraphs
3. Functions
4. Mathematical Logic and Methods of Proofs
5. Combinatorics
6. Recurrence Relations and Generating Functions
7. Algebraic Structures
8. Ordered Sets and Lattices
9. Boolean Algebra
10. Topics in Graph Theory
11. Trees
12. Vector Spaces
13. ANSWER TO EXERCISEs
14. References
15. Index

Table of contents

  1. Front Cover
  2. Contents (1/2)
  3. Contents (2/2)
  4. Preface
  5. Acknowledgements
  6. About The Author (1/2)
  7. About The Author (2/2)
  8. 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
        1. EXERCISES
  9. 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 Boolean...Equation
      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
      1. EXERCISES
  10. 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 W (Lower Bound) and Big-Theta Q (Tight Bound) Notations
      6. 3.12.6 Little Oh (o) and Little Omega (w)
    13. 3.13 CONNECTIVITY RELATION (1/2)
    14. 3.13 CONNECTIVITY RELATION (2/2)
      1. EXERCISE – A (1/2)
      2. EXERCISE – A (2/2)
        1. EXERCISE – B
  11. 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
        1. EXERCISE – A
        2. EXERCISE – B
  12. 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) (1/2)
    11. 5.10 MULTIPLICATION THEOREM (Independent Events) (2/2)
    12. 5.11 BAYE’S THEOREM
    13. 5.12 CONCEPT OF A RANDOM VARIABLE
      1. 5.12.1 Probability Distribution
    14. 5.13 BINOMIAL DISTRIBUTION
      1. 5.13.1 Repeated Independent Trials with Two Outcomes
      2. 5.13.2 Mean and Variance
    15. 5.14 POISSON DISTRIBUTION
      1. 5.14.1 Mean and Variance
      2. 5.14.2 Another Approach to Poisson Distribution (1/2)
      3. 5.14.2 Another Approach to Poisson Distribution (2/2)
        1. EXERCISE – A
        2. EXERCISE – B
        3. EXERCISE – C
        4. EXERCISE – D
  13. 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 (1/2)
      3. 6.3.2 Non-homogeneous Recurrence Relation (2/2)
    4. 6.4 E AND d 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 (1/2)
      4. 6.4.3 Factorial Notation (2/2)
    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
        1. EXERCISES
  14. 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 (1/2)
      4. 7.3.3 Group (2/2)
      5. 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
      1. EXERCISES
  15. 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
      1. Exercises
  16. 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 (1/2)
      5. 9.2.4 Minterm and Maxterm (2/2)
    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.1 INTRODUCTION
    6. 9.2 DEFINITION: BOOLEAN ALGEBRA
    7. 9.3 DISJUNCTIVE AND CONJUNCTIVE NORMAL FORMS (CANONICAL FORMS)
    8. 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 (1/2)
      4. 9.5.3 Four-Variable K-Map (2/2)
        1. EXERCISES
  17. 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
    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 (1/3)
      2. 10.19.1 Assignment Problem (2/3)
      3. 10.19.1 Assignment Problem (3/3)
        1. EXERCISE – A
        2. EXERCISE – B
  18. 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 (1/2)
      3. 11.7.2 Prim’s Algorithm (2/2)
        1. EXERCISES
  19. 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/2)
    7. 12.6 DIMENSION and basis (2/2)
      1. 12.6.1 Coordinates
    8. 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
    9. 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 (1/2)
      7. 12.8.6 Gram–Schmidt Orthogonalization Process (2/2)
        1. EXERCISE – A
        2. EXERCISE – B
  20. ANSWER TO EXERCISEs (1/29)
  21. ANSWER TO EXERCISEs (2/29)
  22. ANSWER TO EXERCISEs (3/29)
  23. ANSWER TO EXERCISEs (4/29)
  24. ANSWER TO EXERCISEs (5/29)
  25. ANSWER TO EXERCISEs (6/29)
  26. ANSWER TO EXERCISEs (7/29)
  27. ANSWER TO EXERCISEs (8/29)
  28. ANSWER TO EXERCISEs (9/29)
  29. ANSWER TO EXERCISEs (10/29)
  30. ANSWER TO EXERCISEs (11/29)
  31. ANSWER TO EXERCISEs (12/29)
  32. ANSWER TO EXERCISEs (13/29)
  33. ANSWER TO EXERCISEs (14/29)
  34. ANSWER TO EXERCISEs (15/29)
  35. ANSWER TO EXERCISEs (16/29)
  36. ANSWER TO EXERCISEs (17/29)
  37. ANSWER TO EXERCISEs (18/29)
  38. ANSWER TO EXERCISEs (19/29)
  39. ANSWER TO EXERCISEs (20/29)
  40. ANSWER TO EXERCISEs (21/29)
  41. ANSWER TO EXERCISEs (22/29)
  42. ANSWER TO EXERCISEs (23/29)
  43. ANSWER TO EXERCISEs (24/29)
  44. ANSWER TO EXERCISEs (25/29)
  45. ANSWER TO EXERCISEs (26/29)
  46. ANSWER TO EXERCISEs (27/29)
  47. ANSWER TO EXERCISEs (28/29)
  48. ANSWER TO EXERCISEs (29/29)
  49. References
  50. Index (1/2)
  51. Index (2/2)

Product information

  • Title: Discrete Mathematical Structures by Pearson
  • Author(s): Uma Shanker Gupta
  • Release date: May 2024
  • Publisher(s): Pearson India
  • ISBN: 9781322128603