Overview

This 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.

Full Product Details

Author:   Santosh Kumar Yadav
Publisher:   Springer International Publishing AG
Imprint:   Springer International Publishing AG
Edition:   1st ed. 2023
Weight:   1.420kg
ISBN:  

9783031213205

ISBN 10:   3031213203
Pages:   648
Publication Date:   15 July 2023
Audience:   Professional and scholarly ,  Professional & Vocational
Format:   Hardback
Publisher's Status:   Active
Availability:   Manufactured on demand  
We will order this item for you from a manufactured on demand supplier.
Language:   English

Table of Contents

0. 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​

Reviews

Author Information

Dr. Santosh Kumar Yadav has been associated with academic and research activities for more than 25 years. He has been an active and dynamic administrator as the director (Academic and Research) at J.J.T. University, Rajasthan. As an academician, he has taught undergraduates and postgraduate classes in different premier institutions including various colleges of Delhi University in different capacities.

Tab Content 6

Author Website:  

Customer Reviews

Recent Reviews

No review item found!

Add your own review!

Countries Available

All regions