Preface 

iii  

The Foundations: Logic and Proofs 


1  (46) 


1  (9) 

Propositional Equivalences 


10  (5) 

Predicates and Quantifiers 


15  (6) 


21  (9) 


30  (4) 


34  (4) 

Proof Methods and Strategy 


38  (9) 

Guide to Review Questions for Chapter 1 


42  (1) 

Supplementary Exercises for Chapter 1 


43  (2) 

Writing Projects for Chapter 1 


45  (2) 

Basic Structures: Sets, Functions, Sequences, and Sums 


47  (25) 


47  (3) 


50  (5) 


55  (8) 


63  (9) 

Guide to Review Questions for Chapter 2 


68  (1) 

Supplementary Exercises for Chapter 2 


69  (2) 

Writing Projects for Chapter 2 


71  (1) 

The Fundamentals: Algorithms, the Integers, and Matrices 


72  (48) 


72  (9) 


81  (5) 


86  (3) 

The Integers and Division 


89  (2) 

Primes and Greatest Common Divisors 


91  (4) 


95  (5) 

Applications of Number Theory 


100  (8) 


108  (12) 

Guide to Review Questions for Chapter 3 


112  (1) 

Supplementary Exercises for Chapter 3 


113  (5) 

Writing Projects for Chapter 3 


118  (2) 


120  (47) 


120  (12) 

Strong Induction and WellOrdering 


132  (6) 

Recursive Definitions and Structural Induction 


138  (9) 


147  (5) 


152  (15) 

Guide to Review Questions for Chapter 4 


154  (2) 

Supplementary Exercises for Chapter 4 


156  (10) 

Writing Projects for Chapter 4 


166  (1) 


167  (39) 


167  (8) 


175  (5) 

Permutations and Combinations 


180  (4) 


184  (5) 

Generalized Permutations and Combinations 


189  (7) 

Generating Permutations and Combinations 


196  (10) 

Guide to Review Questions for Chapter 5 


198  (1) 

Supplementary Exercises for Chapter 5 


199  (6) 

Writing Projects for Chapter 5 


205  (1) 


206  (22) 

An Introduction to Discrete Probability 


206  (3) 


209  (6) 


215  (2) 

Expected Value and Variance 


217  (11) 

Guide to Review Questions for Chapter 6 


222  (1) 

Supplementary Exercises for Chapter 6 


223  (4) 

Writing Projects for Chapter 6 


227  (1) 

Advanced Counting Techniques 


228  (52) 


228  (13) 

Solving Linear Recurrence Relations 


241  (10) 

DivideandConquer Algorithms and Recurrence Relations 


251  (4) 


255  (12) 


267  (2) 

Applications of InclusionExclusion 


269  (11) 

Guide to Review Questions for Chapter 7 


273  (1) 

Supplementary Exercises for Chapter 7 


274  (5) 

Writing Projects for Chapter 7 


279  (1) 


280  (40) 

Relations and Their Properties 


280  (8) 

nary Relations and Their Applications 


288  (2) 


290  (3) 


293  (4) 


297  (8) 


305  (15) 

Guide to Review Questions for Chapter 8 


313  (1) 

Supplementary Exercises for Chapter 8 


314  (5) 

Writing Projects for Chapter 8 


319  (1) 


320  (47) 


320  (3) 

Graph Terminology and Special Types of Graphs 


323  (6) 

Representing Graphs and Graph Isomorphism 


329  (7) 


336  (6) 


342  (5) 


347  (4) 


351  (4) 


355  (12) 

Guide to Review Questions for Chapter 9 


359  (1) 

Supplementary Exercises for Chapter 9 


360  (5) 

Writing Projects for Chapter 9 


365  (2) 


367  (32) 


367  (5) 


372  (9) 


381  (4) 


385  (5) 


390  (9) 

Guide to Review Questions for Chapter 10 


393  (1) 

Supplementary Exercises for Chapter 10 


394  (3) 

Writing Projects for Chapter 10 


397  (2) 


399  (21) 


399  (4) 

Representing Boolean Functions 


403  (2) 


405  (3) 


408  (12) 

Guide to Review Questions for Chapter 11 


416  (1) 

Supplementary Exercises for Chapter 11 


417  (2) 

Writing Projects for Chapter 11 


419  (1) 


420  (32) 


420  (7) 

FiniteState Machines with Output 


427  (5) 

FiniteState Machines with No Output 


432  (5) 


437  (4) 


441  (11) 

Guide to Review Questions for Chapter 12 


445  (1) 

Supplementary Exercises for Chapter 12 


446  (4) 

Writing Projects for Chapter 12 


450  (2) 


452  (3) 

Appendix 1 Axioms for the Real Numbers and the Positive Integers 


452  (2) 

Appendix 2 Exponential and Logarithmic Functions 


454  (1) 


454  (1) 


455  (11) 

References and Advice on Writing Projects 


466  (8) 

Sample Chapter Tests with Solutions 


474  (28) 

Common Mistakes in Discrete Mathematics 


502  (10) 

Solving Problems in Discrete Mathematics 


502  (1) 


503  (9) 


512  