Description

Features

• Strong emphasis on reading and writing proofs – Illustrates most proofs of theorems with annotated figures to provide additional explanation and insight into the proofs.

• Extensive discussion of algorithms, recursive algorithms, and the analysis of algorithms – The algorithms are written in a flexible form of pseudocode, which resembles currently popular languages such as C, C++, and Java.

• Over 500 worked examples throughout the text.

• Over 3500 exercises – Approximately one third have answers at the back of the book.

• Extensive applications with an emphasis on computer science.

• Emphasis on the interplay among the various topics – For example, mathematical induction is closely tied to recursive algorithms; the Fibonacci sequence is used in the analysis of the Euclidean algorithm; many exercises throughout the book require mathematical induction; demonstrations of how to characterize the components of a graph by defining an equivalence relation on the set of vertices; and more.

• Figures and tables – Illustrate concepts, show how algorithms work, elucidate proofs, and motivate the material. Figure captions provide additional explanation and insight into figures accompanying proofs.

• Summaries of the mathematical and algorithm notation used in the book on the inside covers.

New To This Edition

• Increased number of examples and exercises throughout:

– Also expands discussion and adds motivation for most of the examples.

– More examples and exercises are included to highlight common errors

• Expanded treatment of problem solving:

– Problem-Solving Tips sections include expanded advice and examples on how to do proofs, how to write up proofs, and common errors in  proofs.

– Two new Problem-Solving Corners have been added, one on quantifiers, the other on proofs (see Proving Some Properties of Real Numbers).

• Expanded discussion of proof writing:

– Sections 2.1 and 2.2 are new extended sections on mathematical systems and proof techniques.

– There are expanded subsections on proofs of equivalence and existence proofs (including constructive and nonconstructive existence proofs).

– Nearly every proof is preceded by a Discussion section and/or accompanied by a figure.

Reorganization of introductory chapters:

– The first chapter from the previous edition (Logic and Proofs) has been divided into two chapters – Logic (Chapter 1) and Proofs (Chapter 2).

– Except for the section on sets, Chapters 2 (The Language of Mathematics) and 3 (Relations) in the sixth edition have been combined into Chapter 3 (Functions, Sequences, and Relations) in this revision.

• Earlier introduction of sets – Now the first section of the book.

– Permits the use of set terminology throughout the book.

– Makes sets available for proofs in examples and exercises, thus providing more interesting examples earlier than in the previous editions.

• Content-specific changes:

– The description and notation for integers (Z, Z⁺ , Z⁻ , Z^nonneg), rational numbers (with Z replaced by Q), and real numbers (with Z replaced by R) are introduced early (in Section 1.1, Sets).

– Proofs, rather than sketches of proofs as in the sixth edition, are provided for Theorems 5.1.17 and 5.1.22, which give the greatest common divisor and least common multiple of two integers given their prime factorizations.

– Recursive algorithms are given (Algorithms 5.3.9 and 5.3.10) to compute the greatest common divisor of two integers a and b, gcd(a, b), and to compute integers s and t satisfying gcd(a, b) = sa + tb.

– The Inclusion-Exclusion Principle has been added to Section 6.1.

– Internet addressing is now included in Section 6.1.

– Several practice exercises have been added to Section 6.1 that specifically say to use either the Multiplication Principle or the Addition Principle. These exercises precede other exercises that require the reader to figure out which Principle to use or require using both Principles.

– The section on Generalized Permutations and Combinations (Section 6.6 in the sixth edition) now follows Sections 6.1 and 6.2 (Basic Principles, Permutations and Combinations) since generalized permutations and combinations are so closely related to the material in Sections 6.1 and 6.2.

– More exercises on graph isomorphism have been added (Section 8.6). The exercises have been divided into those that ask for a proof that two given graphs are isomorphic, those that ask for a proof that two given graphs are not isomorphic, and those that ask the reader to determine, with a proof, whether two given graphs are isomorphic.

– In Section 9.3, there are several new backtracking exercises including the popular Sudoku puzzle.

• Updated Web site at http://condor.depaul.edu/~rjohnson/dm7th/

– Includes expanded explanations of difficult material and links to other sites for additional information about discrete mathematics topics.

– A WWW icon signals that an expanded explanation or a link is at the book’s web site.

– Also includes supplementary material, computer programs, and an errata list.

Table of Contents

1 Sets and Logic

1.1 Sets

1.2 Propositions

1.3 Conditional Propositions and Logical Equivalence

1.4 Arguments and Rules of Inference

1.5 Quantifiers

1.6 Nested Quantifiers

Problem-Solving Corner: Quantifiers

2 Proofs

2.1 Mathematical Systems, Direct Proofs, and Counterexamples

2.2 More Methods of Proof

Problem-Solving Corner: Proving Some Properties of Real Numbers

2.3 Resolution Proofs

2.4 Mathematical Induction

Problem-Solving Corner: Mathematical Induction

2.5 Strong Form of Induction and the Well-Ordering Property Notes Chapter Review Chapter Self-Test Computer Exercises

