You are here

Home » Discrete Mathematics with Proof

Discrete Mathematics with Proof

Eric Gossett
Publisher: 
John Wiley
Publication Date: 
2010
Number of Pages: 
806
Format: 
Hardcover
Price: 
130.00
ISBN: 
9780470457931
Category: 
Textbook
[Reviewed by
Miklós Bóna
, on
06/6/2010
]

This is a well-written, comprehensive textbook with a lot of information, good examples and plenty of exercises. This reviewer, an enumerative combinatorialist, finds the organization of chapters rather odd, but it is plausible that some instructors prefer to teach in this way.

The book starts with two long and technical chapters on sets, Boolean logic, and various proof techniques. This is appropriate for those students who never had a class on this, but in programs where a separate course on Transition into Advanced Mathematics is required, these two chapters can safely be omitted.

Then there is a chapter on Algorithms. This contains pattern matching, and the Halting problem. This reviewer thinks that it might be too early in the semester for the advanced ideas related to the Halting problem, but that is a judgement call.

The next four chapters consist of material that is, in many programs, taught in a combinatorics course. The chapters are, Counting, Finite Probability, Recursion, and, by a strange choice of a title, “Combinatorics.” The latter chapter discusses design theory, error correcting codes, Ramsey numbers, integer partitions and set partitions. This is certainly combinatorics, but so are the topics discussed in the previous three chapters, and also graphs, trees, partially ordered sets, hypergraphs, generating functions, magic squares, permutations, and countless other areas. Choosing a small subset of them and calling it combinatorics is as though someone wrote a book on Paris and called it Western Europe.

Then there is a chapter on formal models of computer science, stopping at Turing machines, and not mentioning complexity classes like P and NP. Perhaps the P versus NP question could have been included; at least it always fascinates the students of this reviewer.

After this, there are very thorough chapters on Graphs and Trees, and a last chapter on Functions, Relations, Databases and Circuits. Again, it struck me as strange to see functions and relations being discussed in the last chapter of a book of this high level. It would seem more natural to discuss them at the beginning, where sets and logic are discussed.

To summarize, if you like the above organization of topics, then this book is definitely for you. The individual chapters are reader-friendly and well supported by examples and exercises. If you do not like the way the parts are put together, you may still want to use the book as a source of examples and exercises for your course.

Miklós Bóna is Professor of Mathematics at the University of Florida.

Preface.

Acknowledgments.

To The Student.

1 Introduction.

1.1 What Is Discrete Mathematics?

1.2 The Stable Marriage Problem.

1.3 Other Examples.

1.4 Exercises.

1.5 Chapter Review.

2 Sets, Logic, and Boolean Algebras.

2.1 Sets.

2.2 Logic in Daily Life.

2.3 Propositional Logic.

2.4 Logical Equivalence and Rules of Inference.

2.5 Boolean Algebras.

2.6 Predicate Logic.

2.7 Quick Check Solutions.

2.8 Chapter Review.

3 Proof.

3.1 Introduction to Mathematical Proof.

3.2 Elementary Number Theory: Fuel for Practice.

3.3 Proof Strategies.

3.4 Applications of Elementary Number Theory.

3.5 Mathematical Induction.

3.6 Creating Proofs: Hints and Suggestions.

3.7 Quick Check Solutions.

3.8 Chapter Review.

4 Algorithms.

4.1 Expressing Algorithms.

4.2 Measuring Algorithm Efficiency.

4.3 Pattern Matching.

4.4 The Halting Problem.

4.5 Quick Check Solutions.

4.6 Chapter Review.

5 Counting.

5.1 Permutations and Combinations.

5.2 Combinatorial Proofs.

5.3 Pigeon-Hole Principle; Inclusion-Exclusion.

5.4 Quick Check Solutions.

5.5 Chapter Review.

6 Finite Probability Theory.

6.1 The Language of Probabilities.

6.2 Conditional Probabilities and Independent Events.

6.3 Counting and Probability.

6.4 Expected Value.

6.5 The Binomial Distribution.

6.6 Bayes’s Theorem.

6.7 Quick Check Solutions.

7 Recursion.

7.1 Recursive Algorithms.

7.2 Recurrence Relations.

7.3 Big-Θ and Recursive Algorithms: The Master Theorem.

7.4 Generating Functions.

7.5 The Josephus Problem.

7.6 Quick Check Solutions.

7.7 Chapter Review.

8 Combinatorics.

8.1 Partitions, Occupancy Problems, Stirling Numbers.

8.2 Latin Squares; Finite Projective Planes.

8.3 Balanced Incomplete Block Designs.

8.4 The Knapsack Problem.

8.5 Error-Correcting Codes.

8.6 Distinct Representatives, Ramsey Numbers.

8.7 Quick Check Solutions.

8.8 Chapter Review.

9 Formal Models in Computer Science.

9.1 Information.

9.2 Finite-State Machines.

9.3 Formal Languages.

9.4 Regular Expressions.

9.5 The Three Faces of Regular.

9.6 A Glimpse at More Advanced Topics.

9.7 Quick Check Solutions.

9.8 Chapter Review.

10. Graphs.

10.1 Terminology.

10.2 Connectivity and Adjacency.

10.3 Euler and Hamilton.

10.4 Representation and Isomorphism.

10.5 The Big Theorems: Planarity, Euler, Polyhedra, Chromatic Number.

10.6 Directed Graphs and Weighted Graphs.

10.7 Quick Check Solutions.

10.8 Chapter Review.

11 Trees.

11.1 Terminology, Counting.

11.2 Traversal, Searching, and Sorting.

11.3 More Applications of Trees.

11.4 Spanning Trees.

11.5 Quick Check Solutions.

11.6 Chapter Review.

12 Functions, Relations, Databases, and Circuits.

12.1 Functions and Relations.

12.2 Equivalence Relations, Partially Ordered Sets.

12.3 n-ary Relations and Relational Databases.

12.4 Boolean Functions and Boolean Expressions.

12.5 Combinatorial Circuits.

12.6 Quick Check Solutions.

12.7 Chapter Review.

A. Number Systems.

A.1 The Natural Numbers.

A.2 The Integers.

A.3 The Rational Numbers.

A.4 The Real Numbers.

A.5 The Complex Numbers.

A.6 Other Number Systems.

A.7 Representation of Numbers.

B. Summation Notation.

C. Logic Puzzles and Analyzing Claims.

C.1 Logic Puzzles.

C.2 Analyzing Claims.

C.3 Quick Check Solutions.

D. The Golden Ratio.

E. Matrices.

F. The Greek Alphabet.

G. Writing Mathematics.

H. Solutions to Selected Exercises.

H.1 Introduction.

H.2 Sets, Logic, and Boolean Algebras.

H.3 Proof.

H.4 Algorithms.

H.5 Counting.

H.6 Finite Probability Theory.

H.7 Recursion.

H.8 Combinatorics.

H.9 Formal Models in Computer Science.

H.10 Graphs.

H.11 Trees.

H.12 Functions, Relations, Databases, and Circuits.

H.13 Appendices.

Bibliography.

Index.

Tags: 
Discrete Mathematics
Transition to Advanced Mathematics