470 INDEX
Closed:
path, 159, 203
under operation, 432
Closure, Kleene, 339
Closure of relations, 31
transitive, 31
Code, Huffman, 252
Codomain, 43
Colored:
graphs, 168
maps, 170
Column, 410
Combinations, 93
with repetition, 107
Commutative operation, 433
Comparable elements, 338
Complement:
in a Boolean algebra, 368
in a lattice, 351
of a set, 6
Complemented lattice, 454
Complete:
binary tree, 237
graph, 163
residue system, 275
set of solutions, 278
sum-of-products form, 374
Complex numbers,C,2
Complexity of algorithms, 57
in a binary search tree, 243
in a heap, 248
Composition:
of functions, 45
of relations, 27
Computable function, 329–330
Concatenation, 303, 305
Conditional probability, 127
Conditional statement, 75
Congruence relation, 274
arithmetic, 275
Conjunction, 71
Connected graph, 160, 204
components, 160
strongly, 235
unilaterally, 235
weakly, 235
Consensus, 375
method, 376
Consistent enumeration, 342
Context-free grammar, 312
Context-sensitive grammar, 312
Contradiction, 74
Contrapositive statement, 83
Converse statement, 83
Coprime, 273
Coset, 440
Countable set, 8, 55
Counterexample, 80
Counting principle, 8
Cover, minimal, 386
Cross partition, 20
Cutpoint, 160
Cycle, 159, 203
Cycle-free, 164, 216
Cyclic group, 442Dm,(divisors of m), 369
DFS (depth-first-search), 173, 214
Dag (directed acyclic graph), 216,
340
Deck of cards, 24, 125
Degree, 203
of a polynomial, 446
of a region, 167
of a vertex, 157
DeMorgan’s law, 7, 11, 62, 79
Dense graph, 171, 206
Denumerable set, 55
Dependent events, 129
Depth:
of a binary tree, 236
of recursion, 54
Depth-first-search, 173, 214
Derangement, 110
Derivation tree, 313
Descendant, 236
Detachment, Law of, 76
Determinants, 416–417
Diagonal of a matrix, 414
Diagram:
Hasse, 346
state, 307, 329
Venn, 3
Diameter of a graph, 160
Dice, 24, 125
Digraph (directed graph), 201
Direct product of groups, 464
Directed graph, 201, 214
Disjoint sets, 3
Disjunction (or), 71
Disjunctive normal form, 373
Distance between vertices, 160
Distribution, 133
binomial, 131
Distributive lattice, 349
Divisibility, 445
Division algorithm, 267
Domain, 24, 43
Domain (integral), 444
Dot product, 410
Dual map, 170
Duality, 8, 347, 369
Dummy index, 51E(G) (edges in a graph), 201
Echelon matrix, 418Edge, 156, 236
file, 172, 212
Element of a set, 1
Elimination, Gaussian, 419
Empty set, 2
word, 303
Equality:
of functions, 44
of matrices, 40
of sets, 2
Equality relation, 25
Equiprobable space, 126
Equivalence:
class, 32
relation, 31
Euclidean algorithm, 271, 447
Euler:
formula, 167
phi function, 278
Eulerian graph, 160
Even integer, 269
vertex, 157
Event (probability), 123
elementary, 126
independent, 129
Exclusive disjunction, 72
Existential quantifier, 78
Expectation, 133
Exponential function, 49
Expression, 327
Extended binary tree, 237
External node, 237FIFO (first-in, first-out), 156
Factor Theorem, 448
Factorial, 89
Failure, 131
Family, 1
Falacy, 76
Fibonacci sequence, 54, 115
Field, 444
File:
edge, 206
vertex, 206
Finite:
graph, 158, 202
set, 8
state automaton (FSA), 306
state machine (FSM), 323
First element, 341
First-in, first-out, 156
Floor function, 48
Forest, 164, 252
Four Color Theorem, 171
Free:
monoid, 135, 304
semigroup, 135, 304
Front of queue, 156