Index
599
quantification, 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
599
quantification, 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