Textbook
Discrete Mathematics with Proof, 2nd EditionISBN: 9780470457931
928 pages
June 2009, ©2009

Description
Discrete mathematics has become increasingly popular in recent years due to its growing applications in the field of computer science. Discrete Mathematics with Proof, Second Edition continues to facilitate an uptodate understanding of this important topic, exposing readers to a wide range of modern and technological applications.
The book begins with an introductory chapter that provides an accessible explanation of discrete mathematics. Subsequent chapters explore additional related topics including counting, finite probability theory, recursion, formal models in computer science, graph theory, trees, the concepts of functions, and relations. Additional features of the Second Edition include:
 An intense focus on the formal settings of proofs and their techniques, such as constructive proofs, proof by contradiction, and combinatorial proofs
 New sections on applications of elementary number theory, multidimensional induction, counting tulips, and the binomial distribution
 Important examples from the field of computer science presented as applications including the Halting problem, Shannon's mathematical model of information, regular expressions, XML, and Normal Forms in relational databases
 Numerous examples that are not often found in books on discrete mathematics including the deferred acceptance algorithm, the BoyerMoore algorithm for pattern matching, Sierpinski curves, adaptive quadrature, the Josephus problem, and the fivecolor theorem
 Extensive appendices that outline supplemental material on analyzing claims and writing mathematics, along with solutions to selected chapter exercises
Combinatorics receives a full chapter treatment that extends beyond the combinations and permutations material by delving into nonstandard topics such as Latin squares, finite projective planes, balanced incomplete block designs, coding theory, partitions, occupancy problems, Stirling numbers, Ramsey numbers, and systems of distinct representatives. A related Web site features animations and visualizations of combinatorial proofs that assist readers with comprehension. In addition, approximately 500 examples and over 2,800 exercises are presented throughout the book to motivate ideas and illustrate the proofs and conclusions of theorems.
Assuming only a basic background in calculus, Discrete Mathematics with Proof, Second Edition is an excellent book for mathematics and computer science courses at the undergraduate level. It is also a valuable resource for professionals in various technical fields who would like an introduction to discrete mathematics.
Table of Contents
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 PigeonHole Principle; InclusionExclusion.
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 ErrorCorrecting 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 FiniteState 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 nary 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.
Author Information
New to This Edition

Features of the new edition include an increased use of combinatorial proofs, an extended discussion on elementary number theory

The numbering of definitions, theorems, propositions, corollaries, and lemmas has been merged. This should help the reader to locate them with less effort. The numbering sequence for examples and Quick Checks have remained as separate sequences.

Over 250 additional exercises or exercise subitems have been added (bringing the total to 3,500)

Supplemented with an Instructor’s Manual containing detailed solutions to every exercise (available upon request to the Publisher). Detailed solutions are also available in the back of the book for selected exercises.
The Wiley Advantage

Emphasizes proof (combinatorial and noncombinatorial) throughout in the text and exercises, and homework problems have been designed to reinforce the book's main concepts

Contains many examples that are not present in most discrete mathematics books, including the deferred acceptance algorithm, the BoyerMoore algorithm for pattern matching, Sierpinski curves, Persian rugs, adaptive quadrature, the Josephus problem, the five color theorem, and relational databases

Includes Quick Check problems at critical points in the reading, and it is intended for these problems to be solved before moving on to the next section in the chapter. Also, many worked examples can be found throughout, which are used to motivate the presented theorems and illustrate the conclusion of a theorem.

Features many important examples from the field of computer science, including the Halting problem, Shannon's mathematical model of information, XML, and Normal Forms in relational databases