Description
Book SynopsisThis book is designed to meet the requirement of undergraduate and postgraduate students pursuing computer science, information technology, mathematical science, and physical science course. No formal prerequisites are needed to understand the text matter except a very reasonable background in college algebra. The text contains in-depth coverage of all major topics proposed by professional institutions and universities for a discrete mathematics course. It emphasizes on problem-solving techniques, pattern recognition, conjecturing, induction, applications of varying nature, proof technique, algorithmic development, algorithm correctness, and numeric computations. A sufficient amount of theory is included for those who enjoy the beauty in development of the subject and a wealth of applications as well as for those who enjoy the power of problem-solving techniques.
Biographical sketches of nearly 25 mathematicians and computer scientists who have played a significant role in the development of the field are threaded into the text to provide a human dimension and attach a human face to major discoveries. Each section of the book contains a generous selection of carefully tailored examples to classify and illuminate various concepts and facts. Theorems are backbone of mathematics. Consequently, this book contains the various proof techniques, explained and illustrated in details. Most of the concepts, definitions, and theorems in the book are illustrated with appropriate examples. Proofs shed additional light on the topic and enable students to sharpen thin problem-solving skills. Each chapter ends with a summary of important vocabulary, formulae, properties developed in the chapter, and list of selected references for further exploration and enrichment.
Table of Contents0. PRELIMINARIES 1–14
0.1 Numbers 1
0.2 Euclid’s Algorithm 3
0.3 Fundamental Theorem of Arithmetic 4
0.4 Euclid’s Theorem 6
0.5 Congruence Modulo m 6
0.6 Chinese Remainder Theorem 7
0.7 Fermat’s and Euler’s Theorems 9
0.8 Exponents and Logarithms 10
0.9 Sums 11
0.10 Mapping 12
Suggested Readings 14
1. THE LANGUAGE OF SETS 15–66
1.1 Introduction 15
1.2 Elements and Notations of Sets 16
1.3 Construction of Sets 17
1.4 Types of Sets 19
1.5 Set Operations 25
1.5.1 Intersection of Sets 25
1.5.2 Union of Sets 26
1.5.3 Disjoint Set (Mutually Exclusive) 27
1.5.4 Ordinary Difference of Sets (A – B) 27
1.5.5 Complementation of Sets 27
Contents
xii Contents
1.5.6 Universal Set and its Complement 27
1.5.7 Symmetric Difference (Boolean Sum) 28
1.6 Venn Diagrams 28
1.7 Some Basic Results 32
1.8 Properties of Set Operations 34
1.8.1 Properties of Intersection on Sets 34
1.8.2 Properties of Union of Sets 35
1.8.3 Number of Elements in a Union of two or more Sets 39
1.9 De-Morgan’s Laws 40
1.10 General form of Principle of Inclusion and Exclusion 44
1.11 Laws of Sets 63
Summary 63
Suggested Readings 65
2. BASIC COMBINATORICS 67–114
2.1 Introduction 67
2.2 Basic Counting Principles 68
2.2.1 The Principle of Disjunctive Counting (Sum Rule) 68
2.2.2 The Principle of Sequential Counting (Product Rule) 69
2.3 Factorial 71
2.4 Permutation and Combination 73
2.4.1 Cyclic Permutation 76
2.4.2 Pascal’s Identity 76
2.4.3 Vandermonde’s Identity 77
2.4.4 Pigeonhole Principle 78
2.4.5 Inclusion–Exclusion Principle 79
2.5 The Binomial Theorem 93
2.6 nth Catalan Number 95
2.7 Principle of Mathematical Induction (P.M.I) 96
2.8 Recurrence Relations 99
Summary 110
Suggested Readings 113
Contents xiii
3. MATHEMATICAL LOGIC 115–180
3.1 Introduction 115
3.2 Propositions (Statements) 117
3.3 Connectives 117
3.3.1 Negation 118
3.3.2 Conjunction 119
3.3.3 Disjunction 119
3.3.4 Conditional 120
3.3.5 Biconditional 120
3.4 Equivalence of Formulae 121
3.5 Well-Formed Formulae (WFF) 122
3.6 Tautologies 122
3.7 Principle of Duality 123
3.8 Two State Devices 128
3.9 The Relay-Switching Devices 129
3.10 Logic Gates and Modules 130
3.10.1 OR, AND and NOT Gates 130
3.10.2 Two-Level Networks 132
3.10.3 NOR and NAND Gates 132
3.11 Normal Forms (Decision Problems) 141
3.11.1 Disjunctive Normal Form (DNF) 141
3.11.2 Conjunctive Normal Form (CNF) 145
3.11.3 Principal Disjunctive Normal Form (PDNF) 146
3.11.4 Principal Conjuctive Normal Forms (PCNF) 148
3.12 Rules of Inference 151
3.13 Automatic Proving System (Theorems) 152
3.14 The Predicate Calculus 164
3.14.1 Statement Functions, Variables and Quantifiers 166
3.14.2 Free and Bound Variables 166
3.14.3 Special Valid Formulae using Quantifiers 167
3.14.4 Theory of Inference for the Predicate Calculus 168
3.14.5 Formulae Involving More than one Quantifier 169
Summary 175
Suggested Readings 179
xiv Contents
4. RELATIONS 181–236
4.1 Introduction 181
4.2 Product Sets 182
4.3 Partitions 182
4.4 Relations 183
4.5 Binary Relations in a Set 183
4.6 Domain and Range of a Relation 184
4.6.1 Number of Distinct Relation From set A to B 185
4.6.2 Solution sets and Graph of Relations 189
4.6.3 Relation as Sets of Ordered Pairs 190
4.7 The Matrix of a Relation and Digraphs 190
4.8 Paths in Relations and Digraphs 191
4.9 Boolean Matrices 194
4.9.1 Boolean Operations AND and OR 195
4.9.2 Joint and Meet 195
4.9.3 Boolean Product 195
4.9.4 Boolean Power of a Boolean Matrix 195
4.10 Adjacency Matrix of a Relation 198
4.11 Gray Code 198
4.12 Properties of Relations 200
4.12.1 Reflexive and Irreflexive Relations 201
4.12.2 Symmetric, Asymmetric and Antisymmetric
Relations 201
4.12.3 Transitive Relation 202
4.13 Equivalence Relations 205
4.14 Closure of Relations 207
4.15 Manipulation and Composition of Relations 208
4.16 Warshall’s Algorithm 216
4.17 Partial Order Relation 225
4.17.1 Totally Ordered Set 226
4.17.2 Lexicographic Order 226
4.17.3 Hasse Diagrams 228
Summary 230
Suggested Readings 235
Contents xv
5. FUNCTIONS 237–270
5.1 Introduction 238
5.1.1 Sum and Product of Functions 239
5.2 Special Types of Functions 242
5.2.1 Polynomial Function 244
5.2.2 Exponential and Logarithmic Function 244
5.2.3 Floor and Ceiling Functions 245
5.2.4 Transcedental Function 247
5.2.5 Identity Function 247
5.2.6 Integer Value and Absolute Value Functions 247
5.2.7 Remainder Function 248
5.3 Composition of Functions 248
5.4 Inverse of a Function 250
5.5 Hashing Functions 256
5.6 Countable and Uncountable Sets 257
5.7 Characteristic Function of a Set 259
5.8 Permutation Function 261
5.9 Growth of Functions 262
5.10 The Relation Θ 262
Summary 267
Suggested Readings 269
6. LATTICE THEORY 271–304
6.1 Introduction 271
6.2 Partial Ordered Sets 272
6.2.1 Some Important Terms 273
6.2.2 Diagramatical Representation of a Poset
(Hasse Diagram) 275
6.2.3 Isomorphism 276
6.2.4 Duality 278
6.2.5 Product of two Posets 280
6.3 Lattices as Posets 282
6.3.1 Some Properties of Lattices 283
6.3.2 Lattices as Algebraic Systems 284
xvi Contents
6.3.3 Complete Lattice 290
6.3.4 Bounded Lattice 290
6.3.5 Sublattices 291
6.3.6 Ideals of Lattices 291
6.4 Modular and Distributive Lattices 292
Summary 302
Suggested Readings 304
7. BOOLEAN ALGEBRAS AND APPLICATIONS 305–354
7.1 Introduction 305
7.2 Boolean Algebra (Analytic Approach) 306
7.2.1 Sub-Boolean Algebra 308
7.2.2 Boolean Homomorphism 309
7.3 Boolean Functions 318
7.3.1 Equality of Boolean Expressions 319
7.3.2 Minterms and Maxterms 319
7.3.3 Functional Completeness 320
7.3.4 NAND and NOR 320
7.4 Combinatorial Circuits (Synthesis of Circuits) 326
7.4.1 Half-Adder and Full-Adder 326
7.4.2 Equivalent Combinatorial Circuits 328
7.5 Karnaugh Map 331
7.5.1 Don’t Care Conditions 334
7.5.2 Minimization Process 335
7.6 Finite State Machines 344
Summary 347
Suggested Readings 352
8. FUZZY ALGEBRA 355–392
8.1 Introduction 355
8.2 Crisp Sets and Fuzzy Sets 357
8.3 Some Useful Definitions 360
8.4 Operations of Fuzzy Sets 362
8.5 Interval-Valued Fuzzy Sets (I-V Fuzzy Sets) 367
8.5.1 Union and Intersection of two I–V Fuzzy Sets 368
Contents xvii
8.6 Fuzzy Relations 369
8.6 Fuzzy Measures 373
8.7.1 Belief and Plausibility Measures 373
8.7.2 Probability Measure 374
8.7.3 Uncertainty and Measures of Fuzziness 374
8.7.4 Uncertainty and Information 375
8.8 Applications of Fuzzy Algebras 376
8.8.1 Natural, Life and Social Sciences 376
8.8.2 Engineering 378
8.8.3 Medical Sciences 381
8.8.4 Management Sciences and Decision Making
Process 382
8.8.5 Computer Science 383
8.9 Uniqueness of Uncertainty Measures 384
8.9.1 Shannon’s Entropy 384
8.9.2 U-uncertainty 386
8.9.3 Uniqueness of the U-uncertainty for
Two-Value Possibility Distributions 388
Summary 389
Suggested Readings 390
9. FORMAL LANGUAGES AND AUTOMATA
THEORY 393–428
9.1 Introduction 393
9.2 Formal Languages 396
9.2.1 Equality of Words 397
9.2.2 Concatenation of Languages 398
9.2.3 Kleene Closure 399
9.3 Grammars 403
9.3.1 Phase-structure Grammar 406
9.3.2 Derivations of Grammar 406
9.3.3 Backus-Normal Form (BNF) or Backus
Naur Form 407
9.3.4 Chomsky Grammar 410
9.3.5 Ambiguous Grammar 411
xviii Contents
9.4 Finite-State Automation (FSA) 413
9.4.1 Counting to Five 414
9.4.2 Process of Getting up in the Morning (Alarm) 414
9.4.3 Traffic Light 415
9.4.4 Vending Machine 416
9.5 Finite-State Machine (FSM) 416
9.6 Finite-State Automata 418
9.6.1 Deterministic Finite-State Automata (DFSA) 418
9.6.2 Nondeterministic Finite-State Automata 419
9.6.3 Equivalent Nondeterministic Finite State
Automata 420
Summary 424
Suggested Readings 428
10. THE BASICS OF GRAPH THEORY 429–480
10.1 Introduction 429
10.2 Graph. What is it? 430
10.2.1 Simple Graph 430
10.2.2 Graph 433
10.2.3 Loops 436
10.2.4 Degree of Vertices 436
10.2.5 Equivalence Relation 441
10.2.6 Random Graph Model 442
10.2.7 Isolated Vertex, Pendent Vertex and Null Graph 442
10.3 Digraphs 443
10.4 Path, Trail, Walk and Vertex Sequence 446
10.5 Subgraph 447
10.6 Circuit and Cycle 447
10.7 Cycles and Multiple Paths 449
10.8 Connected Graph 449
10.9 Spanning Subgraph and Induced Subgraph 450
10.10 Eulerian Graph (Eulerian Trail and Circuit) 450
10.11 Hamiltonian Graph 451
10.12 Biconnected Graph 452
Contents xix
10.13 Algebraic terms and operations used in Graph Theory 453
10.13.1 Graphs Isomorphism 453
10.13.2 Union of two Graphs 455
10.13.3 Intersection of two Graphs 455
10.13.4 Addition of two Graphs 456
10.13.5 Direct Sum or Ring Sum of two Graphs 456
10.13.6 Product of two Graphs 457
10.13.7 Composition of two Graphs 457
10.13.8 Complement of a Graph 457
10.13.9 Fusion of a Graph 458
10.13.10 Rank and Nullity 459
10.13.11 Adjacency Matrix 459
10.13.12 Some Important Theorems 460
10.14 Some Popular Problems in Graph Theory 465
10.14.1 Tournament Ranking Problem 465
10.14.2 The Königsberg Bridge Problem 467
10.14.3 Four Colour Problem 467
10.14.4 Three Utilities Problem 468
10.14.5 Traveling - Salesman Problem 468
10.14.6 MTNL’S Networking Problem 470
10.14.7 Electrical Network Problems 470
10.14.8 Satellite Channel Problem 471
10.15 Applications of Graphs 471
Summary 475
Suggested Readings 480
11. TREES 481–520
11.1 Introduction 481
11.2 Definitions of a Tree 482
11.3 Forest 483
11.4 Rooted Graph 484
11.5 Parent, Child, Sibling and Leaf 485
11.6 Rooted Plane Tree 485
11.7 Binary Trees 492
xx Contents
11.8 Spanning Trees 494
11.9 Breadth – First Search and Depth – First
Search (BFS and DFS) 496
11.10 Minimal Spanning Trees 504
11.10.1 Kruskal’s Algorithm (for Finding a Minimal
Spanning Tree) 504
11.10.2 Prim’s Algorithm 509
11.11 Directed Trees 511
Summary 516
Suggested Readings 518
12. PLANAR GRAPHS 521–544
12.1 Introduction 521
12.2 Geometrical Representation of Graphs 522
12.3 Bipertite Graph 524
12.4 Homeomorphic Graph 525
12.5 Kuratowski’s Graphs 526
12.6 Dual Graphs 530
12.7 Euler’s Formula 532
12.8 Outerplanar Graphs 535
12.8.1 k-outerplanar Graphs 536
Summary 542
Suggested Readings 543
13. DIRECTED GRAPHS 545–574
13.1 Introduction 545
13.2 Directed Paths 547
13.3 Tournament 549
13.4 Directed Cycles 550
13.5 Acyclic Graph 554
13.6 Di-Orientable Graph 555
13.7 Applications of Directed Graphs 558
13.7.1 Job Sequencing Problem 558
13.7.2 To Design an Efficient Computer Drum 560
13.7.3 Ranking of the Participants in a Tournament 562
Contents xxi
13.8 Network Flows 564
13.9 Improvable Flows 565
13.10 Max-Flow Min-Cut Theorem 567
13.11 k-flow 568
13.12 Tutte’s Problem 569
Summary 571
Suggested Readings 574
14. MATCHING AND COVERING 575–608
14.1 Introduction 575
14.2 Matching and Covering in Bipertite Graphs 577
14.2.1 Covering 582
14.3 Perfect Matching 584
14.4 Factor-critical Graph 588
14.5 Complete Matching 590
14.6 Matrix Method to Find Matching of a Bipertite Graph 592
14.7 Path Covers 595
14.8 Applications 596
14.8.1 The Personnel Assignment Problem 596
14.8.2 The Optimal Assignment Problem 601
14.8.3 Covering to Switching Functions 602
Summary 604
Suggested Readings 607
15. COLOURING OF GRAPHS 609–640
15.1 Introduction 609
15.2 Vertex Colouring 612
15.3 Chromatic Polynomial 613
15.3.1 Bounds of the Chromatic Number 614
15.4 Exams Scheduling Problem 617
15.5 Edge Colouring 625
15.6 List Colouring 630
15.7 Greedy Colouring 631
15.8 Applications 635
15.8.1 The Time Table Problem 635
xxii Contents
15.8.2 Scheduling of Jobs 636
15.8.3 Ramsey Theory 637
15.8.4 Storage Problem 637
Summary 638
Suggested Readings 639
References 641–642
Index 643–648
