598
Index
least upper bound, 217
occur, 478
polynomial, 291
left child, 381
odd integer, 75
function, 291
lemma, 53
odd vertex, 334
time, 309
length, 340
onto, 232
postorder traversal, 386
level, 379
operation
power set, 28
lexicographical order, 194, 446
commutative, 253
predicate, 135
linear order, 191
operations on functions, 243
binary, 135
lists, 249
F + G, 248
constant, 135
logically
F - G, 248
n-ary, 135
equivalent, 110
FIG, 248
preimage, 223
implies, 110
composition, 243
preorder traversal, 386
valid, 106
inverse, 245
Prim's Algorithm for MCST, 417
loop, 57
or
prime, 4
command, 57
inclusive, 38
Principle
loop invariant assertions, 141
order of, 285
Inclusion-Exclusion, 491
lower bound, 217
ordered pair, 220, 477
Inclusion-Exclusion for a Finite
Lucas Numbers, 64
ordering, 194
Number of Sets, 41
dictionary, 194
Inclusion-Exclusion for Three or
mapped, 223
lexicographical, 194
More Sets, 37
Master Theorem, 579
linear, 194
Inclusion-Exclusion for Two Sets,
mathematical induction, 47
total, 194
36
Principle of Mathematical
orientable, 405
Mathematical Induction, 48
Induction, 48
outcome, 477, 478
Well-Ordering, 81
Strong Form of Mathematical
outdegree, 393
probability, 475
Induction, 67
density function, 479
matrix, 346
P(n; ri, r2 ... , rm), 453
conditional, 507
columns, 346
P does not equal NP, 310
cross product events, 504
rows, 346
palindrome, 434
density, 479
maximal, 197
parent, 379
frequency interpretation, 510
maximum, 30, 197
parser, 588
of an outcome, 478
MCST, 377
partial function, 229, 230, 318
reliability of a communication
mean, 524, 532
codomain, 230
channel, 514
member, 2
domain, 230
total, 512
merge sort, 571
domain of definition, 230
probability density, 492
minimal, 197
preimage, 230
uniform, 482, 491
minimal cost spanning tree, 377
range, 230
probability of an event, 479
minimum, 197
partial order, 191
probability principle
element, 30
particular solution, 564
multiplication, 493
modus tollen ponens, 108
partition, 183
product of sums, 494
modus
~Pascalprcs
multigraph, 361
process
multigraphs, 415
identity, 458
Bernoulli, 498
multinomial coefficient, 463
triangle, 463
dependent trials, 516, 518
Multiplication Principle, 424
column sum, 463
trials, 498
multiplication principle
diagonal sum, 463
product of sums principle,
probability, 493
triangle, row sum, 463
494
path, 340
projection, 206
directed, 394
proof
n-ary, 135
perfect square, 58
indirect, 27
n-cube, 337
permutation, 436
proof is analogous, 16
Qn, 337
with repetitions, 452
proper subset, 6
n-cycle, 341
permutations, circular, 439
property, 163
n-regular, 335
Pierce arrow, 152
proposition, 90
natural join, 208
Pigeon-Hole Principle, 253, 255,
connectives, 90
natural numbers, 4
430
constants, 90
negation, 91
Generalized, 255
letter, 90
negation normal form, 138
Weak Form, 255
propositional logic, 89
nested quantifiers, 137
pips, 476
pseudocode, 56
nondeterministic polynomial time,
poker hand, 441
comment, 57
310
flush, 443
condition, 57
nonhomogeneous, 555
full house, 449
loop, 57
nonterminating decimal, 257
straight, 443
recursion, 57
normal forms, 89
straight flush, 443, 449
while loop, 57
Index
least upper bound, 217
occur, 478
polynomial, 291
left child, 381
odd integer, 75
function, 291
lemma, 53
odd vertex, 334
time, 309
length, 340
onto, 232
postorder traversal, 386
level, 379
operation
power set, 28
lexicographical order, 194, 446
commutative, 253
predicate, 135
linear order, 191
operations on functions, 243
binary, 135
lists, 249
F + G, 248
constant, 135
logically
F - G, 248
n-ary, 135
equivalent, 110
FIG, 248
preimage, 223
implies, 110
composition, 243
preorder traversal, 386
valid, 106
inverse, 245
Prim's Algorithm for MCST, 417
loop, 57
or
prime, 4
command, 57
inclusive, 38
Principle
loop invariant assertions, 141
order of, 285
Inclusion-Exclusion, 491
lower bound, 217
ordered pair, 220, 477
Inclusion-Exclusion for a Finite
Lucas Numbers, 64
ordering, 194
Number of Sets, 41
dictionary, 194
Inclusion-Exclusion for Three or
mapped, 223
lexicographical, 194
More Sets, 37
Master Theorem, 579
linear, 194
Inclusion-Exclusion for Two Sets,
mathematical induction, 47
total, 194
36
Principle of Mathematical
orientable, 405
Mathematical Induction, 48
Induction, 48
outcome, 477, 478
Well-Ordering, 81
Strong Form of Mathematical
outdegree, 393
probability, 475
Induction, 67
density function, 479
matrix, 346
P(n; ri, r2 ... , rm), 453
conditional, 507
columns, 346
P does not equal NP, 310
cross product events, 504
rows, 346
palindrome, 434
density, 479
maximal, 197
parent, 379
frequency interpretation, 510
maximum, 30, 197
parser, 588
of an outcome, 478
MCST, 377
partial function, 229, 230, 318
reliability of a communication
mean, 524, 532
codomain, 230
channel, 514
member, 2
domain, 230
total, 512
merge sort, 571
domain of definition, 230
probability density, 492
minimal, 197
preimage, 230
uniform, 482, 491
minimal cost spanning tree, 377
range, 230
probability of an event, 479
minimum, 197
partial order, 191
probability principle
element, 30
particular solution, 564
multiplication, 493
modus tollen ponens, 108
partition, 183
product of sums, 494
modus
~Pascalprcs
multigraph, 361
process
multigraphs, 415
identity, 458
Bernoulli, 498
multinomial coefficient, 463
triangle, 463
dependent trials, 516, 518
Multiplication Principle, 424
column sum, 463
trials, 498
multiplication principle
diagonal sum, 463
product of sums principle,
probability, 493
triangle, row sum, 463
494
path, 340
projection, 206
directed, 394
proof
n-ary, 135
perfect square, 58
indirect, 27
n-cube, 337
permutation, 436
proof is analogous, 16
Qn, 337
with repetitions, 452
proper subset, 6
n-cycle, 341
permutations, circular, 439
property, 163
n-regular, 335
Pierce arrow, 152
proposition, 90
natural join, 208
Pigeon-Hole Principle, 253, 255,
connectives, 90
natural numbers, 4
430
constants, 90
negation, 91
Generalized, 255
letter, 90
negation normal form, 138
Weak Form, 255
propositional logic, 89
nested quantifiers, 137
pips, 476
pseudocode, 56
nondeterministic polynomial time,
poker hand, 441
comment, 57
310
flush, 443
condition, 57
nonhomogeneous, 555
full house, 449
loop, 57
nonterminating decimal, 257
straight, 443
recursion, 57
normal forms, 89
straight flush, 443, 449
while loop, 57