Preface to the Second Edition |
|
v | |
Preface to the First Edition |
|
vii | |
|
|
1 | (36) |
|
1.1 Statements, Propositions, and Theorems |
|
|
1 | (5) |
|
1.2 Logical Connectives and Truth Tables |
|
|
6 | (6) |
|
1.3 Conditional Statements |
|
|
12 | (6) |
|
1.4 Proofs: Structures and Strategies |
|
|
18 | (8) |
|
|
26 | (5) |
|
1.6 Application: A Brief Introduction to Switching Circuits |
|
|
31 | (6) |
|
|
37 | (72) |
|
|
37 | (8) |
|
|
45 | (1) |
|
|
46 | (7) |
|
|
53 | (5) |
|
2.5 Union, Intersection, and Complement |
|
|
58 | (5) |
|
|
63 | (8) |
|
|
71 | (4) |
|
2.8 Ordered Pairs and Cartesian Products |
|
|
75 | (7) |
|
2.9 Set Decomposition: Partitions and Relations |
|
|
82 | (15) |
|
2.10 Mathematical Induction and Recursion |
|
|
97 | (12) |
|
|
109 | (32) |
|
3.1 Definitions and Examples |
|
|
109 | (9) |
|
3.2 Surjections, Injections, Bijections, Sequences |
|
|
118 | (13) |
|
3.3 Composition of Functions |
|
|
131 | (10) |
|
4 Finite and Infinite Sets |
|
|
141 | (50) |
|
4.1 Cardinality; Fundamental Counting Principles |
|
|
141 | (17) |
|
4.2 Comparing Sets, Finite or Infinite |
|
|
158 | (7) |
|
4.3 Countable and Uncountable Sets |
|
|
165 | (10) |
|
|
175 | (1) |
|
4.5 Languages and Finite Automata |
|
|
176 | (15) |
|
|
191 | (86) |
|
5.1 Combinatorial Problems |
|
|
191 | (3) |
|
5.2 The Addition and Product Rules (review) |
|
|
194 | (2) |
|
5.3 Introduction to Permutations |
|
|
196 | (11) |
|
5.4 Permutations and Geometric Symmetry |
|
|
207 | (7) |
|
5.5 Decomposition into Cycles |
|
|
214 | (12) |
|
5.6 The Order of a Permutation; A Card-Shuffling Example |
|
|
226 | (7) |
|
5.7 Odd and Even Permutations; Applications to Configurations |
|
|
233 | (10) |
|
5.8 Binomial and Multinomial Coefficients |
|
|
243 | (18) |
|
|
261 | (16) |
|
|
277 | (72) |
|
|
278 | (6) |
|
6.2 The Integers: Operations and Order |
|
|
284 | (3) |
|
6.3 Divisibility: The Fundamental Theorem of Arithmetic |
|
|
287 | (15) |
|
6.4 Congruence; Divisibility Tests |
|
|
302 | (7) |
|
6.5 Introduction to Euler's Function |
|
|
309 | (6) |
|
6.6 The Inclusion-Exclusion Principle and Euler's Function |
|
|
315 | (7) |
|
6.7 More on Prime Numbers |
|
|
322 | (5) |
|
6.8 Primitive Roots and Card Shuffling |
|
|
327 | (9) |
|
6.9 Perfect Numbers, Mersenne Primes, Arithmetic Functions |
|
|
336 | (10) |
|
6.10 Number Theory and Cryptography: A Brief Glimpse |
|
|
346 | (3) |
|
|
349 | (26) |
|
|
349 | (13) |
|
7.2 The Gaussian Integers |
|
|
362 | (13) |
Hints and Partial Solutions to Selected Odd-Numbered Exercises |
|
375 | (20) |
Index |
|
395 | |