Essentials of Discrete Mathematics, 3rd Edition

Essentials of Discrete Mathematics, 3rd Edition

by David J. Hunter
Released September 2015
Publisher(s): Jones & Bartlett Learning
ISBN: 9781284056259

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

Written for the one-term course, the Third Edition of Essentials of Discrete Mathematics is designed to serve computer science majors as well as students from a wide range of disciplines. 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. tudents 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.

Table of contents

  1. Cover
  2. Title Page
  3. Copyright
  4. Contents
  5. Preface
  6. How to Use This Book
  7. Chapter 1 Logical Thinking
    1. 1.1 Formal Logic
      1. 1.1.1 Inquiry Problems
      2. 1.1.2 Connectives and Propositions
      3. 1.1.3 Truth Tables
      4. 1.1.4 Logical Equivalences
      5. Exercises 1.1
    2. 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
      5. Exercises 1.2
    3. 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
    4. 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
      5. Exercises 1.4
    5. 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
      4. 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
      4. Exercises 2.1
    2. 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
    3. 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
      4. Exercises 2.3
    4. 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
      6. Exercises 2.4
    5. 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‡
      6. Exercises 2.5
    6. 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
      7. 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
      4. Exercises 3.1
    2. 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
    3. 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
      5. Exercises 3.3
    4. 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
      5. Exercises 3.4
    5. 3.5 Recursive Data Structures
      1. 3.5.1 Lists
      2. 3.5.2 Efficiency
      3. 3.5.3 Binary Search Trees Revisited
      4. 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
      4. Exercises 4.1
    2. 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
    3. 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‡
      5. Exercises 4.3
    4. 4.4 Discrete Probability
      1. 4.4.1 Definitions and Examples
      2. 4.4.2 Applications
      3. 4.4.3 Expected Value
      4. Exercises 4.4
    5. 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
      7. Exercises 4.5
    6. 4.6 Estimation
      1. 4.6.1 Growth of Functions
      2. 4.6.2 Estimation Targets
      3. 4.6.3 Properties of Big-Θ
      4. 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
      5. Exercises 5.1
    2. 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
    3. 5.3 Algorithm Complexity
      1. 5.3.1 The Good, the Bad, and the Average
      2. 5.3.2 Approximate Complexity Calculations
      3. Exercises 5.3
    4. 5.4 Bounds on Complexity
      1. 5.4.1 Algorithms as Decisions
      2. 5.4.2 A Lower Bound
      3. 5.4.3 Searching an Array
      4. 5.4.4 Sorting
      5. 5.4.5 P vs. NP
      6. Exercises 5.4
    5. 5.5 Program Verification
      1. 5.5.1 Verification vs. Testing
      2. 5.5.2 Verifying Recursive Algorithms
      3. 5.5.3 Searching and Sorting
      4. 5.5.4 Towers of Hanoi
      5. Exercises 5.5
    6. 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
      4. 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
      4. Exercises 6.1
    2. 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
      5. Exercises 6.2
    3. 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
      5. Exercises 6.3
    4. 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
      5. Exercises 6.4
    5. 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
      5. 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, 3rd Edition
  • Author(s): David J. Hunter
  • Release date: September 2015
  • Publisher(s): Jones & Bartlett Learning
  • ISBN: 9781284056259