book

Essentials of Discrete Mathematics, 2nd Edition

Name: Essentials of Discrete Mathematics, 2nd Edition
Author: David J. Hunter
ISBN: 9781449604448

by David J. Hunter

December 2010

Intermediate to advanced

494 pages

11h 20m

English

Jones & Bartlett Learning

Read now

Unlock full access

Cover Page
Title Page
Copyright Page
Table of Contents
Preface
How to Use This Book
Chapter 1 Logical Thinking
1.1 Formal Logic1.1.1 Connectives and Propositions1.1.2 Truth Tables1.1.3 Logical EquivalencesExercises 1.11.2 Propositional Logic1.2.1 Tautologies and Contradictions1.2.2 Derivation Rules1.2.3 Proof Sequences1.2.4 Forward—BackwardExercises 1.21.3 Predicate Logic1.3.1 Predicates1.3.2 Quantifiers1.3.3 Translation1.3.4 Negation1.3.5 Two Common ConstructionsExercises 1.31.4 Logic in Mathematics1.4.1 The Role of Definitions in Mathematics1.4.2 Other Types of Mathematical Statements1.4.3 Counterexamples1.4.4 Axiomatic SystemsExercises 1.41.5 Methods of Proof1.5.1 Direct Proofs1.5.2 Proof by Contraposition1.5.3 Proof by ContradictionExercises 1.5
Chapter 2 Relational Thinking
2.1 Graphs2.1.1 Edges and Vertices2.1.2 Terminology2.1.3 Modeling Relationships with GraphsExercises 2.12.2 Sets2.2.1 Membership and Containment2.2.2 New Sets from Old2.2.3 IdentitiesExercises 2.22.3 Functions2.3.1 Definition and Examples2.3.2 One-to-One and Onto Functions2.3.3 New Functions from OldExercises 2.32.4 Relations and Equivalences2.4.1 Definition and Examples2.4.2 Graphs of Relations2.4.3 Relations vs. Functions2.4.4 Equivalence Relations2.4.5 Modular ArithmeticExercises 2.42.5 Partial Orderings2.5.1 Definition and Examples2.5.2 Hasse Diagrams2.5.3 Topological Sorting2.5.4 Isomorphisms2.5.5 Boolean Algebras ‡Exercises 2.52.6 Graph Theory2.6.1 Graphs: Formal Definitions2.6.2 Isomorphisms of Graphs2.6.3 Degree Counting2.6.4 Euler Paths and Circuits2.6.5 Hamilton Paths and Circuits2.6.6 TreesExercises 2.6
Chapter 3 Recursive Thinking
3.1 Recurrence Relations3.1.1 Definition and Examples3.1.2 The Fibonacci Sequence3.1.3 Modeling with Recurrence RelationsExercises 3.13.2 Closed-Form Solutions and Induction3.2.1 Guessing a Closed-Form Solution3.2.2 Polynomial Sequences: Using Differences ‡3.2.3 Inductively Verifying a SolutionExercises 3.23.3 Recursive Definitions3.3.1 Definition and Examples3.3.2 Writing Recursive Definitions3.3.3 Recursive Geometry3.3.4 Recursive JokesExercises 3.33.4 Proof by Induction3.4.1 The Principle of Induction3.4.2 Examples3.4.3 Strong Induction3.4.4 Structural InductionExercises 3.43.5 Recursive Data Structures3.5.1 Lists3.5.2 Efficiency3.5.3 Binary Search Trees RevisitedExercises 3.5
Chapter 4 Quantitative Thinking
4.1 Basic Counting Techniques4.1.1 Addition4.1.2 Multiplication4.1.3 Mixing Addition and MultiplicationExercises 4.14.2 Selections and Arrangements4.2.1 Permutations: The Arrangement Principle4.2.2 Combinations: The Selection Principle4.2.3 The Binomial Theorem‡Exercises 4.24.3 Counting with Functions4.3.1 One-to-One Correspondences4.3.2 The Pigeonhole Principle4.3.3 The Generalized Pigeonhole Principle4.3.4 Ramsey Theory ‡Exercises 4.34.4 Discrete Probability4.4.1 Definitions and Examples4.4.2 Applications4.4.3 Expected ValueExercises 4.44.5 Counting Operations in Algorithms4.5.1 Algorithms4.5.2 Pseudocode4.5.3 Sequences of Operations4.5.4 Loops4.5.5 Arrays4.5.6 SortingExercises 4.54.6 Estimation4.6.1 Growth of Functions4.6.2 Estimation Targets4.6.3 Properties of Big-ΘExercises 4.6

