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.
Author(s): Santosh Kumar Yadav
Edition: 1
Publisher: Springer
Year: 2023
Language: English
Commentary: Publisher PDF | Classifiers were derived from "Discrete Mathematics" by Norman L. Biggs (ISBN: 9780198507178).
Pages: 668
City: Cham
Tags: Euclid's Algorithm; Euclid's Theorem; Congruence Modulo M; Chinese Remainder Theorem; Fermat’s Theorem; Euler’s Theorem; Set Ordinary Difference; Disjoint Set; Venn Diagrams; De-Morgan’s Laws; The Binomial Theorem
Preface
Acknowledgments
Contents
0 Preliminaries
0.1 Numbers
0.2 Euclid’s Algorithm
0.3 Fundamental Theorem of Arithmetic
0.4 Euclid’s Theorem
0.5 Congruence Modulo m
0.6 Chinese Remainder Theorem
0.7 Fermat’s and Euler Theorems
0.8 Exponents and Logarithms
0.9 Sums
0.10 Mapping
Suggested Readings
1
The Language of Sets
1.1 Introduction
1.2 Elements and Notations of Sets
1.3 Construction of Sets
1.4 Types of Sets
1.5 Set Operations
1.5.1 Intersection of Sets
1.5.2 Union of Sets
1.5.3 Disjoint Set (Mutually Exclusive)
1.5.4 Ordinary Difference of Sets (A – B)
1.5.5 Complementation of Sets
1.5.6 Universal Set and its Complement
1.5.7 Symmetric Difference (Boolean Sum)
1.6 Venn Diagrams
1.7 Some Basic Results
1.8 Properties of Set Operations
1.8.1 Properties of Intersection on Sets
1.8.2 Properties of Union on Sets
1.8.3 Number of Elements in a Union of Two or more Sets
1.9 De-Morgan’s Laws
1.10 General form of Principle of Inclusion and Exclusion
Summary
Suggested Readings
2
Basic Combinatorics
2.1 Introduction
2.2 Basic Counting Principles
2.2.1 The Principle of Disjunctive Counting (Sum Rule)
2.2.2 The Principle of Sequential Counting (Product Rule)
2.3 Factorial
2.4 Permutation and Combination
2.4.1 Cyclic Permutation
2.4.2 Pascal’s Identity
2.4.3 Vandermonde’s Identity
2.4.4 Pigeonhole Principle
2.4.5 Inclusion–Exclusion Principle
2.5 The Binomial Theorem
2.6 nth Catalan Number
2.7 Principle of Mathematical Induction (P.M.I)
2.8 Recurrence Relations
Summary
Suggested Readings
3
Mathematical Logic
3.1 Introduction
3.2 Propositions (Statements)
3.3 Connectives
3.3.1 Negation
3.3.2 Conjunction
3.3.3 Disjunction
3.3.4 Conditional
3.3.5 Biconditional
3.4 Equivalence of Formulae
3.5 Well-Formed Formulae (WFF)
3.6 Tautologies
3.7 Principle of Duality
3.8 Two State Devices
3.9 The Relay-Switching Devices
3.10 Logic Gates and Modules
3.10.1 OR, AND and NOT Gates
3.10.2 Two-Level Networks
3.10.3 NOR and NAND Gates
3.11 Normal Forms (Decision Problems)
3.11.1 Disjunctive Normal Form (DNF)
3.11.2 Conjunctive Normal Form (CNF)
3.11.3 Principal Disjunctive Normal Form (PDNF)
3.11.4 Principal Conjuctive Normal Forms (PCNF)
3.12 Rules of Inference
3.13 Automatic Proving System (Theorems)
3.14 The Predicate Calculus
3.14.1 Statement Functions, Variables and Quantifiers
3.14.2 Free and Bound Variables
3.14.3 Special Valid Formulae using Quantifiers
3.14.4 Theory of Inference for the Predicate Calculus
3.14.5 Formulae Involving More than One Quantifier
Summary
Suggested Readings
4
Relations
4.1 Introduction
4.2 Product Sets
4.3 Partitions
4.4 Relations
4.5 Binary Relations in a Set
4.6 Domain and Range of a Relation
4.6.1 Number of Distinct Relation From set A to B
4.6.2 Solution sets and Graph of Relations
4.6.3 Relation as Sets of Ordered Pairs
4.7 The Matrix of a Relation and Digraphs
4.8 Paths in Relations and Digraphs
4.9 Boolean Matrices
4.9.1 Boolean Operations AND and OR
4.9.2 Joint and Meet
4.9.3 Boolean Product
4.9.4 Boolean Power of a Boolean Matrix
4.10 Adjacency Matrix of a Relation
4.11 Gray Code
4.12 Properties of Relations
4.12.1 Reflexive and Irreflexive Relations
4.12.2 Symmetric, Asymmetric and Antisymmetric Relations
4.12.3 Transitive Relation
4.13 Equivalence Relations
4.14 Closure of Relations
4.15 Manipulation and Composition of Relations
4.16 Warshall's Algorithm
4.17 Partial Order Relation
4.17.1 Totally Ordered Set
4.17.2 Lexicographic Order
4.17.3 Hasse Diagrams
Summary
Suggested Readings
5
Functions
5.1 Introduction
5.1.1 Sum and Product of Functions
5.2 Special Types of Functions
5.2.1 Polynomial Function
5.2.2 Exponential and Logarithmic Function
5.2.3 Floor and Ceiling Functions
5.2.4 Transcedental Function
5.2.5 Identity Function
5.2.6 Integer Value and Absolute Value Functions
5.2.7 Remainder Function
5.3 Composition of Functions
5.4 Inverse of a Function
5.5 HASHING FUNCTIONS
5.6 Countable and Uncountable Sets
5.7 Characteristic Function of A Set
5.8 Permutation Function
5.9 Growth of Functions
5.10 The Relation Θ
Summary
Suggested Readings
6
Lattice Theory
6.1 Introduction
6.2 Partial Ordered Sets
6.2.1 Some Important Terms
6.2.2 Diagramatical Representation of a Poset (Hasse Diagram)
6.2.3 Isomorphism
6.2.4 Duality
6.2.5 Product of two Posets
6.3 Lattices as Posets
6.3.1 Some Properties of Lattices
6.3.2 Lattices as Algebraic Systems
6.3.3 Complete Lattice
6.3.4 Bounded Lattice
6.3.5 Sublattices
6.3.6 Ideals of Lattices
6.4 Modular and Distributive Lattices
Summary
Suggested Readings
7
Boolean Algebras and Applications
7.1 Introduction
7.2 Boolean Algebra (Analytic Approach)
7.2.1 Sub-Boolean Algebra
7.2.2 Boolean Homomorphism
7.3 Boolean Functions
7.3.1 Equality of Boolean Expressions
7.3.2 Minterms and Maxterms
7.3.3 Functional Completeness
7.3.4 NAND and NOR
7.4 Combinatorial Circuits (Synthesis of Circuits)
7.4.1 Half-Adder and Full-Adder
7.4.2 Equivalent Combinatorial Circuits
7.5 Karnaugh Map
7.5.1 Don’t Care Conditions
7.5.2 Minimization Process
7.6 Finite State Machines
Summary
Suggested Readings
8
Fuzzy Algebra
8.1 Introduction
8.2 Crisp Sets and Fuzzy Sets
8.3 Some Useful Definitions
8.4 Operations of Fuzzy Sets
8.5 Interval-Valued Fuzzy Sets (I-V Fuzzy Sets)
8.5.1 Union and Intersection of two I–V Fuzzy Sets
8.6 Fuzzy Relations
8.6 Fuzzy Measures
8.7.1 Belief and Plausibility Measures
8.7.2 Probability Measure
8.7.3 Uncertainty and Measures of Fuzziness
8.7.4 Uncertainty and Information
8.8 Applications of Fuzzy Algebras
8.8.1 Natural, Life and Social Sciences
8.8.2 Engineering
8.8.3 Medical Sciences
8.8.4 Management Sciences and Decision Making Process
8.8.5 Computer Science
8.9 Uniqueness of Uncertainty Measures
8.9.1 Shannon’s Entropy
8.9.2 U-uncertainty
8.9.3 Uniqueness of the U-uncertainty for Two-Value Possibility Distributions
Summary
Suggested Readings
9 Formal Languages and Automata Theory
9.1 Introduction
9.2 Formal Languages
9.2.1 Equality of Words
9.2.2 Concatenation of Languages
9.2.3 Kleene Closure
9.3 Grammars
9.3.1 Phase-structure Grammar
9.3.2 Derivations of Grammar
9.3.3 Backus-Normal Form (BNF) or Backus Naur Form
9.3.4 Chomsky Grammar
9.3.5 Ambiguous Grammar
9.4 Finite-State Automation (FSA)
9.4.1 Counting to Five
9.4.2 Process of Getting up in the Morning (Alarm)
9.4.3 Traffic Light
9.4.4 Vending Machine
9.5 Finite-State Machine (FSM)
9.6 Finite-State Automata
9.6.1 Deterministic Finite-State Automata (DFSA)
9.6.2 Nondeterministic Finite-State Automata
9.6.3 Equivalent Nondeterministic Finite State Automata
Summary
Suggested Readings
10
The Basics of Graph Theory
10.1 Introduction
10.2 Graph! What is it?
10.2.1 Simple Graph
10.2.2 Graph
10.2.3 Loops
10.2.4 Degree of Vertices
10.2.5 Equivalence Relation
10.2.6 Random Graph Model
10.2.7 Isolated Vertex, Pendent Vertex and Null Graph
10.3 Digraphs
10.4 Path, Trail, Walk and Vertex Sequence
10.5 Subgraph
10.6 Circuit and Cycle
10.7 Cycles and Multiple Paths
10.8 Connected Graph
10.9 Spanning Subgraph and Induced Subgraph
10.10 Eulerian Graph (Eulerian Trail and Circuit)
10.11 Hamiltonian Graph
10.12 Biconnected Graph
10.13 Algebraic terms and operations used in Graph Theory
10.13.1 Graphs Isomorphism
10.13.2 Union of two Graphs
10.13.3 Intersection of two Graphs
10.13.4 Addition of two Graphs
10.13.5 Direct Sum or Ring Sum of two Graphs
10.13.6 Product of two Graphs
10.13.7 Composition of two Graphs
10.13.8 Complement of a Graph
10.13.9 Fusion of a Graph
10.13.10 Rank and Nullity
10.13.11 Adjacency Matrix
10.13.12 Some Important Theorems
10.14 Some Popular Problems in Graph Theory
10.14.1 Tournament Ranking Problem
10.14.2 The Königsberg Bridge Problem
10.14.3 Four Colour Problem
10.14.4 Three Utilities Problem
10.14.5 Traveling - Salesman Problem
10.14.6 MTNL’S Networking Problem
10.14.7 Electrical Network Problems
10.14.8 Satellite Channel Problem
10.15 Applications of Graphs
Summary
Suggested Readings
11
Trees
11.1 Introduction
11.2 Definitions of a Tree
11.3 Forest
11.4 Rooted Graph
11.5 Parent, Child, Sibling and Leaf
11.6 Rooted Plane Tree
11.7 Binary Trees
11.8 Spanning Trees
11.9 Breadth – First Search and Depth – First Search (BFS and DFS)
11.10 Minimal Spanning Trees
11.10.1 Kruskal’s Algorithm (for Finding a Minimal Spanning Tree)
11.10.2 Prim’s Algorithm
11.11 Directed Trees
Summary
Suggested Readings
12
Planar Graphs
12.1 Introduction
12.2 Geometrical Representation of Graphs
12.3 Bipertite Graph
12.4 Homeomorphic Graph
12.5 Kuratowski’s Graphs
12.6 Dual Graphs
12.7 Euler’s Formula
12.8 Outerplanar Graphs
12.8.1 k-outerplanar Graphs
Summary
Suggested Readings
13
Directed Graphs
13.1 Introduction
13.2 Directed Paths
13.3 Tournament
13.4 Directed Cycles
13.5 Acyclic Graph
13.6 Di-Orientable Graph
13.7 Applications of Directed Graphs
13.7.1 Job Sequencing Problem
13.7.2 To Design an Efficient Computer Drum
13.7.3 Ranking of the Participants in a Tournament
13.8 Network Flows
13.9 Improvable Flows
13.10 Max-Flow Min-Cut Theorem
13.11 k-flow
13.12 Tutte’s Problem
Summary
Suggested Readings
14
Matching and Covering
14.1 Introduction
14.2 Matching and Covering in Bipertite Graphs
14.2.1 Covering
14.3 Perfect Matching
14.4 Factor-critical Graph
14.5 Complete Matching
14.6 Matrix Method to Find Matching of a Bipertite Graph
14.7 Path Covers
14.8 Applications
14.8.1 The Personnel Assignment Problem
14.8.2 The Optimal Assignment Problem
14.8.3 Covering to Switching Functions
Summary
Suggested Readings
15
Colouring of Graphs
15.1 Introduction
15.2 Vertex Colouring
15.3 Chromatic Polynomial
15.3.1 Bounds of the Chromatic Number
15.4 Exams Scheduling Problem
15.5 Edge Colouring
15.6 List Colouring
15.7 Greedy Colouring
15.8 Applications
15.8.1 The Time Table Problem
15.8.2 Scheduling of Jobs
15.8.3 Ramsey Theory
15.8.4 Storage Problem
Summary
Suggested Readings
References
Index