3 Functions, Sequences, and Relations

3.1 Functions

Problem-Solving Corner: Functions

3.2 Sequences and Strings

3.3 Relations

3.4 Equivalence Relations

Problem-Solving Corner: Equivalence Relations

3.5 Matrices of Relations

3.6 Relational Databases

4 Algorithms

4.1 Introduction

4.2 Examples of Algorithms

4.3 Analysis of Algorithms

Problem-Solving Corner: Design and Analysis of an Algorithm

4.4 Recursive Algorithms

5 Introduction to Number Theory

5.1 Divisors

5.2 Representations of Integers and Integer Algorithms

5.3 The Euclidean Algorithm

Problem-Solving Corner: Making Postage

5.4 The RSA Public-Key Cryptosystem

6 Counting Methods and the Pigeonhole Principle

6.1 Basic Principles

Problem-Solving Corner: Counting

6.2 Permutations and Combinations

Problem-Solving Corner: Combinations

6.3 Generalized Permutations and Combinations

6.4 Algorithms for Generating Permutations and Combinations

6.5 Introduction to Discrete Probability

6.6 Discrete Probability Theory

6.7 Binomial Coefficients and Combinatorial Identities

6.8 The Pigeonhole Principle

7 Recurrence Relations

7.1 Introduction

7.2 Solving Recurrence Relations

Problem-Solving Corner: Recurrence Relations

7.3 Applications to the Analysis of Algorithms

8 Graph Theory

8.1 Introduction

8.2 Paths and Cycles

Problem-Solving Corner: Graphs

8.3 Hamiltonian Cycles and the Traveling Salesperson Problem

8.4 A Shortest-Path Algorithm

8.5 Representations of Graphs

8.6 Isomorphisms of Graphs

8.7 Planar Graphs

8.8 Instant Insanity

9 Trees

9.1 Introduction

9.2 Terminology and Characterizations of Trees

Problem-Solving Corner: Trees

9.3 Spanning Trees

9.4 Minimal Spanning Trees

9.5 Binary Trees

9.6 Tree Traversals

9.7 Decision Trees and the Minimum Time for Sorting

9.8 Isomorphisms of Trees

9.9 Game Trees

10 Network Models

10.1 Introduction

10.2 A Maximal Flow Algorithm

10.3 The Max Flow, Min Cut Theorem

10.4 Matching

Problem-Solving Corner: Matching

11 Boolean Algebras and Combinatorial Circuits

11.1 Combinatorial Circuits

11.2 Properties of Combinatorial Circuits

11.3 Boolean Algebras

Problem-Solving Corner: Boolean Algebras

11.4 Boolean Functions and Synthesis of Circuits

11.5 Applications

12 Automata, Grammars, and Languages

12.1 Sequential Circuits and Finite-State Machines

12.2 Finite-State Automata

12.3 Languages and Grammars

12.4 Nondeterministic Finite-State Automata

12.5 Relationships Between Languages and Automata

13 Computational Geometry

13.1 The Closest-Pair Problem

13.2 An Algorithm to Compute the Convex Hull

Appendix

A Matrices

B Algebra Review

C Pseudocode

References

Hints and Solutions to Selected Exercises Index

Courses

Discrete Math  (Mathematics)

Downloadable Instructor Resources

Show All Downloadable Files

Hide All Downloadable Files

|

Help Downloading Files

Instructor's Solutions Manual for Discrete Mathematics, 7/E
Johnsonbaugh
©2009  |  Pearson  |  Paper; 244 pp  |  Instock
ISBN-10: 0136037380  |  ISBN-13: 9780136037385

Show Downloadable Files

Hide Downloadable Files

|

More Info

Back to top