Chapter 5 Analytical Thinking
5.1 Algorithms5.1.1 More Pseudocode5.1.2 Preconditions and Postconditions5.1.3 Iterative Algorithms5.1.4 Functions and Recursive AlgorithmsExercises 5.15.2 Three Common Types of Algorithms5.2.1 Traversal Algorithms5.2.2 Greedy Algorithms5.2.3 Divide-and-Conquer AlgorithmsExercises 5.25.3 Algorithm Complexity5.3.1 The Good, the Bad, and the Average5.3.2 Approximate Complexity CalculationsExercises 5.35.4 Bounds on Complexity5.4.1 Algorithms as Decisions5.4.2 A Lower Bound5.4.3 Searching an Array5.4.4 Sorting5.4.5 P vs. NPExercises 5.45.5 Program Verification5.5.1 Verification versus Testing5.5.2 Verifying Recursive Algorithms5.5.3 Searching and Sorting5.5.4 Towers of HanoiExercises 5.55.6 Loop Invariants5.6.1 Verifying Iterative Algorithms5.6.2 Searching and Sorting5.6.3 Using Invariants to Design AlgorithmsExercises 5.6
Chapter 6 Thinking Through Applications
6.1 Patterns in DNA6.1.1 Mutations and Phylogenetic Distance6.1.2 Phylogenetic Trees6.1.3 UPGMAExercises 6.16.2 Social Networks6.2.1 Definitions and Terminology6.2.2 Notions of Equivalence6.2.3 Hierarchical Clustering6.2.4 Signed Graphs and BalanceExercises 6.26.3 Structure of Languages6.3.1 Terminology6.3.2 Finite-State Machines6.3.3 Recursion6.3.4 Further Issues in LinguisticsExercises 6.36.4 Discrete-Time Population Models6.4.1 Recursive Models for Population Growth6.4.2 Fixed Points, Equilibrium, and Chaos6.4.3 Predator-Prey Systems6.4.4 The SIR ModelExercises 6.46.5 Twelve-Tone Music6.5.1 Twelve-Tone Composition6.5.2 Listing All Permutations6.5.3 Transformations of Tone Rows6.5.4 Equivalence Classes and SymmetryExercises 6.5
Hints, Answers, and Solutions to Selected Exercises
1.1 Formal Logic1.2 Propositional Logic1.3 Predicate Logic1.4 Logic in Mathematics1.5 Methods of Proof2.1 Graphs2.2 Sets2.3 Functions2.4 Relations and Equivalences2.5 Partial Orderings2.6 Graph Theory3.1 Recurrence Relations3.2 Closed-Form Solutions and Induction3.3 Recursive Definitions3.4 Proof by Induction3.5 Recursive Data Structures4.1 Basic Counting Techniques4.2 Selections and Arrangements4.3 Counting with Functions4.4 Discrete Probability4.5 Counting Operations in Algorithms4.6 Estimation5.1 Algorithms5.2 Three Common Types of Algorithms5.3 Algorithm Complexity5.4 Bounds on Complexity5.5 Program Verification5.6 Loop Invariants
Selected References
Index
Index of Symbols

Content preview from Essentials of Discrete Mathematics, 2nd Edition

Chapter 1Logical Thinking

Mathematicians are in the business of stating things precisely. When you read a mathematical statement, you are meant to take every word seriously; good mathematical language conveys a clear, unambiguous message. In order to read and write mathematics, you must practice the art of logical thinking. The goal of this chapter is to help you communicate mathematically by understanding the basics of logic.

Figure 1.1 Symbols are an important part of the language of mathematics.

A word of warning: mathematical logic can be difficult—especially the first time you see it. This chapter begins with the study of formal, or symbolic, ...

Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.

Read now

Unlock full access

More than 5,000 organizations count on O’Reilly

O’Reilly covers everything we've got, with content to help us build a world-class technology community, upgrade the capabilities and competencies of our teams, and improve overall team performance as well as their engagement.

Julian F.

Head of Cybersecurity

I wanted to learn C and C++, but it didn't click for me until I picked up an O'Reilly book. When I went on the O’Reilly platform, I was astonished to find all the books there, plus live events and sandboxes so you could play around with the technology.

Addison B.

Field Engineer

I’ve been on the O’Reilly platform for more than eight years. I use a couple of learning platforms, but I'm on O'Reilly more than anybody else. When you're there, you start learning. I'm never disappointed.

Amir M.

Data Platform Tech Lead

I'm always learning. So when I got on to O'Reilly, I was like a kid in a candy store. There are playlists. There are answers. There's on-demand training. It's worth its weight in gold, in terms of what it allows me to do.

Mark W.

Embedded Software Engineer

Essentials of Discrete Mathematics, 3rd Edition

Publisher Resources

ISBN: 9781449604424

Cloud Computing

Data Engineering

Data Science

AI & ML

Programming Languages

Software Architecture

IT/Ops

Security

Design

Business

Soft Skills

Essentials of Discrete Mathematics, 2nd Edition

by David J. Hunter

Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.