Table of Contents
Preface xiii
1 Sets 1
1.1 Preliminaries 1
1.2 Algebra of Sets 4
1.3 Venn Diagrams 9
1.4 Power Set 10
1.5 Countable Sets 11
1.6 Some Special Maps (Functions 17
1.6.1 The characteristic function 21
1.7 Partitions of Sets 22
1.8 The Minset and Maxset Normal Forms 24
1.9 Multisets 31
2 Propositional Calculus and Logic 41
2.1 Propositions 41
2.2 Compositions of Propositions 43
2.3 Truth Tables and Applications 45
2.4 Some Further Applications of Logic 55
2.5 Functionally Complete Set of Connectives 63
2.6 The Connectives NAND and NOR 64
3 More on Sets 69
3.1 The Principle of Inclusion and Exclusion 69
3.2 The Pigeonhole Principle 81
3.2.1 Some typical applications of the pigeonhole principle 82
3.3 Binary Relations 89
3.3.1 Relations 89
3.3.2 Equivalence relations 89
3.3.3 Union, intersection and inverse of relations 91
3.3.4 Composition of relations 93
3.3.5 The matrix of a relation 95
3.3.6 Closure operations on relations 98
4 Some Counting Techniques 107
4.1 The Principle of Mathematical Induction 107
4.2 Strong Induction 114
4.3 Arithmetic, Geometric and Arithmetic-Geometric Series 131
4.4 Permutations and Combinations 144
4.4.1 Rules of product and sum 144
4.4.2 Permutations 147
4.4.3 The arrangements of objects that are not all distinct 149
4.4.4 Combinations 152
4.4.5 Generation of permutations and combinations 156
5 Recurrence Relations 167
5.1 Partial Fractions 167
5.1.1 Rational functions 167
5.1.2 Partial fractions 168
5.1.3 Procedure for resolving into partial fractions 170
5.1.4 Some solved examples 173
5.2 Recurrence Relations: Preliminaries 180
5.2.1 Homogeneous solutions 183
5.2.2 Particular solutions 187
5.2.3 Solution by the method of generating functions 193
5.2.4 Some typical examples 197
5.2.5 Recurrence relations reducible to linear recurrence relations 205
6 Partially Ordered Sets 213
6.1 Preliminaries 213
6.2 Hasse Diagrams 216
6.3 Chains and Antichains in Posets 221
7 Graphs 241
7.1 Preliminaries and Graph Terminology 241
7.1.1 Some typical examples 261
7.2 Paths and Circuits 265
7.3 Shortest Path in Weighted Graphs 271
7.4 Eulerian Paths and Circuits 281
7.5 Hamiltonian Paths and Circuits 298
7.6 Planar Graphs 309
7.6.1 Applications 313
7.6.2 Some further examples 316
7.6.3 Graph colouring 319
7.7 Matrix Representations of Graphs 325
7.7.1 Adjacency matrix 325
8 Trees 343
8.1 Introduction and Elementary Properties 343
8.2 Rooted Trees 350
8.3 Tree Searching or Traversing a Tree 362
8.4 Applications of Trees 376
8.4.1 Prefix codes 376
8.4.2 Binary search trees 384
8.4.3 On counting trees 388
8.4.4 Some further examples 395
8.5 Spanning Trees and Cut-Sets 400
8.6 Minimal/Minimum/Shortest Spanning Tree 416
9 Groups 443
9.1 Groups: Preliminaries 443
9.2 Subgroups 449
9.2.1 Lagrange's theorem 451
9.3 Quotient Groups 455
9.4 Symmetric Groups 457
10 Rings 467
10.1 Rings 467
10.2 Polynomial Rings 470
10.3 Quotient Rings and Homomorphisms 474
11 Fields and Vector Spaces 481
11.1 Fields 481
11.1.1 Field extensions and minimal polynomial 484
11.1.2 Characteristic of a field 485
11.1.3 Splitting field 485
11.2 Vector Spaces 491
11 2 1 Basis of a vector space 494
11.2.2 Subspaces and quotient spaces 498
11.2.3 Linear transformations 504
12 Lattices and Boolean Algebra 509
12.1 Lattices 509
12.2 Lattices as Algebraic Systems 515
12.3 Sublattices and Homomorphisms 521
12.4 Distributive and Modular Lattices 525
12.5 Complemented Lattices 541
12.6 Boolean Algebras 545
12.7 Boolean Polynomials and Boolean Functions 554
12.8 Switching (or Logical) Circuits 567
13 Matrices, Systems of Linear Equations and Eigen Values 577
13.1 Linear System of Equations 577
13.1.1 Rank of a matrix 577
13.1.2 Linear system of equations 578
13.2 Elementary Row Operations, Gaussian Elimination 581
13.2.1 Elementary row operations 581
13.2.2 Gaussian elimination in matrix form 583
13.2.3 Gaussian elimination method 585
13.2.4 Direct methods for the solution of linear system of equations 591
13.2.5 Method of factorization 594
13 2 6 Some additional examples 598
13.3 Eigen Values 600
13.3. Eigen values and eigen vectors 603
Bibliography 613
Index 615
