Index 597probability, 504 injection, 234 Inclusion-Exclusion, 491
cross product form, 500 injective, 234, 434 inclusive or, 15, 38
equally likely, 491 inverse, 245 increasing, 238
events invertible, 247 strictly, 238
disjoint, 508, 509 logarithmic, 293 indegree, 393
independent, 507, 509 onto, 232 independence
independent, alternate definition, partial, 229, 230 alternate definition for, 512
512 restriction, 228 independent, 507
excluded middle, 108 strictly decreasing, 238 pair of events, 509
existential quantification, 135 strictly increasing, 238 set of events, 508
expectation, 524 surjection, 234 independent events, 507, 509
of a random variable, 524 surjective, 234 independent random variables, 533
expected value, 524, 532 undefined, 230 indirect proof, 25, 27
experiment, 476, 477,498 Fundamental Theorem of Arithmetic, induced
expression tree, 95 68 subgraph, 336, 393
extends, 320 inductive step, 48, 589
gates, 28, 98 infinite, 265
face card, 482 generalized intersection, 20 infinite decimal, 257
factor, 4 generalized union, 20 infinite sequence, 248
failure in a Bernoulli trial, 498 geometric series, 557 infinite sets, 5
fair, 483 graph, 168, 334 InFrontOf relation, 173
card, 483 acyclic, 341 initial value, 552, 554, 562
coin, 483 directed, 393 injection, 234
false in formula, 104 disconnected, 353 injective, 234
Fibonacci numbers, 51, 561 invariant, 346 function, 434
finite, 265 of a function, 225 inorder traversal, 386, 549
finite automaton, 591 of a relation, 168 input size, 308, 311
finite decimal, 257 regular, 335 interior vertex, 379
finite sequence, 248 same, 345 internal vertex, 379
finite sets, 5 self-complementary, 345 internet address, 435
first order, 554 underlying, 393 intersection, 17
first-order recurrence relation, 552, WAITFOR, 396 associative, 17
554 weighted, 376 commutative, 17
floor, 220 graphical, 334 invariant, 346
flush (poker), 443 greatest integer function, 220 inverse, 25
for statement, 304 greatest lower bound, 217 of a function, 245
formula, 92, 135 greedy algorithms, 374 of a relation, 164
atomic, 135 invertible, 247
frequency interpretation, 480 halting problem, 318, 319 IPv4, 435
and conditional probability, 510 NegSelfRef, 319 IPv6, 435
full house, 449 unsolvable, 319 irreflexive, 168
function, 221, 222 Handshaking Theorem, 339 isolated vertex, 334
1-1 correspondence, 234 head, 393 isomorphic, 345, 394
bijection, 234 heapsort, 87
bijective, 234 height, 379 join, 208
binary, 223 tree, 379 natural, 208
Boolean, 227 homogeneous, 562
ceiling, 255 horizontal line test, 232 key operations, 300, 311
codomain, 221 Horn clause, 153 Kruskal's algorithm, 374
composition, 243 hypercube, 337
decreasing, 238 hypergeometric distribution, 522, 523 language, 587, 591
domain, 221 hypothesis, 7, 91 lattice, 28
equality, 226 complemented, 30
exponential, 293 i.i.d. random variables, 538 distributive, 29, 30
F + G, 248 idempotence, 108 lattice points, 279
F -G, 248 identically distributed, 534 Law of
F G, 248 identity function, 220 Averages, 538, 539
FIG, 248 if and only if, 7 Large Numbers, 538
greatest integer, 220 if... then ... else, 57 law of
identity, 220 image, 223 syllogism, 108
image, 223 implication, 6, 91 trichotomy, 194, 196
increasing, 238 incident, 334, 393 leaf, 371, 379