 Shopping Bag ( 0 items )

All (24) from $65.10

New (11) from $106.40

Used (13) from $65.10
More About This Textbook
Overview
Focused on helping readers understand and construct proofs – and, generally, expanding their mathematical maturity – this bestseller is an accessible introduction to discrete mathematics. Takes an algorithmic approach that emphasizes problemsolving techniques. Expands discussion on how to construct proofs and treatment of problem solving. Increases number of examples and exercises throughout.
Editorial Reviews
Booknews
New edition of a timetested text first published in 1984 in response to a need for a course that extended students' mathematical maturity and ability to deal with abstraction and included useful topics such as combinatorics, algorithms, and graphs. Intended for a oneor two term introductory course, the text does not require knowledge of calculus, and there are no computer science prerequisites. Annotation c. by Book News, Inc., Portland, Or.Product Details
Related Subjects
Meet the Author
Read an Excerpt
PREFACE
This book is intended for a one or twoterm introductory course in discrete mathematics, based on my experience in teaching this course over a 20year period. Formal mathematics prerequisites are minimal; calculus is not required. There are no computer science prerequisites. The book includes examples, exercises, figures, tables, sections on problemsolving, section reviews, notes, chapter reviews, selftests, and computer exercises to help the reader master introductory discrete mathematics. In addition, an Instructor's Guide and World Wide Web site are available.
The main changes in this edition (discussed in more detail later) are an expanded discussion of logic and proofs, the addition of two sections on discrete probability, a new appendix that reviews basic algebra, many new examples and exercises, section reviews, and computer exercises.
OVERVIEW
In the early 1980s there were almost no books appropriate for an introductory course in discrete mathematics. At the same time, there was a need for a course that extended students' mathematical maturity and ability to deal with abstraction and also included useful topics such as combinatorics, algorithms, and graphs. The original edition of this book (1984) addressed this need. Subsequently, discrete mathematics courses were endorsed by many groups for several different audiences, including mathematics and computer science majors. A panel of the Mathematical Association of America (MAA) endorsed a yearlong course in discrete mathematics. The Educational Activities Board of the Institute of Electrical and Electronics Engineers (IEEE) recommended a freshmandiscrete mathematics course. The Association for Computing Machinery (ACM) and IEEE accreditation guidelines mandated a discrete mathematics course. This edition, like its predecessors, includes topics such as algorithms, combinatorics, sets, functions, and mathematical induction endorsed by these groups. It also addresses understanding and doing proofs and, generally, expanding mathematical maturity.
ABOUT THIS BOOK
This book includes
CHANGES FROM THE FOURTH EDITION
CHAPTER STRUCTURE
Each chapter is organized as follows:
— Overview
— Section
— Section Review
— Section Exercises
— Section
— Section Review
— Section Exercises
— Notes
— Chapter Review
— Chapter SelfTest
— Computer Exercises
Section reviews consist of exercises, with answers in the back of the book, that review the key concepts of the section. Notes contain suggestions for further reading. Chapter reviews provide reference lists of the key concepts of the chapters. Chapter selftests contain four exercises per section, with answers in the back of the book. Computer exercises request implementation of some of the algorithms, projects, and other programming related activities. In addition, most chapters have ProblemSolving Corners.
Exercises
The book contains over 3500 exercises, 135 of which are computer exercises. Exercises felt to be more challenging than average are indicated with a star. Exercise numbers in color (approximately onethird of the exercises) indicate that the exercise has a hint or solution in the back of the book. The solutions to the remaining exercises may be found in the Instructor's Guide. A handful of exercises are clearly identified as requiring calculus. No calculus concepts are used in the main body of the book and, except for these marked exercises, no calculus is needed to solve the exercises.
EXAMPLES
The book contains over 500 worked examples. These examples show students how to tackle problems in discrete mathematics, demonstrate applications of the theory, clarify proofs, and help motivate the material. Ends of examples are marked with a square symbol.
PROBLEMSOLVING CORNERS
The ProblemSolving Corner sections help students attack and solve problems and show them how to do proofs. Written in an informal style, each is a selfcontained section following the discussion of the subject of the problem. Rather than simply presenting a proof or a solution to a problem, in these sections the intent is to show alternative ways of attacking a problem, to discuss what to look for in trying to obtain a solution to a problem, and to present problemsolving and proof techniques.
Each ProblemSolving Corner begins with a statement of a problem. After stating the problem, ways to attack the problem are discussed. This discussion is followed by techniques for finding a solution. After a solution is found, a formal solution is given to show how to correctly write up a formal solution. Finally, the problemsolving techniques used in the section are summarized. In addition, some of these sections include a Comments subsection, which discusses connections with other topics in mathematics and computer science, provides motivation for the problem, and lists references for further reading about the problem. Exercises conclude some ProblemSolving Corners.
INSTRUCTOR SUPPLEMENT
An Instructor's Guide is available at no cost from the publisher to instructors who adopt or sample this book. The Instructor's Guide contains solutions to the exercises not included in the book, tips for teaching the course, and transparency masters.
WORLD WIDE WEB SITE
A World Wide Web site
www.prenhall.com/johnsonbaugh
contains
Both instructors and students will find the PowerPoint slides useful. The supplementary material includes the section on Petri nets from the fourth edition.
ACKNOWLEDGMENTS
I received helpful comments from many persons, including Gregory Bachelis, Gregory Brewster, Robert Busby, David G. Cantor, Tim Carroll, Joseph P Chan, HonWing Cheng, IPing Chu, Robert Crawford, Henry D'Angelo, Jerry Delazzer, Br. Michael Driscoll, Carl E. Eckberg, Susanna Epp, Gerald Gordon, Jerrold Grossman, Mark Herbster, Martin Kalin, Nicholas Krier, Warren Krueger, Glenn Lancaster, Donald E. G. Malm, Kevin Phelps, James H. Stoddard, Michael Sullivan, Edward J. Williams, and Hanyi Zhang.
Special thanks for this edition go to my colleague Andre Berthiaume for suggesting the logic game, for developing the PowerPoint slides, and, with Sigrid (Anne) Settle, for the pine cone used in Figure 3.4.1. I appreciate Example 4.5.22, suggested by my colleague Steve Jost, and Exercise 24, Section 9.3, suggested by Reino Hakala, Governors State University. Credit goes to my students Jenni Piane and Nick Meshes for C++ code to implement the tromino tiling algorithm (Algorithm 3.4.4). I am grateful to Herbert Enderton, UCLA, for pointing out the problem with the fourth edition's definition of "bipartite graph." My colleague Gary Andrus, made several suggestions that improved Chapters 9 and 10. Thanks also to all of the users of my book for their helpful letters and email. Finally, for reviewing the manuscript for this edition, thanks go to Kendall Atkinson, University of Iowa; Mansur Samadzadeh, Oklahoma State University; and Chaim Goodman Strauss, University of Arkansas.
I am indebted to Helmut Epp, Dean of the School of Computer Science, Telecommunications and Information Systems at DePaul University, for providing time and encouragement for the development of this edition and its predecessors.
I have received consistent support from the staff at Prentice Hall. Special thanks for their help go to George Lobell, executive editor; Gale Epps, editorial assistant; and Judith L. Winthrop, production editor.
R.J.
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
ProblemSolving Corner: Quantifiers
2 Proofs
2.1 Mathematical Systems, Direct Proofs, and Counterexamples
2.2 More Methods of Proof
ProblemSolving Corner: Proving Some Properties of Real Numbers
2.3 Resolution Proofs
2.4 Mathematical Induction
ProblemSolving Corner: Mathematical Induction
2.5 Strong Form of Induction and the WellOrdering Property Notes Chapter Review Chapter SelfTest Computer Exercises
3 Functions, Sequences, and Relations
3.1 Functions
ProblemSolving Corner: Functions
3.2 Sequences and Strings
3.3 Relations
3.4 Equivalence Relations
ProblemSolving 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
ProblemSolving 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
ProblemSolving Corner: Making Postage
5.4 The RSA PublicKey Cryptosystem
6 Counting Methods and the Pigeonhole Principle
6.1 Basic Principles
ProblemSolving Corner: Counting
6.2 Permutations and Combinations
ProblemSolving 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
ProblemSolving Corner: Recurrence Relations
7.3 Applications to the Analysis of Algorithms
8 Graph Theory
8.1 Introduction
8.2 Paths and Cycles
ProblemSolving Corner: Graphs
8.3 Hamiltonian Cycles and the Traveling Salesperson Problem
8.4 A ShortestPath 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
ProblemSolving 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
ProblemSolving Corner: Matching
11 Boolean Algebras and Combinatorial Circuits
11.1 Combinatorial Circuits
11.2 Properties of Combinatorial Circuits
11.3 Boolean Algebras
ProblemSolving Corner: Boolean Algebras
11.4 Boolean Functions and Synthesis of Circuits
11.5 Applications
12 Automata, Grammars, and Languages
12.1 Sequential Circuits and FiniteState Machines
12.2 FiniteState Automata
12.3 Languages and Grammars
12.4 Nondeterministic FiniteState Automata
12.5 Relationships Between Languages and Automata
13 Computational Geometry
13.1 The ClosestPair 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
Preface
PREFACE
This book is intended for a one or twoterm introductory course in discrete mathematics, based on my experience in teaching this course over a 20year period. Formal mathematics prerequisites are minimal; calculus is not required. There are no computer science prerequisites. The book includes examples, exercises, figures, tables, sections on problemsolving, section reviews, notes, chapter reviews, selftests, and computer exercises to help the reader master introductory discrete mathematics. In addition, an Instructor's Guide and World Wide Web site are available.
The main changes in this edition (discussed in more detail later) are an expanded discussion of logic and proofs, the addition of two sections on discrete probability, a new appendix that reviews basic algebra, many new examples and exercises, section reviews, and computer exercises.
OVERVIEW
In the early 1980s there were almost no books appropriate for an introductory course in discrete mathematics. At the same time, there was a need for a course that extended students' mathematical maturity and ability to deal with abstraction and also included useful topics such as combinatorics, algorithms, and graphs. The original edition of this book (1984) addressed this need. Subsequently, discrete mathematics courses were endorsed by many groups for several different audiences, including mathematics and computer science majors. A panel of the Mathematical Association of America (MAA) endorsed a yearlong course in discrete mathematics. The Educational Activities Board of the Institute of Electrical and Electronics Engineers (IEEE) recommended afreshmandiscrete mathematics course. The Association for Computing Machinery (ACM) and IEEE accreditation guidelines mandated a discrete mathematics course. This edition, like its predecessors, includes topics such as algorithms, combinatorics, sets, functions, and mathematical induction endorsed by these groups. It also addresses understanding and doing proofs and, generally, expanding mathematical maturity.
ABOUT THIS BOOK
This book includes
CHANGES FROM THE FOURTH EDITION
CHAPTER STRUCTURE
Each chapter is organized as follows:
— Overview
— Section
— Section Review
— Section Exercises
— Section
— Section Review
— Section Exercises
— Notes
— Chapter Review
— Chapter SelfTest
— Computer Exercises
Section reviews consist of exercises, with answers in the back of the book, that review the key concepts of the section. Notes contain suggestions for further reading. Chapter reviews provide reference lists of the key concepts of the chapters. Chapter selftests contain four exercises per section, with answers in the back of the book. Computer exercises request implementation of some of the algorithms, projects, and other programming related activities. In addition, most chapters have ProblemSolving Corners.
Exercises
The book contains over 3500 exercises, 135 of which are computer exercises. Exercises felt to be more challenging than average are indicated with a star. Exercise numbers in color (approximately onethird of the exercises) indicate that the exercise has a hint or solution in the back of the book. The solutions to the remaining exercises may be found in the Instructor's Guide. A handful of exercises are clearly identified as requiring calculus. No calculus concepts are used in the main body of the book and, except for these marked exercises, no calculus is needed to solve the exercises.
EXAMPLES
The book contains over 500 worked examples. These examples show students how to tackle problems in discrete mathematics, demonstrate applications of the theory, clarify proofs, and help motivate the material. Ends of examples are marked with a square symbol.
PROBLEMSOLVING CORNERS
The ProblemSolving Corner sections help students attack and solve problems and show them how to do proofs. Written in an informal style, each is a selfcontained section following the discussion of the subject of the problem. Rather than simply presenting a proof or a solution to a problem, in these sections the intent is to show alternative ways of attacking a problem, to discuss what to look for in trying to obtain a solution to a problem, and to present problemsolving and proof techniques.
Each ProblemSolving Corner begins with a statement of a problem. After stating the problem, ways to attack the problem are discussed. This discussion is followed by techniques for finding a solution. After a solution is found, a formal solution is given to show how to correctly write up a formal solution. Finally, the problemsolving techniques used in the section are summarized. In addition, some of these sections include a Comments subsection, which discusses connections with other topics in mathematics and computer science, provides motivation for the problem, and lists references for further reading about the problem. Exercises conclude some ProblemSolving Corners.
INSTRUCTOR SUPPLEMENT
An Instructor's Guide is available at no cost from the publisher to instructors who adopt or sample this book. The Instructor's Guide contains solutions to the exercises not included in the book, tips for teaching the course, and transparency masters.
WORLD WIDE WEB SITE
A World Wide Web site
www.prenhall.com/johnsonbaugh
contains
Both instructors and students will find the PowerPoint slides useful. The supplementary material includes the section on Petri nets from the fourth edition.
ACKNOWLEDGMENTS
I received helpful comments from many persons, including Gregory Bachelis, Gregory Brewster, Robert Busby, David G. Cantor, Tim Carroll, Joseph P Chan, HonWing Cheng, IPing Chu, Robert Crawford, Henry D'Angelo, Jerry Delazzer, Br. Michael Driscoll, Carl E. Eckberg, Susanna Epp, Gerald Gordon, Jerrold Grossman, Mark Herbster, Martin Kalin, Nicholas Krier, Warren Krueger, Glenn Lancaster, Donald E. G. Malm, Kevin Phelps, James H. Stoddard, Michael Sullivan, Edward J. Williams, and Hanyi Zhang.
Special thanks for this edition go to my colleague Andre Berthiaume for suggesting the logic game, for developing the PowerPoint slides, and, with Sigrid (Anne) Settle, for the pine cone used in Figure 3.4.1. I appreciate Example 4.5.22, suggested by my colleague Steve Jost, and Exercise 24, Section 9.3, suggested by Reino Hakala, Governors State University. Credit goes to my students Jenni Piane and Nick Meshes for C++ code to implement the tromino tiling algorithm (Algorithm 3.4.4). I am grateful to Herbert Enderton, UCLA, for pointing out the problem with the fourth edition's definition of "bipartite graph." My colleague Gary Andrus, made several suggestions that improved Chapters 9 and 10. Thanks also to all of the users of my book for their helpful letters and email. Finally, for reviewing the manuscript for this edition, thanks go to Kendall Atkinson, University of Iowa; Mansur Samadzadeh, Oklahoma State University; and Chaim Goodman Strauss, University of Arkansas.
I am indebted to Helmut Epp, Dean of the School of Computer Science, Telecommunications and Information Systems at DePaul University, for providing time and encouragement for the development of this edition and its predecessors.
I have received consistent support from the staff at Prentice Hall. Special thanks for their help go to George Lobell, executive editor; Gale Epps, editorial assistant; and Judith L. Winthrop, production editor.
R.J.