Elements of discrete mathematics

ELEMENTS OF DISCRETE MATHEMATICS 5......Page 5
Copyright 6......Page 6
CONTENTS 7......Page 7
Preface to the Second Edition 11 ......Page 11
Preface to the First Edition 13......Page 13
1.1 Introduction 15 ......Page 15
1.2 Combinations of Sets 19 ......Page 19
1.3 Finite and Infinite Sets 23 ......Page 23
1.4 Uncountably Infinite Sets 25 ......Page 25
1.5 Mathematical Induction 27 ......Page 27
1.6 Principle of Inclusion and Exclusion 35 ......Page 35
1.7 Multisets 40 ......Page 40
1.8 Propositions 42 ......Page 42
1.9 Remarks and References 47 ......Page 47
2.2 Russell’s Paradox and Noncomputability 58 ......Page 58
2.4 Languages 63 ......Page 63
2.5 Phrase Structure Grammars 65 ......Page 65
2.6 Types of Grammars and Languages 73 ......Page 73
2.7 Remarks and References 75 ......Page 75
3.1 Introduction 80......Page 80
3.3 Permutations 81......Page 81
3.4 Combinations 87......Page 87
3.5 Generation of Permutations and Combinations 92 ......Page 92
3.6 Discrete Probability  94......Page 94
3.7 Conditional Probability 100 ......Page 100
3.8 Information and Mutual Information 103......Page 103
3.9 Remarks and References 109......Page 109
4.1 Introduction 117......Page 117
4.2 A Relational Model for Data Bases 120......Page 120
4.3 Properties of Binary Relations 123......Page 123
4.4 Equivalence Relations and Partitions 126......Page 126
4.5 Partial Ordering Relations and Lattices 130......Page 130
4.6 Chains and Antichains 133......Page 133
4.7 A Job-Scheduling Problem 136......Page 136
4.8 Functions and the Pigeonhole Principle 140......Page 140
4.9 Remarks and References 144......Page 144
5.1 Introduction 151......Page 151
5.2 Basic Terminology 153......Page 153
5.3 Multigraphs and Weighted Graphs 156......Page 156
5.4 Paths and Circuits 159......Page 159
5.5 Shortest Paths in Weighted Graphs 161......Page 161
5.6 Eulerian Paths and Circuits 163......Page 163
5.7 Hamiltonian Paths and Circuits 169......Page 169
5.8 The Traveling Salesperson Problem 173......Page 173
5.9 Factors of a Graph 179......Page 179
5.10 Planar Graphs 182......Page 182
5.11 Remarks and References 187......Page 187
6.1 Trees 201......Page 201
6.2 Rooted Trees 205......Page 205
6.3 Path Lengths in Rooted Trees 208......Page 208
6.4 Prefix Codes 211......Page 211
6.5 Binary Search Trees 216......Page 216
6.6 Spanning Trees and Cut-Sets 219......Page 219
6.7 Minimum Spanning Trees 224......Page 224
6.8 Transport Networks 227......Page 227
6.9 Remarks and References 233......Page 233
7.1 Introduction 244......Page 244
7.2 Finite State Machines 248 ......Page 248
7.3 Finite State Machines as Models of Physical Systems 250 ......Page 250
7.4 Equivalent Machines 251 ......Page 251
7.5 Finite State Machines as Language Recognizers 255 ......Page 255
7.6 Finite State Languages and Type3־ Languages 258 ......Page 258
7.7 Remarks and References 263 ......Page 263
8.1 Introduction 274 ......Page 274
8.2 Time Complexity of Algorithms 275 ......Page 275
8.3 A Shortest-Path Algorithm 278 ......Page 278
8.4 Complexity of Problems 279 ......Page 279
8.5 Tractable and Intractable Problems 283 ......Page 283
8.6 Remarks and References 285 ......Page 285
9.1 Introduction 291 ......Page 291
9.2 Manipulation of Numeric Functions 292 ......Page 292
9.3 Asymptotic Behavior of Numeric Functions 297 ......Page 297
9.4 Generating Functions 289 303......Page 303
9.5 Combinatorial Problems 310......Page 310
9.6 Remarks and References 313 ......Page 313
10.1 Introduction 320 ......Page 320
10.2 Recurrence Relations 321 ......Page 321
10.3 Linear Recurrence Relations with Constant Coefficients 323 ......Page 323
10.4 Homogeneous Solutions 326 ......Page 326
10.5 Particular Solutions 328 ......Page 328
10.6 Total Solutions 333 ......Page 333
10.7 Solution by the Method of Generating Functions 334 ......Page 334
10.8 Sorting Algorithms 340 ......Page 340
10.9 Matrix Multiplication Algorithms 345 ......Page 345
10.10 Remarks and References 348......Page 348
11.1 Introduction 356 ......Page 356
11.2 Groups 358 ......Page 358
11.3 Subgroups 362 ......Page 362
11.4 Generators and Evaluation of Powers 363 ......Page 363
11.5 Cosets and Lagrange’s Theorem 366 ......Page 366
11.6 Permutation Groups and Burnside’s Theorem 367......Page 367
11.7 Codes and Group Codes 373 ......Page 373
11.8 Isomorphisms and Automorphisms 377 ......Page 377
11.9 Homomorphisms and Normal Subgroups 379 ......Page 379
11.10 Rings, Integral Domains, and Fields 384 ......Page 384
11.11 Ring Homomorphisms 387 ......Page 387
11.12 Polynomial Rings and Cyclic Codes 390 ......Page 390
11.13 Remarks and References 393 ......Page 393
12.1 Lattices and Algebraic Systems 399 ......Page 399
12.2 Principle of Duality 402 ......Page 402
12.3 Basic Properties of Algebraic Systems Defined by Lattices 404 ......Page 404
12.4 Distributive and Complemented Lattices 407 ......Page 407
12.5 Boolean Lattices and Boolean Algebras 410 ......Page 410
12.6 Uniqueness of Finite Boolean Algebras 411 ......Page 411
12.7 Boolean Functions and Boolean Expressions 414 ......Page 414
12.8 Propositional Calculus 418 ......Page 418
12.9 Design and Implementation of Digital Networks 421 ......Page 421
12.10 Switching Circuits 423 ......Page 423
12.11 Remarks and References 430......Page 430
Index 437......Page 437