Schaum's Outline of Discrete Mathematics, Third Edition (Schaum's Outlines)

472 INDEX

Matrix (continued)
Boolean, 206, 422
of a relation, 26
Maximal:
element, 341
rectangle, 386
Maxheap, 244
Mean, 133
Meet, 346
Member of a set, 1
Minheap, 245
Minimal:
cover, 386
element, 341
path, 249
spanning tree, 165
sum-of-products, 375
Modified cancellation law,
277
Modular arithmetic, 48, 274
Modulus, 274
Moments, 148
Monic polynomial, 446
Monoid, 304, 435
Multigraph, 156
Multiplicative function,
278
Multiplier, 419
Mutually exclusive events,
123

N(positive integers), 2
n(•) (number of elements), 8
n-cubeQn, 192
n-tuple, 51
NAND gate, 380
Natural:
log, 50
mapping, 437
numbers, 2
Negation, 72
of a quantifier, 78
Negative, 434
Neighbor, 157
Nearest-neighbor algorithm,
177
Next-state function, 307
NLR traversal, 240
NO state, 327
Nodes, 154, 156, 201, 235
external, 237
internal, 237
Nonplanar graph, 168
Nonsingular matrix, 415
NOR gate, 380
Norm, 410
Normal subgroup, 440
NOT gale, 378

Null:

pointer, 155, 239

set Ø, 3

tree, 235

Odd vertex, 157

One to-one:

correspondence, 46

function, 46

Onto function, 46

Operations, 432

OR, 208

OR gate, 377

Order, 33, 365

dual, 338

of an element, 442

of a group, 438

product, 339

Ordered:

pairs, 23

partitions, 108

rooted tree, 205

samples, 92

set, 338

Outdegree, 203

P(n, r) (permutations), 91

Parallel:

arcs, 202

edges, 202

Parent, 236

Partially ordered set, 33, 337

Partition:

ordered, 32

of a positive integer, 341

of a set, 10

Pascal’s triangle, 90

Path in a graph, 159, 203, 236

matrix, 207

PERM (·), 440

Permutations, 91, 439

with repetition, 92

Phrase structure grammars, 310

Picture card, 125

PID (Principal Ideal Domain), 445

Pigeonhole principle, 94, 110

Pivot, 419

Planar graphs, 166

Pointer, 154

Polish notation, 238

Polynomial, 446

evaluation, 56

function, 45

monic, 446

Poset (partially ordered set), 33,

337

Positive integersN,2

Postfix form, 238

Postorder transversal, 240

Power set, 10

Precedes, 337

Prefix form, 238

property, 250

Premises, 76

Preordcr traversal, 240

Prime implicant, 375

Prime number, 269

Principal ideal, 445

domain, 445

Priority queue, 156, 444

Probability, 126

conditional, 127

distribution, 132

random variable, 132

Product:

order, 339

rule, 89

set, 23, 24

Production in a grammar, 310

Proposition, 70

truth table of, 73

Propositional function, 77

Pruning algorithm, 419

Pumping Lemma, 309

Pushdown automata, 314

Q(rational numbers), 2

Quantifiers, 77

negation of, 78

Quasi-order, 339

Queue, 156

priority, 156

Quintuple (Turing machine),

328

Quotient:

group, 440

ring, 445

semigroup, 436

set, 32

R(real number system), 2

Random, 126

variable, 132

Range, 43

space, 132

Rate of growth, 59

Reachable vertex, 203

matrix, 207

Real number systemR,2

Rear of a queue, 156

Recognition of words, 308

Recurance relation, 11, 113

Recursively defined functions, 52

Reduced residue system, 276

Reflexive relation, 28

Region of a map, 167