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

INDEX 471

Full disjunctive form, 374
Function, 43
computable, 329
next-state, 307
rate of growth, 59
recursively defined, 52
Fundamental product, 6, 372
Fundamental Theorem of Algebra,
449

Gates, logic, 377
Gaussian elimination, 419
gcd(a, b) (greatest common
divisor), 270, 449
General tree, 251
Generators of a group, 202, 435
Gödel number, 326
Grammar, 310
Turing machine, 329
types of, 312
Graph, 156
adjacency structure (AS), 171,
212
Gray code, 193
Greatest lower bound, 342
Group, 438
cyclic, 442
symmetric, 439
Growth of functions, rate of, 59

Haken, Wolfgang, 170
HALT state, 327
Hamiltonian circuit, 161
Hamiltonian graph, 161
Hasse diagram, 346
Heap, 244
Height, 236
Homeomorphic graphs, 158
Homomorphism
of groups, 442
of rings, 445
of semi groups, 437, 442
Horner’s method, 56
Huffman’s algorithm, 249
code, 252

Ideal, 289, 444
Idempotent laws, 347
Identity:
element, 454
function, 44
matrix In, 414
relation, 25
Image of a function, 43, 44
Impossible event, 123
Incident, 157
Inclusion map, 44

Inclusion-Exclusion Principle, 9,

95, 108

Indegree, 203

Independent:

events, 129

repeated trials, 130

Index of a subgroup, 440

Indexed sets, 52

Induction, mathematical, 12, 266

transfinite, 346

Inequalities, 265

Infinium (inf), 342

Infinite set, 8, 61

Initial:

condition, 112

state, 307

Injective function, 46

Inner product, 410

Inorder traversal, 240

Input (in a Turing machine), 324,

329

Insertion:

in a binary tree, 243

in a heap, 245

Integer value, 48

Integers, 264

modulom, 276, 441

Integral domain, 444

Internal nodes, 237

Intersection of sets, 4

Inverse, 83

element, 434

matrix, 415

relation, 25

Inverter, 378

Invertible matrices, 415

Involution law, 370

Irreducible element, 445

Irredundant decompositions, 350

Isolated vertex, 160

Isomorphic, 437, 442

ordered sets, 344

rings, 445

semigroups, 437

Join, 346

irreducible, 349

Kn(complete graph), 163

Km,n(complete bipartite graph),

163

Karnaugh maps, 383

Kernel (Ker), 442

Kleene, 308

closure, 339

Königsberg bridges problem, 160

Kuratowski’s theorem, 168

LIFO (last-in, first-out), 155

Labeled graph, 202

Lagrange Theorem, 440

Language, 304, 308

regular, 306

types of, 312

Large Numbers, Law of, 136

Last-in, first-out, 155

Last element, 341

Lattice, 346

lcm(a, b) (least common multiple),

272

Leading nonzero element, 417

Least common multiple, 272

Least upper bound, 342

Leaves, 204, 236

Length, 210

of a path, 159, 203

of a vector, 410

of a word, 303

Level, 54, 204, 236

Lexicographical order, 205, 339

Linear:

combination, 269

congruence relation, 279

equations, 420

search, 58

Linear bounded automata, 314

Linearly ordered, 338

Linked list, 154

Linked representation, 171, 239

List, 51

linked, 154

Literal, 372

LNR traversal, 240

Logarithmic functions, 49

Logic,

circuits, 377

gates, 377

Logical equivalence, 74

Loop, 157, 201

Lower bound, 267, 342, 348

LRN traversal, 240

Lukasiewicz, 238

Machine:

finite state, 323

Turing, 314, 329

Map, 167

MAP(·), 440

Mathematical induction,

12, 266

Matrices, 410

determinant of, 416

square, 108

Matrix, 410

adjacency, 171, 206

augmented, 420