Index
597
probability, 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
597
probability, 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