Index 599quantification,^135 cross product,^496 second kind,^469
existential, 135 SAT, 310 straight flush, 449
universal, 135 satisfiability,^310 streams,^249
query, 205 3-satisfiability problem, 548 strict partial orderings, 192
quotient, 181 satisfiable, 106 strictly
satisfies, 110 decreasing, 238
r-permutation, 436 scaling of a random variable, 527 increasing, 238
random variable, 520 scope of quantifier,^136 strings,^587
constant, 528 second order strongly connected component, 402,
expectation of, 524 homogeneous recurrence, 563 403
expected value of, 532 recurrence,^562 structured programming,^300
i.i.d., 534 recurrence relation subformula, 96
mean of, 532 homogeneous, 566 subgraph, 336
scaling of, 527 selection, 205 directed, 393
standard deviation of, 531 selection database (programming), induced, 336, 393
variance of, 531 301 spanning, 336, 394
random variables selection sort, 45 subsequence, 249, 250
i.i.d., 538 self-complementary, 345 subset, 6, 191, 426
independent, 533 sentences,^588 proper,^6
independent, identically distributed, sequence, 249, 301 success in a Bernoulli trial, 498
538 decreasing, 249 sum of random variables, 526
sum of, 526 finite, 248 surjection, 234
range, 223 increasing,^249 surjective,^234
reals are uncountable, 271 infinite, 248 symmetric, 169, 181
recursive definition, 51 lists, 249 difference, 24
recursively defined, 51 strictly decreasing, 249 syntax, 588
refines, 186 strictly increasing, 249
reflexive, 168, 181 subsequence,^250 tail,^393
regular sequences tautologically
graph, 335 streams, 249 equivalent, 110
set, 589 set implies,^110
relation complement, 488 tautology, 106
ancestor, 172 decomposition, 428 Taylor series,^298
binary, 222 size, 482 Template
empty, 161 sets disproving for every x E A,^27
equivalence,^181 infinite,^5 if and only if results,^13
trivial, 161 equal, 5 mathematical induction, 49
unary, 163 finite, 5 prove A C B, 10
universal, 161 Sheffer stroke,^152 prove A C B,^9
void, 161 sibling, 379 proving sets equal, 11
relational size of cross product,^496 proving sets not equal,^12
database, 203 solution, 552 Strong Form of Mathematical
algebra, 205 solving Induction, 70
database, 204 divide-and-conquer r.r., 577 terminal, 379
reliability, 514 first-order r.r., 555 terminating decimal,^257
remainder, 181 second-order r.r., 566 time complexity, 300
repeating decimal, 257 sorting total ordering,^194
repeating decimal notation, 257 bubble,^305 total probability,^512
repetition, 301 insertion, 326 Tower of Hanoi,^549
nested, 307 merge,^571 trail,^340
resolution, 129 selection, 45 directed,^394
restriction, 228 sound,^131 transcendental,^272
right child, 381 spanning subgraph, 336,^374 transition function,^591
root, 378 spots, 476 transitive, 172, 181
rooted standard deviation, 531 closure, 173
subtree, 380 start state,^591 transmitter,^416
tree, 378 statement,^25 Traveler's Problem,^421
rotation, 384 while, 57 traversal
states, 591 inorder, 386
same cardinality,^265 STCONN,^403 postorder,^386
sample space, 477, 478 Stirling numbers preorder, 386
countably infinite, 491 first kind, 468 tree, 371, 424