Discrete Math Workbook: Interactive Exercises
Bush
©2003  |  Pearson  |  Paper; 404 pp  |  Instock
ISBN-10: 0130463272  |  ISBN-13: 9780130463272
Suggested retail price:  $41.00Net price: $30.75  (What's this?)More Info

Practice Problems in Discrete Mathematics
Obrenic
©2003  |  Pearson  |  Paper; 275 pp  |  Instock
ISBN-10: 0130458031  |  ISBN-13: 9780130458032
Suggested retail price:  $40.60Net price: $30.45  (What's this?)More Info

Back to top

Allied Health Study Card, 2/E
Forshier
©2006  |  Pearson  |  Study Card  |  Instock
ISBN-10: 0321394747  |  ISBN-13: 9780321394743
Suggested retail price:  $4.00    Buy from myPearsonStoreNet price: $3.00  (What's this?)More Info

Basic Math Review Card, 2/E
Addison-Wesley
©2006  |  Pearson  |  Study Card; 6 pp  |  Instock
ISBN-10: 0321394763  |  ISBN-13: 9780321394767
Suggested retail price:  $4.00    Buy from myPearsonStoreNet price: $3.00  (What's this?)More Info

Center for Excellence Sticker
Addison Wesley Higher Education Group
©2000  |  Pearson  |  Unknown / Other  |  Instock
ISBN-10: 0201716275  |  ISBN-13: 9780201716276
Suggested retail price:  $0.00Net price: $0.00  (What's this?)More Info

Concept Videos: Algebra
Addison-Wesley
©2008  |  Pearson  |  Multiple Media Package  |  Instock
ISBN-10: 0321517199  |  ISBN-13: 9780321517197
Suggested retail price:  $36.67Net price: $27.50  (What's this?)More Info

Concept Videos: Basic Math & Prealgebra
Addison-Wesley
©2008  |  Pearson  |  Multiple Media Package  |  Instock
ISBN-10: 032151758X  |  ISBN-13: 9780321517586
Suggested retail price:  $36.67Net price: $27.50  (What's this?)More Info

Discovering Algebra: Examples with Keystrokes on the TI-83/TI-82 and TI-85/TI-86, A Laboratory Approach
Pirich & Bigliani
©1997  |  Pearson  |  Paper; 195 pp  |  Instock
ISBN-10: 0136492037  |  ISBN-13: 9780136492030
Suggested retail price:  $47.80    Buy from myPearsonStoreNet price: $35.85  (What's this?)More Info

Graphing Calculator Tutorial CD
Addison-Wesley
©2006  |  Pearson  |  CD-ROM Only  |  Instock
ISBN-10: 0321357744  |  ISBN-13: 9780321357748
Suggested retail price:  $13.33    Buy from myPearsonStoreNet price: $10.00  (What's this?)More Info

Overcoming Math Anxiety, 2/E
Davidson & Levitov
©2000  |  Pearson  |  Paper  |  Instock
ISBN-10: 0321069188  |  ISBN-13: 9780321069184
Suggested retail price:  $36.67    Buy from myPearsonStoreNet price: $27.50  (What's this?)More Info

Prealgebra Review Workbook
Wheel
©2006  |  Pearson  |  Paper; 300 pp  |  Instock
ISBN-10: 0321473329  |  ISBN-13: 9780321473325
Suggested retail price:  $36.67    Buy from myPearsonStoreNet price: $27.50  (What's this?)More Info

Review of Algebra, A
Howard
©2002  |  Pearson  |  Paper; 224 pp  |  Instock
ISBN-10: 0201773473  |  ISBN-13: 9780201773477
Suggested retail price:  $36.67    Buy from myPearsonStoreNet price: $27.50  (What's this?)More Info

Spanish Basic Math Study Card
Leonarte
©2007  |  Pearson  |  Study Card  |  Instock
ISBN-10: 0321438582  |  ISBN-13: 9780321438584
Suggested retail price:  $4.00    Buy from myPearsonStoreNet price: $3.00  (What's this?)More Info

TestGen All-in-One 2005 Package
Addison-Wesley
©2005  |  Pearson  |  CD-ROM Only  |  Instock
ISBN-10: 0321334469  |  ISBN-13: 9780321334466
Suggested retail price:  $0.00Net price: $0.00  (What's this?)More Info

Back to top

Back to top

Give your students a choice! PearsonChoices products are designed to give your students more value and flexibility by letting them choose from a variety of text and media formats to best match their learning style and their budget.

Pearson Higher Education offers special pricing when you choose to package your text with other student resources. If you're interested in creating a cost-saving package for your students, see the Packages Tab.

• Discrete Mathematics, CourseSmart eTextbook, 7/E
  Johnsonbaugh
  ©2009  |  Pearson  |  Electronic Book; 792 pp  |  Available
  ISBN-10: 0132082853  |  ISBN-13: 9780132082853
  Online purchase price: $55.99Brief Description  | 

  

  CourseSmart eTextbooks are a creative digital solution that offers the freedom and convenience of online, offline, and mobile access using a single platform. With a CourseSmart eTextbook, students can:

  • search the text

  • make notes online

  • print out reading assignments that incorporate lecture notes

  • bookmark important passages for later review

  • save money. As an alternative to purchasing the print textbook, students can subscribe to the same content online for a significant discount off the suggested list price of the print text.

  For more information, or to subscribe to the CourseSmart eTextbook, visit www.coursesmart.com (for customers in U.S. and Canada) or www.coursesmart.co.uk (for customers in Europe, Middle East, and Africa).

  More Info  |  Students, buy access
  

• Pearson Custom Mathematics
  Pearson
  ©2009  |  Pearson  |  On-line Supplement  |  Live
  ISBN-10: 0321625242  |  ISBN-13: 9780321625243
  This online resource is available at no cost at http://www.pearsoncustom.com/custom-library/pearson-custom-mathematics.
  More Info
  

This product is a member of the following series. Click on the series name to see the full list of products in the series.

• Pearson Custom Mathematics

Pearson Higher Education offers special pricing when you choose to package your text with other student resources. If you're interested in creating a cost-saving package for your students, browse our available packages below, or contact your Pearson Higher Education representative to create your own package.

Package ISBN-10: 0321632729 | ISBN-13: 9780321632722
©2009 | Instock (Additional assembly time required)
Suggested retail price: $138.67  Buy from myPearsonStore
Net price: $104.00  (What's this?)
This package contains: