You are previewing Discrete Mathematics.
O'Reilly logo
Discrete Mathematics

Book Description

Discrete Mathematics will be of use to any undergraduate as well as post graduate courses in Computer Science and Mathematics. The syllabi of all these courses have been studied in depth and utmost care has been taken to ensure that all the essential topics in discrete structures are adequately emphasized. The book will enable the students to develop the requisite computational skills needed in software engineering.

Table of Contents

  1. Cover
  2. Title page
  3. Contents
  4. About the Author
  5. Dedication
  6. List of Symbols
  7. Preface
  8. Chapter 1 Sets, Relations and Functions
    1. 1.1 Sets
    2. 1.2 Algebra of Sets
    3. 1.3 Representation of Relations on Finite Set
    4. 1.4 Mappings (Functions)
    5. 1.5 Composition of Mappings
    6. 1.6 Countability of Sets
    7. 1.7 Partially Ordered Sets
    8. 1.8 Hasse Diagram
    9. 1.9 Isomorphic (Similar) Ordered Sets
    10. 1.10 Hashing Function
    11. 1.11 Principle of Mathematical Induction
    12. Exercises
  9. Chapter 2 Counting
    1. 2.1 Addition Rule
    2. 2.2 Multiplication Rule
    3. 2.3 Permutations
    4. 2.4 Combinations
    5. 2.5 Combinations Where Repetitions are Allowed
    6. 2.6 Counting the Elements of a List
    7. 2.7 Pigeonhole Principle
    8. 2.8 Probability
    9. 2.9 Conditional Probability
    10. 2.10 Independent Events
    11. 2.11 Probability Distribution
    12. Exercises
  10. Chapter 3 Recurrence Relations
    1. 3.1 Recurrence Relations
    2. 3.2 Explicit Formula for a Sequence
    3. 3.3 Solutions of Recurrence Relations
    4. 3.4 Homogeneous Recurrence Relations with Constant Coefficients
    5. 3.5 Particular Solution of a Difference Equation
    6. 3.6 Recursive Functions
    7. 3.7 Generating Functions
    8. 3.8 Convolution of Numeric Functions
    9. 3.9 Solution of Recurrence Relations by the Method of Generating Function
    10. Exercises
  11. Chapter 4 Logic
    1. 4.1 Propositions
    2. 4.2 Basic Logical Operations
    3. 4.3 Logical Equivalence Involving Tautologies and Contradictions
    4. 4.4 Conditional Propositions
    5. 4.5 Quantifiers
    6. 4.6 Universal Modus Ponens
    7. 4.7 Universal Modus Tollens
    8. 4.8 Use of Diagrams for Validity of Arguments
    9. Exercises
  12. Chapter 5 Algebraic Structures
    1. 5.1 Binary Operations
    2. 5.2 Properties of Binary Operation
    3. 5.3 Semigroups and Monoids
    4. 5.4 Homomorphism of Semigroups
    5. 5.5 Quotient Structures
    6. 5.6 Equivalence Classes
    7. 5.7 Direct Product of Semigroups
    8. 5.8 Groups
    9. 5.9 Subgroups
    10. 5.10 Normal Subgroup
    11. 5.11 Quotient Group (Factor Group)
    12. 5.12 Homomorphism of Groups
    13. 5.13 Cyclic Groups
    14. 5.14 Permutation Groups
    15. 5.15 Direct Product and Direct Sum of Groups
    16. 5.16 Group as Direct Product of its Subgroups
    17. 5.17 Rings
    18. 5.18 Ring Homomorphism
    19. 5.19 Ideals and Quotient Rings
    20. 5.20 Polynomial Rings
    21. 5.21 Division Algorithm for Polynomials Over a Field
    22. 5.22 Algebraic Coding Theory
    23. Exercises
  13. Chapter 6 Lattices
    1. 6.1 Lattice
    2. 6.2 Properties of Lattices
    3. 6.3 Lattices as Algebraic System
    4. 6.4 Lattice Isomorphism
    5. 6.5 Bounded, Complemented and Distributive Lattices
    6. Exercises
  14. Chapter 7 Boolean Algebra
    1. 7.1 Definitions and Basic Properties
    2. 7.2 Representation Theorem
    3. 7.3 Boolean Expressions
    4. 7.4 Logic Gates and Circuits
    5. 7.5 Boolean Function
    6. 7.6 Method to Find Truth Table of a Boolean Function
    7. 7.7 Expressing Boolean Functions as Boolean Polynomials
    8. 7.8 Addition of Binary Digits
    9. Exercises
  15. Chapter 8 Graphs
    1. 8.1 Definitions and Basic Concepts
    2. 8.2 Special Graphs
    3. 8.3 Subgraphs
    4. 8.4 Isomorphisms of Graphs
    5. 8.5 Walks, Paths and Circuits
    6. 8.6 Eulerian Paths and Circuits
    7. 8.7 Hamiltonian Circuits
    8. 8.8 Matrix Representation of Graphs
    9. 8.9 Planar Graphs
    10. 8.10 Colouring of Graph
    11. 8.11 Directed Graphs
    12. 8.12 Trees
    13. 8.13 Isomorphism of Trees
    14. 8.14 Representation of Algebraic Expressions by Binary Trees
    15. 8.15 Spanning Tree of a Graph
    16. 8.16 Shortest Path Problem
    17. 8.17 Minimal Spanning Tree
    18. 8.18 Cut Sets
    19. 8.19 Tree Searching
    20. 8.20 Transport Networks
    21. Exercises
  16. Chapter 9 Finite State Automata
    1. 9.1 Finite State Machines
    2. 9.2 Finite State Automata
    3. 9.3 Non-Deterministic Finite State Automaton
    4. 9.4 Equivalence of DFSA and NDFSA
    5. 9.5 Moore Machine and Mealy Machine
    6. 9.6 Godel Numbers
    7. 9.7 Turing Machine
    8. Exercises
  17. Chapter 10 Languages and Grammars
    1. 10.1 Languages and Regular Expressions
    2. 10.2 Language Determined by a Finite-State Automaton
    3. 10.3 Grammars
    4. 10.4 Derivation Trees of Context-Free Grammars
    5. Exercises
  18. Appendix
  19. Answers to Exercises
  20. Copyright