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
matrix, Induction, 346 67 P(n; ri, r2 ... density function,^479
columns, 346 P does not equal , rm), NP,^453 310 conditional, cross product^507 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
merge member, sort,^2 571 domain, domain of^230 definition, total,^512
minimal, 197 preimage, 230 230 probability uniform, 482, density, 491492
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 modus ponens, (^108) ~Pascalprcspartition, 183 product of sums,^494
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 probability, 493 principle diagonal sum, 463 product of sums principle,
path, triangle, 340 row sum,^463 projection,^494206
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