Preface |
|
ix | |
|
|
1 | (42) |
|
|
3 | (3) |
|
1.2 Naming and Describing Sets |
|
|
6 | (4) |
|
1.3 Comparison Relations on Sets |
|
|
10 | (4) |
|
|
14 | (14) |
|
1.5 Principle of Inclusion/Exclusion |
|
|
28 | (6) |
|
|
34 | (9) |
|
2 Patterns: Sequences, Summations, Mathematical Induction |
|
|
43 | (32) |
|
|
44 | (2) |
|
2.2 Describing Patterns in Sequences |
|
|
46 | (10) |
|
|
56 | (4) |
|
2.4 Mathematical Induction |
|
|
60 | (12) |
|
2.4.1 First Principle of Mathematical Induction |
|
|
62 | (2) |
|
2.4.2 Examples Using Mathematical Induction |
|
|
64 | (8) |
|
|
72 | (3) |
|
|
75 | (46) |
|
|
76 | (32) |
|
|
78 | (5) |
|
3.1.2 Propositional Forms |
|
|
83 | (3) |
|
3.1.3 Parse Trees and the Operator Hierarchy (*) |
|
|
86 | (2) |
|
3.1.4 Truth Tables, Tautologies, and Contradictions |
|
|
88 | (4) |
|
3.1.5 Propositional Equivalences |
|
|
92 | (3) |
|
3.1.6 Propositional Identities |
|
|
95 | (2) |
|
|
97 | (3) |
|
3.1.8 Indirect Proofs (*) |
|
|
100 | (3) |
|
3.1.9 From English to Propositions |
|
|
103 | (2) |
|
3.1.10 Logic Circuits (*) |
|
|
105 | (3) |
|
|
108 | (7) |
|
|
110 | (2) |
|
3.2.2 Some Rules for Using Predicates |
|
|
112 | (3) |
|
|
115 | (6) |
|
|
121 | (28) |
|
4.1 Ways to Describe Relations Between Sets |
|
|
122 | (10) |
|
|
123 | (3) |
|
|
126 | (2) |
|
|
128 | (1) |
|
4.1.4 Using the Cartesian Product |
|
|
129 | (3) |
|
4.2 Properties of Relations |
|
|
132 | (10) |
|
|
132 | (3) |
|
|
135 | (4) |
|
|
139 | (3) |
|
|
142 | (3) |
|
|
145 | (4) |
|
|
149 | (48) |
|
|
151 | (5) |
|
5.2 Functions and Relations |
|
|
156 | (6) |
|
5.3 Properties of Functions |
|
|
162 | (4) |
|
|
166 | (5) |
|
5.5 Identity and Inverse Functions |
|
|
171 | (9) |
|
5.6 An Application: Cryptography |
|
|
180 | (3) |
|
|
181 | (1) |
|
5.6.2 Cryptography in Cyber-Commerce |
|
|
182 | (1) |
|
|
183 | (6) |
|
5.7.1 Standard Mathematical Functions |
|
|
183 | (1) |
|
|
184 | (2) |
|
5.7.3 Functions in Program Construction |
|
|
186 | (3) |
|
5.8 An Application: Secure Storage of Passwords |
|
|
189 | (2) |
|
|
191 | (6) |
|
|
197 | (26) |
|
6.1 Counting and How to Count |
|
|
198 | (2) |
|
6.2 Elementary Rules for Counting |
|
|
200 | (9) |
|
|
200 | (2) |
|
6.2.2 The Multiplication Rule |
|
|
202 | (5) |
|
6.2.3 Using the Elementary Rules Together |
|
|
207 | (2) |
|
6.3 Permutations and Combinations |
|
|
209 | (9) |
|
|
210 | (2) |
|
|
212 | (6) |
|
|
218 | (5) |
|
|
223 | (32) |
|
7.1 Terminology and Background |
|
|
224 | (4) |
|
|
228 | (2) |
|
7.3 Elementary Rules for Probability |
|
|
230 | (7) |
|
7.3.1 The Elementary Addition Rule |
|
|
232 | (2) |
|
7.3.2 The Elementary Multiplication Rule |
|
|
234 | (3) |
|
7.4 General Rules for Probability |
|
|
237 | (4) |
|
7.4.1 The General Addition Rule |
|
|
238 | (2) |
|
7.4.2 The General Multiplication |
|
|
240 | (1) |
|
7.5 Bernoulli Trials and Probability Distributions |
|
|
241 | (3) |
|
|
244 | (2) |
|
|
246 | (9) |
|
|
255 | (28) |
|
8.1 What is an Algorithm? |
|
|
255 | (2) |
|
8.2 Applications of Algorithms |
|
|
257 | (1) |
|
8.3 Searching and Sorting Algorithms |
|
|
258 | (9) |
|
|
258 | (4) |
|
|
262 | (5) |
|
8.4 Analysis of Algorithms |
|
|
267 | (11) |
|
8.4.1 How Do We Measure Efficiency? |
|
|
267 | (1) |
|
8.4.2 The Time Complexity of an Algorithm |
|
|
268 | (2) |
|
8.4.3 Analysis of Several Algorithms |
|
|
270 | (6) |
|
|
276 | (2) |
|
|
278 | (5) |
|
|
283 | (32) |
|
|
286 | (5) |
|
|
286 | (2) |
|
9.1.2 Directed and Undirected Graphs |
|
|
288 | (1) |
|
|
289 | (2) |
|
9.2 Euler Trails and Circuits |
|
|
291 | (4) |
|
9.2.1 Walks, Trails, Circuits and Cycles |
|
|
291 | (2) |
|
9.2.2 When Can We Find Euler Trails and Circuits? |
|
|
293 | (2) |
|
|
295 | (2) |
|
9.4 Minimum Spanning Tree |
|
|
297 | (3) |
|
|
298 | (1) |
|
9.4.2 Prim's Algorithm for the Minimum Spanning Tree |
|
|
299 | (1) |
|
9.5 Matrix Notation For Graphs |
|
|
300 | (9) |
|
|
309 | (6) |
Appendix A Our Social Networking Example |
|
315 | (6) |
Index |
|
321 | |