Fundamentals | p. 1 |

Definition | p. 1 |

Recap | p. 4 |

Exercises | p. 4 |

Theorem | p. 7 |

The Nature of Truth | p. 7 |

If-Then | p. 9 |

If and Only If | p. 11 |

And, Or, and Not | p. 12 |

What Theorems Are Called | p. 13 |

Vacuous Truth | p. 13 |

Recap | p. 14 |

Exercises | p. 14 |

Proof | p. 15 |

Proving If-and-Only-If Theorems | p. 19 |

Recap | p. 22 |

Exercises | p. 22 |

Counterexample | p. 22 |

Recap | p. 24 |

Exercises | p. 24 |

Boolean Algebra | p. 25 |

More Operations | p. 28 |

Recap | p. 29 |

Exercises | p. 29 |

Collections | p. 33 |

Lists | p. 33 |

Counting Two-Element Lists | p. 34 |

Longer Lists | p. 36 |

Recap | p. 40 |

Exercises | p. 40 |

Factorial | p. 41 |

Much Ado about 0! | p. 42 |

Product Notation | p. 43 |

Recap | p. 44 |

Exercises | p. 44 |

Sets I: Introduction, Subsets | p. 46 |

Relationships Between Sets | p. 47 |

Counting Subsets | p. 49 |

Power Set | p. 50 |

Recap | p. 51 |

Exercises | p. 51 |

Quantifiers | p. 52 |

There Is | p. 52 |

For All | p. 53 |

Negating Quantified Statements | p. 54 |

Combining Quantifiers | p. 55 |

Recap | p. 56 |

Exercises | p. 56 |

Sets II: Operations | p. 58 |

Union and Intersection | p. 58 |

The Size of a Union | p. 60 |

Difference and Symmetric Difference | p. 63 |

Cartesian Product | p. 67 |

Recap | p. 68 |

Exercises | p. 68 |

Counting and Relations | p. 72 |

Relations | p. 72 |

Properties of Relations | p. 75 |

Recap | p. 76 |

Exercises | p. 76 |

Equivalence Relations | p. 78 |

Equivalence Classes | p. 82 |

Recap | p. 85 |

Exercises | p. 85 |

Partitions | p. 87 |

Counting Classes/Parts | p. 90 |

Recap | p. 93 |

Exercises | p. 93 |

Binomial Coefficients | p. 94 |

Calculating (n k) | p. 98 |

Pascal's Triangle | p. 100 |

A Formula for (n k) | p. 102 |

Recap | p. 104 |

Exercises | p. 104 |

Counting Multisets | p. 108 |

Multisets | p. 109 |

Formulas for ((n k)) | p. 110 |

Recap | p. 114 |

Exercises | p. 114 |

Inclusion-Exclusion | p. 116 |

How to Use Inclusion-Exclusion | p. 119 |

Derangements | p. 121 |

A Ghastly Formula | p. 124 |

Recap | p. 124 |

Exercises | p. 124 |

More Proof | p. 126 |

Contradiction | p. 126 |

Proof by Contrapositive | p. 126 |

Reductio ad Absurdum | p. 128 |

A Matter of Style | p. 132 |

Recap | p. 132 |

Exercises | p. 132 |

Smallest Counterexample | p. 133 |

Well-Ordering | p. 139 |

Recap | p. 145 |

Exercises | p. 145 |

And Finally | p. 146 |

Induction | p. 146 |

Strong Induction | p. 149 |

A More Complicated Example | p. 151 |

Recap | p. 154 |

Exercises | p. 154 |

A Matter of Style | p. 157 |

Functions | p. 158 |

Functions | p. 158 |

Domain and Image | p. 160 |

Pictures of Functions | p. 161 |

Counting Functions | p. 162 |

Inverse Functions | p. 163 |

Counting Functions, Again | p. 167 |

Recap | p. 169 |

Exercises | p. 169 |

The Pigeonhole Principle | p. 171 |

Cantor's Theorem | p. 174 |

Recap | p. 176 |

Exercises | p. 176 |

Composition | p. 177 |

Identity Function | p. 180 |

Recap | p. 181 |

Exercises | p. 181 |

Permutations | p. 183 |

Cycle Notation | p. 184 |

Calculations with Permutations | p. 187 |

Transpositions | p. 188 |

Recap | p. 193 |

Exercises | p. 194 |

Symmetry | p. 196 |

Symmetries of a Square | p. 196 |

Symmetries as Permutations | p. 198 |

Combining Symmetries | p. 198 |

Formal Definition of Symmetry | p. 200 |

Recap | p. 201 |

Exercises | p. 201 |

Assorted Notation | p. 202 |

Big Oh | p. 202 |

[Omega] and [Theta] | p. 205 |

Little Oh | p. 206 |

Floor and Ceiling | p. 207 |

Recap | p. 208 |

Exercises | p. 208 |

Probability | p. 209 |

Sample Space | p. 209 |

Recap | p. 212 |

Exercises | p. 212 |

Events | p. 213 |

Combining Events | p. 216 |

The Birthday Problem | p. 218 |

Recap | p. 219 |

Exercises | p. 219 |

Conditional Probability and Independence | p. 221 |

Independence | p. 223 |

Independent Repeated Trials | p. 226 |

The Monty Hall Problem | p. 227 |

Recap | p. 228 |

Exercises | p. 228 |

Random Variables | p. 231 |

Random Variables as Events | p. 232 |

Independent Random Variables | p. 234 |

Recap | p. 235 |

Exercises | p. 235 |

Expectation | p. 236 |

Linearity of Expectation | p. 241 |

Product of Random Variables | p. 245 |

Expected Value as a Measure of Centrality | p. 248 |

Variance | p. 249 |

Recap | p. 252 |

Exercises | p. 253 |

