Discrete Mathematics

Discrete Mathematics

by Rajendra Akerkar, Rupali Akerkar
Released November 2007
Publisher(s): Pearson India
ISBN: 9788131717943

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 Mathematics provides an introduction to some of the fundamental concepts in modern mathematics. Abundant examples help explain the principles and practices of discrete mathematics. The book intends to cover material required by readers for whom mathematics is just a tool, as well as provide a strong foundation for mathematics majors. The vital role that discrete mathematics plays in computer science is strongly emphasized as well. The book is useful for students and instructors, and also software professionals.

Table of contents

  1. Cover
  2. Title Page
  3. Contents
  4. Dedication
  5. Preface
  6. Proof Methods and Induction
    1. Formal Proofs
    2. Proofs and the Real World
    3. Propositional Reasoning Examples
    4. Proofs by Contradiction
    5. Proofs
    6. False Proofs
    7. Inductive Proofs
    8. More Simple Induction
    9. Tiling Problem
    10. Geometry
    11. Double Induction
    12. Strong Induction
    13. Tournaments
    14. Induction, Strong Induction, and Well-ordering
    15. Structural Induction
    16. Induction and Recursive Algorithms
  7. 1. Symbolic Logic
    1. 1.1 Introduction to Logic
    2. 1.2 Boolean Expressions
    3. 1.3 Construction of Boolean Expressions
    4. 1.4 Meaning of Boolean Expressions
    5. 1.5 Construction of Truth Tables
    6. 1.6 Logical Equivalence
    7. 1.7 DeMorgan’s Law
    8. 1.8 Why Use Logical Equivalences
    9. 1.9 Tautologies and Contradictions
    10. 1.10 Implication and Biconditionals
    11. 1.11 Logical Equivalences
    12. 1.12 Another Equivalence
    13. 1.13 Negation of Conditionals
    14. 1.14 Variations on a Theme
    15. 1.15 Translations
    16. 1.16 Arguments
    17. 1.17 Fallacies
    18. 1.18 Valid Argument with a False Conclusion
    19. 1.19 Contradiction Rule
    20. 1.20 Applications of Boolean Expressions
    21. 1.21 Logic Gates
    22. 1.22 How to Construct Circuits
    23. 1.23 How to Derive a Boolean Expression
    24. 1.24 Creating a Circuit from Truth Tables
    25. 1.25 Adders
    26. 1.26 Predicate Calculus
    27. 1.27 Boolean Formulas
    28. 1.28 Understanding Quantifiers
    29. 1.29 Negation of Quantifiers
    30. 1.30 Vacuously True Statements
    31. 1.31 Normal Forms in Propositional Logic
    32. 1.32 Normal Forms in Predicate Logic
    33. 1.33 The Resolution Principle
    34. 1.34 Parenthesized Infix Notation and Polish Notation
  8. 2. Set Theory
    1. 2.1 Definitions
    2. 2.2 Set Specification
    3. 2.3 Set Operations
    4. 2.4 Characteristic Function
    5. 2.5 Fuzzy Set Theory
    6. 2.6 Basic Notions of Fuzzy Set
  9. 3. Relations
    1. 3.1 Operations on Relations
    2. 3.2 Computing the Transitive Closure
    3. 3.3 Equivalence Relation and Partitions
    4. 3.4 Partial Orders
    5. 3.5 Ordered Pairs
    6. 3.6 Warshall’s Algorithm
    7. 3.7 Application of Relation
  10. 4. Functions and Recursion
    1. 4.1 Functions
    2. 4.2 Recursion
  11. 5. Algebraic Structures
    1. 5.1 Algebra
    2. 5.2 DeMorgan’s Law
    3. 5.3 Group
    4. 5.4 Ring
    5. 5.5 Polish Expressions and Their Compilation
    6. 5.6 The Communication Model and Error Correction
    7. 5.7 Hamming Codes
    8. 5.8 Error Recovery in Group Codes
  12. 6. Graph Theory
    1. 6.1 Introduction
    2. 6.2 Graph Representation
    3. 6.3 Topological Sort
    4. 6.4 Simple Graph Propagation Algorithm
    5. 6.5 Depth-First Search
    6. 6.6 Breadth-First Search
    7. 6.7 Shortest-Path Algorithm
    8. 6.8 Directed Acyclic Graphs
  13. 7. Counting
    1. 7.1 A Party Problem
    2. 7.2 Induction
    3. 7.3 Counting Subsets
    4. 7.4 Pascal’s Triangle
    5. 7.5 Combinatorial Probability
    6. 7.6 Fibonacci Numbers
    7. 7.7 Integers, Divisors, and Primes
  14. 8. Combinatorics
    1. 8.1 The Pigeonhole Principle
    2. 8.2 Strong Pigeonholes
    3. 8.3 Dilworth’s Theorem
    4. 8.4 Problems
    5. 8.5 Sets of the Same Size: Bijections
    6. 8.6 Finite Sets
    7. 8.7 Inclusion-Exclusion
    8. 8.8 Infinite Sets
    9. 8.9 Schroder-Bernstein Theorem
    10. 8.10 Countable Sets
    11. 8.11 The Continuum
    12. 8.12 Diagonal Arguments
    13. 8.13 Set Theory Revisited
    14. 8.14 Functions and Permutations
  15. 9. Automata
    1. 9.1 Introduction
    2. 9.2 Decision Problems vs Functions
    3. 9.3 Finite Automata and Regular Sets
    4. 9.4 More on Regular Sets
    5. 9.5 Nondeterministic Finite Automata
    6. 9.6 The Subset Construction
  16. 10. Program Verification
    1. 10.1 Introduction
    2. 10.2 A Simple Example
    3. 10.3 Linear Search
  17. 11. Design of Algorithms
    1. 11.1 Introduction
    2. 11.2 Greedy Algorithms
    3. 11.3 Backtracking
    4. 11.4 Divide and Conquer
    5. 11.5 Dynamic Programming
  18. Bibliography
  19. Copyright

Product information

  • Title: Discrete Mathematics
  • Author(s): Rajendra Akerkar, Rupali Akerkar
  • Release date: November 2007
  • Publisher(s): Pearson India
  • ISBN: 9788131717943