- ホーム
- > 洋書
- > 英文書
- > Science / Mathematics
基本説明
Features of the new edition include an increased use of combinatorial proofs, many new exercises, an extended discussion on elementary number theory, and more.
Full Description
A Trusted Guide to Discrete Mathematics with Proof?Now in a Newly Revised Edition 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 up-to-date 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 Boyer-Moore algorithm for pattern matching, Sierpinski curves, adaptive quadrature, the Josephus problem, and the five-color 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 non-standard 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.
Contents
Preface xiii
Acknowledgments xx
To The Student xxii
1 Introduction 1
1.1 What Is Discrete Mathematics? 1
1.1.1 A Break from the Past 3
1.2 The Stable Marriage Problem 3
1.2.1 Seeking a Solution 4
1.2.2 The Deferred Acceptance Algorithm 5
1.2.3 Some Concluding Comments 7
1.3 Other Examples 7
1.3.1 A Simple Counting and Probability Example 7
1.3.2 Sierpinski Curves 8
1.3.3 The Bridges of Konigsberg 9
1.3.4 Kirkman's Schoolgirls 9
1.3.5 Finite-State Machines 10
1.3.6 The Set of Rational Numbers Is Countably Infinite 11
1.4 Exercises 13
1.5 Chapter Review 15
1.5.1 Summary 15
1.5.2 Notation 15
2 Sets, Logic, and Boolean Algebras 17
2.1 Sets 19
2.1.1 Definitions and Notation 19
2.1.2 Exercises 26
2.1.3 Proofs about Sets 29
2.1.4 Exercises 33
2.2 Logic in Daily Life 34
2.2.1 General Guidelines for Analyzing Claims 34
2.2.2 Informal Fallacies 35
2.2.3 Everyday Logic versus Symbolic Logic 37
2.2.4 Exercises 37
2.3 Propositional Logic 38
2.3.1 Truth Tables 39
2.3.2 The Operators NOT, AND, OR, and XOR 39
2.3.3 Negations of AND, OR, and NOT 40
2.3.4 Exercises 42
2.3.5 Implication and the Biconditional 43
2.3.6 Operator Precedence 46
2.3.7 Logical Equivalence 46
2.3.8 Derived Implications 47
2.3.9 Exercises 48
2.4 Logical Equivalence and Rules of Inference 50
2.4.1 Important Logical Equivalences and Rules of Inference 53
2.4.2 Proving that a Statement is a Tautology 54
2.4.3 Exercises 56
2.5 Boolean Algebras 58
2.5.1 Sets and Propositions as Boolean Algebras 60
2.5.2 Proving Additional Boolean Algebra Properties 63
2.5.3 Exercises 67
2.6 Predicate Logic 68
2.6.1 Quantifiers 69
2.6.2 Exercises 74
2.7 Quick Check Solutions 76
2.8 Chapter Review 81
2.8.1 Summary 81
2.8.2 Notation 82
2.8.3 Fundamental Properties 83
2.8.4 Additional Review Material 84
3 Proof 85
3.1 Introduction to Mathematical Proof 85
3.1.1 Mathematics and Proof: The Big Picture 86
3.1.2 Mathematical Objects Related to Proofs 87
3.1.3 Exercises 91
3.2 Elementary Number Theory: Fuel for Practice 92
3.2.1 The Integers and Other Number Systems 92
3.2.2 Divisibility 93
3.2.3 Primes 95
3.2.4 The Well-Ordering Principle 96
3.2.5 Congruence, Factorials, Floor and Ceiling Functions 98
3.2.6 Exercises 99
3.3 Proof Strategies 100
3.3.1 Trivial Proof 100
3.3.2 Direct Proof 101
3.3.3 Indirect Proof: Proving the Contrapositive 103
3.3.4 Proof by Contradiction 103
3.3.5 Proof by Cases 105
3.3.6 Implications with Existential Quantifiers 105
3.3.7 Implications with Universal Quantifiers 106
3.3.8 Proofs Involving the Biconditional and Logical Equivalence 108
3.3.9 Some Important Examples 109
3.3.10 Exercises 111
3.4 Applications of Elementary Number Theory 113
3.4.1 The Euclidean Algorithm: Calculating gcd(a, b) 113
3.4.2 Hashing 116
3.4.3 Pseudorandom Numbers 117
3.4.4 Linear Congruence and the Chinese Remainder Theorem 119
3.4.5 Fermat's Little Theorem and Fermat's Last Theorem 124
3.4.6 Encryption 126
3.4.7 Exercises 130
3.5 Mathematical Induction 132
3.5.1 The Principle of Mathematical Induction 132
3.5.2 Complete Induction 139
3.5.3 Interesting Mathematical Induction Problems 141
3.5.4 The Well-Ordering Principle, Mathematical Induction, and Complete Induction 146
3.5.5 Multidimensional Induction 148
3.5.6 Exercises 151
3.6 Creating Proofs: Hints and Suggestions 153
3.6.1 A Few Very General Suggestions 153
3.6.2 Some Specific Tactics 156
3.6.3 Exercises 161
3.7 Quick Check Solutions 162
3.8 Chapter Review 167
3.8.1 Summary 167
3.8.2 Notation 168
3.8.3 Additional Review Material 168
4 Algorithms 169
4.1 Expressing Algorithms 170
4.1.1 Flow of Control 170
4.1.2 Flow of Information 176
4.1.3 Exercises 179
4.2 Measuring Algorithm Efficiency 180
4.2.1 Big-2 and Its Cousins 181
4.2.2 Practical Big-2 Tools 185
4.2.3 Exercises 193
4.2.4 Big-2 in Action: Searching a List 195
4.2.5 Exercises 200
4.3 Pattern Matching 202
4.3.1 The Obvious Algorithm 202
4.3.2 KMP: Knuth-Morris-Pratt 204
4.3.3 BM: Boyer-Moore 206
4.3.4 Exercises 213
4.4 The Halting Problem 214
4.4.1 Setting the Stage 214
4.4.2 The Halting Problem 215
4.5 Quick Check Solutions 217
4.6 Chapter Review 222
4.6.1 Summary 222
4.6.2 Notation 223
4.6.3 Big-2 Shortcuts 224
4.6.4 Additional Review Material 224
5 Counting 225
5.1 Permutations and Combinations 226
5.1.1 Two Basic Counting Principles 226
5.1.2 Permutations 229
5.1.3 Permutations with Repetition 231
5.1.4 Combinations 231
5.1.5 Combinations with Repetition 234
5.1.6 Exercises 237
5.1.7 More Complex Counting Problems 239
5.1.8 Exercises 246
5.2 Combinatorial Proofs 248
5.2.1 Introduction to Combinatorial Proofs 248
5.2.2 Counting Tulips: Three Combinatorial Proofs 251
5.2.3 Exercises 257
5.3 Pigeon-Hole Principle; Inclusion-Exclusion 258
5.3.1 The Pigeon-Hole Principle 258
5.3.2 Inclusion-Exclusion 261
5.3.3 Exercises 264
5.4 Quick Check Solutions 266
5.5 Chapter Review 270
5.5.1 Summary 270
5.5.2 Notation 271
5.5.3 Some Counting Formulas 272
5.5.4 Additional Review Material 272
6 Finite Probability Theory 273
6.1 The Language of Probabilities 274
6.1.1 Sample Spaces, Outcomes, and Events 274
6.1.2 Probabilities of Events 277
6.1.3 Exercises 281
6.2 Conditional Probabilities and Independent Events 283
6.2.1 Definitions 283
6.2.2 Computing Probabilities 287
6.2.3 Exercises 294
6.3 Counting and Probability 297
6.3.1 Exercises 299
6.4 Expected Value 302
6.4.1 Exercises 308
6.5 The Binomial Distribution 310
6.5.1 Exercises 315
6.6 Bayes's Theorem 316
6.6.1 Exercises 319
6.7 Quick Check Solutions 322
6.8 Chapter Review 327
6.8.1 Summary 327
6.8.2 Notation 328
6.8.3 Additional Review Material 328
7 Recursion 329
7.1 Recursive Algorithms 332
7.1.1 General Guidelines for Creating Recursive Algorithms 333
7.1.2 A Detailed Example 334
7.1.3 When Should Recursion Be Avoided? 336
7.1.4 Persian Rugs 339
7.1.5 Drawing Sierpinski Curves 342
7.1.6 Adaptive Quadrature 345
7.1.7 Exercises 349
7.2 Recurrence Relations 350
7.2.1 Solving Recurrence Relations 353
7.2.2 Linear Homogeneous Recurrence Relations with Constant Coefficients 357
7.2.3 Repeated Roots 366
7.2.4 The Sordid Truth 373
7.2.5 Exercises 375
7.3 Big-2 and Recursive Algorithms: The Master Theorem 377
7.3.1 Exercises 389
7.4 Generating Functions 391
7.4.1 Exercises 401
7.5 The Josephus Problem 402
7.5.1 Exercises 407
7.6 Quick Check Solutions 407
7.7 Chapter Review 414
7.7.1 Summary 414
7.7.2 Notation 416
7.7.3 Generating Function Table 416
7.7.4 Additional Review Material 416
8 Combinatorics 417
8.1 Partitions, Occupancy Problems, Stirling Numbers 419
8.1.1 Partitions of a Positive Integer 419
8.1.2 Occupancy Problems 423
8.1.3 Stirling Numbers 427
8.1.4 Exercises 433
8.2 Latin Squares, Finite Projective Planes 435
8.2.1 Latin Squares 435
8.2.2 Finite Projective Planes 442
8.2.3 Finite Projective Planes and Latin Squares 447
8.2.4 Exercises 457
8.3 Balanced Incomplete Block Designs 460
8.3.1 Constructing Balanced Incomplete Block Designs 464
8.3.2 Exercises 471
8.4 The Knapsack Problem 472
8.4.1 Exercises 485
8.5 Error-Correcting Codes 488
8.5.1 The 7-Bit Hamming Code 489
8.5.2 A Formal Look at Coding Theory 492
8.5.3 Combinatorial Aspects of Coding Theory 497
8.5.4 Exercises 500
8.6 Distinct Representatives, Ramsey Numbers 502
8.6.1 Systems of Distinct Representatives 502
8.6.2 Ramsey Numbers 509
8.6.3 Exercises 516
8.7 Quick Check Solutions 518
8.8 Chapter Review 529
8.8.1 Summary 529
8.8.2 Notation 531
8.8.3 The Fano Plane 532
8.8.4 Occupancy Problems 532
8.8.5 Additional Review Material 532
9 Formal Models in Computer Science 533
9.1 Information 533
9.1.1 A General Model of Communication 534
9.1.2 A Mathematical Definition of Information 535
9.1.3 A Summary of Other Ideas in Shannon's Paper 540
9.1.4 Exercises 541
9.2 Finite-State Machines 542
9.2.1 Finite Automata 543
9.2.2 Finite-State Machines with Output 547
9.2.3 Exercises 551
9.3 Formal Languages 553
9.3.1 Regular Grammars 554
9.3.2 Exercises 559
9.4 Regular Expressions 560
9.4.1 Introduction to Regular Expressions 560
9.4.2 Perl Extensions 566
9.4.3 Exercises 568
9.5 The Three Faces of Regular 569
9.5.1 Optional: Completing the Proof of Kleene's Theorem 576
9.5.2 Exercises 582
9.6 A Glimpse at More Advanced Topics 584
9.6.1 Context-Free Languages and Grammars 584
9.6.2 Turing Machines 585
9.6.3 Exercises 590
9.7 Quick Check Solutions 591
9.8 Chapter Review 596
9.8.1 Summary 596
9.8.2 Notation 597
9.8.3 Additional Review Material 598
10 Graphs 599
10.1 Terminology 600
10.1.1 New Graphs from Old 603
10.1.2 Special Graph Families 605
10.1.3 Exercises 608
10.2 Connectivity and Adjacency 609
10.2.1 Connectivity 609
10.2.2 The Adjacency Matrix 613
10.2.3 Exercises 615
10.3 Euler and Hamilton 618
10.3.1 Euler Circuits and Euler Trails 618
10.3.2 Hamilton Cycles and Hamilton Paths 620
10.3.3 Exercises 624
10.4 Representation and Isomorphism 626
10.4.1 Representation 626
10.4.2 Isomorphism 629
10.4.3 Exercises 631
10.5 The Big Theorems: Planarity, Euler, Polyhedra, Chromatic Number 634
10.5.1 Planarity 634
10.5.2 The Regular Polyhedra 639
10.5.3 Chromatic Number 642
10.5.4 Exercises 648
10.6 Directed Graphs and Weighted Graphs 651
10.6.1 Directed Graphs 651
10.6.2 Weighted Graphs and Shortest Paths 655
10.6.3 Exercises 662
10.7 Quick Check Solutions 665
10.8 Chapter Review 670
10.8.1 Summary 670
10.8.2 Notation 671
10.8.3 Additional Review Material 671
11 Trees 673
11.1 Terminology, Counting 673
11.1.1 Exercises 680
11.2 Traversal, Searching, and Sorting 682
11.2.1 Traversing Binary Trees 682
11.2.2 Binary Search Trees 685
11.2.3 Sorting 689
11.2.4 Exercises 690
11.3 More Applications of Trees 692
11.3.1 Parse Trees 692
11.3.2 Huffman Compression 694
11.3.3 XML 699
11.3.4 Exercises 708
11.4 Spanning Trees 711
11.4.1 Spanning Trees in Unweighted Graphs 711
11.4.2 Minimal Spanning Trees in Weighted Graphs 717
11.4.3 Exercises 722
11.5 Quick Check Solutions 726
11.6 Chapter Review 729
11.6.1 Summary 729
11.6.2 Notation 729
11.6.3 Additional Review Material 730
12 Functions, Relations, Databases, and Circuits 731
12.1 Functions and Relations 731
12.1.1 Functions 731
12.1.2 Relations 735
12.1.3 Exercises 737
12.2 Equivalence Relations, Partially Ordered Sets 739
12.2.1 Properties that Characterize Relations 739
12.2.2 Equivalence Relations and Partitions 742
12.2.3 Exercises 746
12.3 n-ary Relations and Relational Databases 748
12.3.1 n-ary Relations 748
12.3.2 Relational Databases 749
12.3.3 Functional Dependence; Models and Instances 751
12.3.4 Keys; Operations on Relations 752
12.3.5 Normal Forms 757
12.3.6 Exercises 769
12.4 Boolean Functions and Boolean Expressions 772
12.4.1 Boolean Functions 773
12.4.2 Binary Functions and Disjunctive Normal Form 775
12.4.3 Binary Expressions and Disjunctive Normal Form 778
12.4.4 Exercises 784
12.5 Combinatorial Circuits 785
12.5.1 Minimizing Binary Expressions 785
12.5.2 Combinatorial Circuits and Binary Expressions 789
12.5.3 Functional Completeness 793
12.5.4 Exercises 795
12.6 Quick Check Solutions 797
12.7 Chapter Review 805
12.7.1 Summary 805
12.7.2 Notation 806
12.7.3 Additional Review Material 806
A Number Systems A1
A.1 The Natural Numbers A1
A.2 The Integers A2
A.3 The Rational Numbers A2
A.4 The Real Numbers A4
A.5 The Complex Numbers A4
A.6 Other Number Systems A6
A.7 Representation of Numbers A7
B Summation Notation A10
C Logic Puzzles and Analyzing Claims A12
C.1 Logic Puzzles A12
C.1.1 Logic Puzzles about AND, OR, and NOT A12
C.1.2 Logic Puzzles about Implication, Biconditional, and Equivalence A16
C.1.3 Exercises A18
C.2 Analyzing Claims A18
C.2.1 Analyzing Claims that Contain Implications A18
C.2.2 Analyzing Claims that Contain Quantifiers A22
C.2.3 Exercises A23
C.3 Quick Check Solutions A24
D The Golden Ratio A27
E Matrices A29
F The Greek Alphabet A33
G Writing Mathematics A34
H Solutions to Selected Exercises A36
H.1 Introduction A36
H.2 Sets, Logic, and Boolean Algebras A36
H.3 Proof A42
H.4 Algorithms A47
H.5 Counting A51
H.6 Finite Probability Theory A54
H.7 Recursion A59
H.8 Combinatorics A63
H.9 Formal Models in Computer Science A68
H.10 Graphs A71
H.11 Trees A75
H.12 Functions, Relations, Databases, and Circuits A78
H.13 Appendices A83
Bibliography A85
Index A90