Number Theory | p. 255 |

Dividing | p. 255 |

Div and Mod | p. 258 |

Recap | p. 259 |

Exercises | p. 259 |

Greatest Common Divisor | p. 260 |

Calculating the gcd | p. 261 |

Correctness | p. 263 |

How Fast? | p. 264 |

An Important Theorem | p. 266 |

Recap | p. 269 |

Exercises | p. 269 |

Modular Arithmetic | p. 271 |

A New Context for Basic Operations | p. 271 |

Modular Addition and Multiplication | p. 272 |

Modular Subtraction | p. 274 |

Modular Division | p. 275 |

A Note on Notation | p. 280 |

Recap | p. 280 |

Exercises | p. 281 |

The Chinese Remainder Theorem | p. 283 |

Solving One Equation | p. 283 |

Solving Two Equations | p. 285 |

Recap | p. 287 |

Exercises | p. 287 |

Factoring | p. 288 |

Infinitely Many Primes | p. 290 |

A Formula for Greatest Common Divisor | p. 291 |

Irrationality of [square root]2 | p. 292 |

Recap | p. 294 |

Exercises | p. 294 |

Algebra | p. 299 |

Groups | p. 299 |

Operations | p. 299 |

Properties of Operations | p. 300 |

Groups | p. 302 |

Examples | p. 304 |

Recap | p. 308 |

Exercises | p. 308 |

Group Isomorphism | p. 310 |

The Same? | p. 310 |

Cyclic Groups | p. 312 |

Recap | p. 315 |

Exercises | p. 315 |

Subgroups | p. 316 |

LaGrange's Theorem | p. 319 |

Recap | p. 323 |

Exercises | p. 323 |

Fermat's Little Theorem | p. 325 |

First Proof | p. 326 |

Second Proof | p. 327 |

Third Proof | p. 330 |

Euler's Theorem | p. 331 |

Primality Testing | p. 332 |

Recap | p. 333 |

Exercises | p. 333 |

Public-Key Cryptography I: Introduction | p. 334 |

The Problem: Private Communication in Public | p. 334 |

Factoring | p. 334 |

Words to Numbers | p. 335 |

Cryptography and the Law | p. 337 |

Recap | p. 337 |

Exercises | p. 337 |

Public-Key Cryptography II: Rabin's Method | p. 337 |

Square Roots Modulo n | p. 338 |

The Encryption and Decryption Procedures | p. 343 |

Recap | p. 343 |

Exercises | p. 343 |

Public-Key Cryptography III: RSA | p. 345 |

The RSA Encryption and Decryption Functions | p. 345 |

Security | p. 347 |

Recap | p. 349 |

Exercises | p. 349 |

Graphs | p. 351 |

Graph Theory Fundamentals | p. 351 |

Map Coloring | p. 351 |

Three Utilities | p. 353 |

Seven Bridges | p. 353 |

What Is a Graph? | p. 354 |

Adjacency | p. 355 |

A Matter of Degree | p. 357 |

Further Notation and Vocabulary | p. 359 |

Recap | p. 359 |

Exercises | p. 360 |

Subgraphs | p. 362 |

Induced and Spanning Subgraphs | p. 362 |

Cliques and Independent Sets | p. 365 |

Complements | p. 366 |

Recap | p. 367 |

Exercises | p. 368 |

Connection | p. 369 |

Walks | p. 369 |

Paths | p. 370 |

Disconnection | p. 374 |

Recap | p. 375 |

Exercises | p. 375 |

Trees | p. 377 |

Cycles | p. 377 |

Forests and Trees | p. 377 |

Properties of Trees | p. 378 |

Leaves | p. 380 |

Spanning Trees | p. 382 |

Recap | p. 383 |

Exercises | p. 383 |

Eulerian Graphs | p. 385 |

Necessary Conditions | p. 386 |

Main Theorems | p. 387 |

Unfinished Business | p. 390 |

Recap | p. 390 |

Exercises | p. 390 |

Coloring | p. 391 |

Core Concepts | p. 392 |

Bipartite Graphs | p. 394 |

The Ease of Two-Coloring and the Difficulty of Three-Coloring | p. 398 |

Recap | p. 399 |

Exercises | p. 399 |

Planar Graphs | p. 400 |

Dangerous Curves | p. 400 |

Embedding | p. 401 |

Euler's Formula | p. 402 |

Nonplanar Graphs | p. 405 |

Coloring Planar Graphs | p. 406 |

Recap | p. 409 |

Exercises | p. 409 |

Partially Ordered Sets | p. 411 |

Partially Ordered Sets Fundamentals | p. 411 |

What Is a Poset? | p. 411 |

Notation and Language | p. 414 |

Recap | p. 416 |

Exercises | p. 416 |

Max and Min | p. 417 |

Recap | p. 419 |

Exercises | p. 419 |

Linear Orders | p. 420 |

Recap | p. 423 |

Exercises | p. 423 |

Linear Extensions | p. 423 |

Sorting | p. 427 |

Linear Extensions of Infinite Posets | p. 429 |

Recap | p. 430 |

Exercises | p. 430 |

Dimension | p. 431 |

Realizers | p. 431 |

Dimension | p. 434 |

Embedding | p. 436 |

Recap | p. 438 |

Exercises | p. 439 |

Lattices | p. 439 |

Meet and Join | p. 439 |

Lattices | p. 442 |

Recap | p. 445 |

Exercises | p. 445 |

Appendices | p. 447 |

Lots of Hints and Comments; Some Answers | p. 447 |

Glossary | p. 469 |

Fundamentals | p. 476 |

Numbers | p. 476 |

Operations | p. 476 |

Ordering | p. 476 |

Substitution | p. 477 |

Index | p. 479 |

Table of Contents provided by Syndetics. All Rights Reserved. |