Essentials of Discrete Mathematics, 2nd Edition

Essentials of Discrete Mathematics, 2nd Edition

by Hunter
Released December 2010
Publisher(s): Jones & Bartlett Learning
ISBN: 9781449604448

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

Essentials of Discrete Mathematics, Second Edition is the ideal text for a one-term discrete mathematics course to serve computer science majors as well as students from a wide range of other disciplines. It introduces students to the mathematical way of thinking, and also to many important modern applications. The material is organized around five types of thinking: logical, relational, recursive, quantitative, and analytical. This presentation results in a coherent outline that steadily builds upon mathematical sophistication. Graphs are introduced early and referred to throughout the text, providing a richer context for examples and applications. Students will encounter algorithms near the end of the text, after they have acquired the skills and experience needed to analyze them. The final chapter contains in-depth case studies from a variety of fields, including biology, sociology, linguistics, economics, and music. Clear and concise, Essentials of Discrete Mathematics presents a unified and complete picture of discrete mathematics that instructors can cover in a single semester.

Table of contents

  1. Cover Page
  2. Title Page
  3. Copyright Page
  4. Table of Contents
  5. Preface
  6. How to Use This Book
  7. Chapter 1 Logical Thinking
    1. 1.1 Formal Logic
      1. 1.1.1 Connectives and Propositions
      2. 1.1.2 Truth Tables
      3. 1.1.3 Logical Equivalences
    2. Exercises 1.1
    3. 1.2 Propositional Logic
      1. 1.2.1 Tautologies and Contradictions
      2. 1.2.2 Derivation Rules
      3. 1.2.3 Proof Sequences
      4. 1.2.4 Forward—Backward
    4. Exercises 1.2
    5. 1.3 Predicate Logic
      1. 1.3.1 Predicates
      2. 1.3.2 Quantifiers
      3. 1.3.3 Translation
      4. 1.3.4 Negation
      5. 1.3.5 Two Common Constructions
    6. Exercises 1.3
    7. 1.4 Logic in Mathematics
      1. 1.4.1 The Role of Definitions in Mathematics
      2. 1.4.2 Other Types of Mathematical Statements
      3. 1.4.3 Counterexamples
      4. 1.4.4 Axiomatic Systems
    8. Exercises 1.4
    9. 1.5 Methods of Proof
      1. 1.5.1 Direct Proofs
      2. 1.5.2 Proof by Contraposition
      3. 1.5.3 Proof by Contradiction
    10. Exercises 1.5
  8. Chapter 2 Relational Thinking
    1. 2.1 Graphs
      1. 2.1.1 Edges and Vertices
      2. 2.1.2 Terminology
      3. 2.1.3 Modeling Relationships with Graphs
    2. Exercises 2.1
    3. 2.2 Sets
      1. 2.2.1 Membership and Containment
      2. 2.2.2 New Sets from Old
      3. 2.2.3 Identities
    4. Exercises 2.2
    5. 2.3 Functions
      1. 2.3.1 Definition and Examples
      2. 2.3.2 One-to-One and Onto Functions
      3. 2.3.3 New Functions from Old
    6. Exercises 2.3
    7. 2.4 Relations and Equivalences
      1. 2.4.1 Definition and Examples
      2. 2.4.2 Graphs of Relations
      3. 2.4.3 Relations vs. Functions
      4. 2.4.4 Equivalence Relations
      5. 2.4.5 Modular Arithmetic
    8. Exercises 2.4
    9. 2.5 Partial Orderings
      1. 2.5.1 Definition and Examples
      2. 2.5.2 Hasse Diagrams
      3. 2.5.3 Topological Sorting
      4. 2.5.4 Isomorphisms
      5. 2.5.5 Boolean Algebras ‡
    10. Exercises 2.5
    11. 2.6 Graph Theory
      1. 2.6.1 Graphs: Formal Definitions
      2. 2.6.2 Isomorphisms of Graphs
      3. 2.6.3 Degree Counting
      4. 2.6.4 Euler Paths and Circuits
      5. 2.6.5 Hamilton Paths and Circuits
      6. 2.6.6 Trees
    12. Exercises 2.6
  9. Chapter 3 Recursive Thinking
    1. 3.1 Recurrence Relations
      1. 3.1.1 Definition and Examples
      2. 3.1.2 The Fibonacci Sequence
      3. 3.1.3 Modeling with Recurrence Relations
    2. Exercises 3.1
    3. 3.2 Closed-Form Solutions and Induction
      1. 3.2.1 Guessing a Closed-Form Solution
      2. 3.2.2 Polynomial Sequences: Using Differences ‡
      3. 3.2.3 Inductively Verifying a Solution
    4. Exercises 3.2
    5. 3.3 Recursive Definitions
      1. 3.3.1 Definition and Examples
      2. 3.3.2 Writing Recursive Definitions
      3. 3.3.3 Recursive Geometry
      4. 3.3.4 Recursive Jokes
    6. Exercises 3.3
    7. 3.4 Proof by Induction
      1. 3.4.1 The Principle of Induction
      2. 3.4.2 Examples
      3. 3.4.3 Strong Induction
      4. 3.4.4 Structural Induction
    8. Exercises 3.4
    9. 3.5 Recursive Data Structures
      1. 3.5.1 Lists
      2. 3.5.2 Efficiency
      3. 3.5.3 Binary Search Trees Revisited
    10. Exercises 3.5
  10. Chapter 4 Quantitative Thinking
    1. 4.1 Basic Counting Techniques
      1. 4.1.1 Addition
      2. 4.1.2 Multiplication
      3. 4.1.3 Mixing Addition and Multiplication
    2. Exercises 4.1
    3. 4.2 Selections and Arrangements
      1. 4.2.1 Permutations: The Arrangement Principle
      2. 4.2.2 Combinations: The Selection Principle
      3. 4.2.3 The Binomial Theorem‡
    4. Exercises 4.2
    5. 4.3 Counting with Functions
      1. 4.3.1 One-to-One Correspondences
      2. 4.3.2 The Pigeonhole Principle
      3. 4.3.3 The Generalized Pigeonhole Principle
      4. 4.3.4 Ramsey Theory ‡
    6. Exercises 4.3
    7. 4.4 Discrete Probability
      1. 4.4.1 Definitions and Examples
      2. 4.4.2 Applications
      3. 4.4.3 Expected Value
    8. Exercises 4.4
    9. 4.5 Counting Operations in Algorithms
      1. 4.5.1 Algorithms
      2. 4.5.2 Pseudocode
      3. 4.5.3 Sequences of Operations
      4. 4.5.4 Loops
      5. 4.5.5 Arrays
      6. 4.5.6 Sorting
    10. Exercises 4.5
    11. 4.6 Estimation
      1. 4.6.1 Growth of Functions
      2. 4.6.2 Estimation Targets
      3. 4.6.3 Properties of Big-Θ
    12. Exercises 4.6
  11. Chapter 5 Analytical Thinking
    1. 5.1 Algorithms
      1. 5.1.1 More Pseudocode
      2. 5.1.2 Preconditions and Postconditions
      3. 5.1.3 Iterative Algorithms
      4. 5.1.4 Functions and Recursive Algorithms
    2. Exercises 5.1
    3. 5.2 Three Common Types of Algorithms
      1. 5.2.1 Traversal Algorithms
      2. 5.2.2 Greedy Algorithms
      3. 5.2.3 Divide-and-Conquer Algorithms
    4. Exercises 5.2
    5. 5.3 Algorithm Complexity
      1. 5.3.1 The Good, the Bad, and the Average
      2. 5.3.2 Approximate Complexity Calculations
    6. Exercises 5.3
      1. 5.4 Bounds on Complexity
      2. 5.4.1 Algorithms as Decisions
      3. 5.4.2 A Lower Bound
      4. 5.4.3 Searching an Array
      5. 5.4.4 Sorting
      6. 5.4.5 P vs. NP
    7. Exercises 5.4
    8. 5.5 Program Verification
      1. 5.5.1 Verification versus Testing
      2. 5.5.2 Verifying Recursive Algorithms
      3. 5.5.3 Searching and Sorting
      4. 5.5.4 Towers of Hanoi
    9. Exercises 5.5
    10. 5.6 Loop Invariants
      1. 5.6.1 Verifying Iterative Algorithms
      2. 5.6.2 Searching and Sorting
      3. 5.6.3 Using Invariants to Design Algorithms
    11. Exercises 5.6
  12. Chapter 6 Thinking Through Applications
    1. 6.1 Patterns in DNA
      1. 6.1.1 Mutations and Phylogenetic Distance
      2. 6.1.2 Phylogenetic Trees
      3. 6.1.3 UPGMA
    2. Exercises 6.1
    3. 6.2 Social Networks
      1. 6.2.1 Definitions and Terminology
      2. 6.2.2 Notions of Equivalence
      3. 6.2.3 Hierarchical Clustering
      4. 6.2.4 Signed Graphs and Balance
    4. Exercises 6.2
    5. 6.3 Structure of Languages
      1. 6.3.1 Terminology
      2. 6.3.2 Finite-State Machines
      3. 6.3.3 Recursion
      4. 6.3.4 Further Issues in Linguistics
    6. Exercises 6.3
    7. 6.4 Discrete-Time Population Models
      1. 6.4.1 Recursive Models for Population Growth
      2. 6.4.2 Fixed Points, Equilibrium, and Chaos
      3. 6.4.3 Predator-Prey Systems
      4. 6.4.4 The SIR Model
    8. Exercises 6.4
    9. 6.5 Twelve-Tone Music
      1. 6.5.1 Twelve-Tone Composition
      2. 6.5.2 Listing All Permutations
      3. 6.5.3 Transformations of Tone Rows
      4. 6.5.4 Equivalence Classes and Symmetry
    10. Exercises 6.5
  13. Hints, Answers, and Solutions to Selected Exercises
    1. 1.1 Formal Logic
    2. 1.2 Propositional Logic
    3. 1.3 Predicate Logic
    4. 1.4 Logic in Mathematics
    5. 1.5 Methods of Proof
    6. 2.1 Graphs
    7. 2.2 Sets
    8. 2.3 Functions
    9. 2.4 Relations and Equivalences
    10. 2.5 Partial Orderings
    11. 2.6 Graph Theory
    12. 3.1 Recurrence Relations
    13. 3.2 Closed-Form Solutions and Induction
    14. 3.3 Recursive Definitions
    15. 3.4 Proof by Induction
    16. 3.5 Recursive Data Structures
    17. 4.1 Basic Counting Techniques
    18. 4.2 Selections and Arrangements
    19. 4.3 Counting with Functions
    20. 4.4 Discrete Probability
    21. 4.5 Counting Operations in Algorithms
    22. 4.6 Estimation
    23. 5.1 Algorithms
    24. 5.2 Three Common Types of Algorithms
    25. 5.3 Algorithm Complexity
    26. 5.4 Bounds on Complexity
    27. 5.5 Program Verification
    28. 5.6 Loop Invariants
  14. Selected References
  15. Index
  16. Index of Symbols

Product information

  • Title: Essentials of Discrete Mathematics, 2nd Edition
  • Author(s): Hunter
  • Release date: December 2010
  • Publisher(s): Jones & Bartlett Learning
  • ISBN: 9781449604448