An edition of Discrete Mathmatics (2015)

Discrete Mathmatics

  • 1 Want to read

My Reading Lists:

Create a new list

  • 1 Want to read

Buy this book

Last edited by ImportBot
September 22, 2025 | History
An edition of Discrete Mathmatics (2015)

Discrete Mathmatics

  • 1 Want to read

Discrete Mathematics is a textbook designed for the students of computer science engineering, information technology, and computer applications to help them develop the foundation of theoretical computer science.

Publish Date
Language
English
Pages
628

Buy this book

Previews available in: English

Edition Availability
Cover of: Discrete Mathmatics
Discrete Mathmatics
2015, Oxford University Press India
in English

Add another edition?

Book Details


Table of Contents

Features of the Book
Page iv
Preface
Page vii
Brief Contents
Page xiii
Detailed Contents
Page xv
List of Symbols
Page xxv
1. Introduction to Discrete Mathematics and Propositional Logic
Page 1
1.1. Discrete Mathematics: A Brief Introduction
Page 1
1.2. Introduction to Propositional Logic
Page 4
1.3. Proposition
Page 5
1.4. Logical Operators
Page 6
1.4.1. Negation (~)
Page 6
1.4.2. Disjunction (OR/∨)
Page 6
1.4.3. Exclusive OR
Page 7
1.4.4. Conjunction (and/∧)
Page 7
1.4.5. Conditional (→)
Page 8
1.4.6. Biconditional (↔)
Page 10
1.4.7. NAND (↑)
Page 10
1.4.8. NOR (↓)
Page 11
1.4.9. Well-formed Formula
Page 13
1.4.10. Rules of Precedence
Page 13
1.5. Tautology
Page 14
1.6. Contradiction
Page 14
1.7. Logical Equivalence
Page 14
1.8. Tautological Implication
Page 17
1.9. Converse, Inverse, and Contrapositive
Page 18
1.10. Functionally Complete Set of Connectives
Page 18
1.11. Normal Forms
Page 19
1.11.1. Elementary Product
Page 20
1.11.2. Elementary Sum
Page 20
1.11.3. Disjunctive Normal Form
Page 20
1.11.4. Conjunctive Normal Form
Page 21
1.11.5. Principal Disjunctive Normal Form
Page 21
1.11.6. Principal Conjunctive Normal Form
Page 22
1.12. Argument
Page 23
1.12.1. Checking the Validity of an Argument by Constructing Truth Table
Page 24
1.12.2. Checking the Validity of an Argument Without Constructing Truth Table
Page 26
1.13. Predicates
Page 27
1.13.1. Quantifiers
Page 27
1.13.2. Free and Bound Variables
Page 29
1.13.3. Negation of Quantifiers
Page 30
1.13.4. Removing Quantifiers from Predicates
Page 31
1.14. Nested Quantifiers
Page 32
1.14.1. Effect of Order of Quantifiers
Page 32
1.15. Inference Theory of Predicate Calculus
Page 34
1.15.1. Universal Specification
Page 35
1.15.2. Existential Specification
Page 35
1.15.3. Universal Generalization
Page 35
1.15.4. Existential Generalization
Page 36
1.15.5. Substitution
Page 37
1.15.6. First-order and Second-order Logic
Page 37
1.16. Methods of Proof
Page 38
1.16.1. Trivial Proof
Page 38
1.16.2. Vacuous Proof
Page 38
1.16.3. Direct Proof
Page 38
1.16.4. Proof by Contradiction
Page 39
1.16.5. Proof by Contraposition
Page 41
1.16.6. Proof by Cases
Page 42
1.16.7. Exhaustive Proof
Page 43
1.16.8. Proof by Mathematical Induction
Page 43
1.16.9. Proof by Minimal Counter Example
Page 48
1.17. Satisfiability and Consistency
Page 49
1.18. Mechanization of Reasoning
Page 49
1.18.1. Russell's Paradox
Page 50
2. Set Theory
Page 62
2.1. Introduction
Page 62
2.2. Sets
Page 63
2.2.1. Roster Notation
Page 63
2.2.2. Set-builder Notation
Page 63
2.2.3. Cardinality of Sets
Page 64
2.3. Some Standard Sets
Page 65
2.3.1. Empty Set
Page 65
2.3.2. Singleton Set
Page 65
2.3.3. Finite and Infinite Sets
Page 65
2.3.4. Countable and Uncountable Sets
Page 66
2.3.5. Universal Set
Page 66
2.4. Subset and Proper Subset
Page 66
2.5. Equality of Sets
Page 67
2.6. Power Set
Page 68
2.7. Venn Diagrams
Page 68
2.8. Operations on Sets
Page 69
2.8.1. Union
Page 69
2.8.2. Intersection
Page 69
2.8.3. Difference of Two Sets
Page 70
2.8.4. Symmetric Difference of Two Sets
Page 70
2.8.5. Complement of a Set
Page 71
2.8.6. Generalized Union and Intersection
Page 71
2.9. Some Other Classes of Sets
Page 74
2.9.1. Disjoint Sets
Page 74
2.9.2. Partition
Page 74
2.9.3. Ordered Set
Page 74
2.9.4. Cartesian Product of Sets
Page 75
2.10. Algebra of Sets
Page 75
2.11. Multisets
Page 81
2.12. Fuzzy Sets
Page 82
2.12.1. Operations on Fuzzy Sets
Page 83
2.12.2. α-Cut and Strong α-Cut
Page 84
2.12.3. Support, Core, and Height of Fuzzy Sets
Page 85
3. Relations
Page 91
3.1. Introduction
Page 91
3.2. Relation
Page 92
3.2.1. Domain and Range
Page 93
3.2.2. Inverse of Relation
Page 93
3.3. Combining Relations
Page 94
3.3.1. Composition of Relations
Page 95
3.4. Different Types of Relations
Page 96
3.4.1. Reflexive Relation
Page 96
3.4.2. Symmetric Relation
Page 97
3.4.3. Transitive Relation
Page 99
3.4.4. Compatible Relation
Page 101
3.4.5. Equivalence Relation
Page 101
3.4.6. Irreflexive Relation
Page 107
3.4.7. Asymmetric Relation
Page 108
3.4.8. Anti-symmetric Relation
Page 109
3.4.9. Partial Order Relation
Page 111
3.5. Pictorial or Graphical Representation of Relations
Page 112
3.6. Matrix Representation of Relations
Page 113
3.7. Closure of Relations
Page 114
3.7.1. Reflexive Closure
Page 114
3.7.2. Symmetric Closure
Page 114
3.7.3. Transitive Closure
Page 115
3.8. Warshall's Algorithm
Page 115
3.9. n-Ary Relations
Page 118
4. Functions
Page 126
4.1. Introduction
Page 126
4.2. Definition of Function
Page 127
4.3. Relations vs Functions
Page 128
4.4. Types of Functions
Page 130
4.4.1. One-One Function
Page 130
4.4.2. Many-One Function
Page 132
4.4.3. Onto Function
Page 133
4.4.4. Identity Function
Page 136
4.4.5. Constant Function
Page 136
4.4.6. Invertible Function
Page 136
4.5. Composition of Functions
Page 138
4.6. Sum and Product of Functions
Page 142
4.7. Functions Used in Computer Science
Page 143
4.7.1. Floor Function
Page 143
4.7.2. Ceiling Function
Page 144
4.7.3. Remainder Function / Modular Arithmetic
Page 146
4.7.4. Characteristic Function
Page 146
4.7.5. Hash Function
Page 146
4.8. Collision Resolution
Page 148
4.8.1. Open Addressing
Page 148
4.8.2. Chaining
Page 150
4.9. Investigation of Functions
Page 150
5. Properties of Integers
Page 158
5.1. Introduction
Page 158
5.2. Basic Properties of Z
Page 159
5.3. Well-Ordering Principle
Page 161
5.4. Elementary Divisibility Properties
Page 161
5.5. Greatest Common Divisor
Page 164
5.6. Least Common Multiple
Page 167
5.7. Linear Diophantine Equation
Page 168
5.8. Fundamental Theorem of Arithmetic
Page 170
5.8.1. Primes and Composites
Page 171
5.8.2. Relatively Prime Integers
Page 173
5.9. Congruence Relation
Page 173
5.10. Residue Classes
Page 175
5.11. Linear Congruence
Page 176
6. Counting Techniques
Page 185
6.1. Introduction
Page 185
6.2. Basic Counting Principle
Page 186
6.2.1. Sum Rule
Page 186
6.2.2. Product Rule
Page 186
6.2.3. Inclusion-Exclusion Principle
Page 189
6.3. Permutations and Combinations
Page 194
6.3.1. Permutation
Page 195
6.3.2. Combination
Page 198
6.4. Generalized Permutation and Combination
Page 201
6.4.1. Permutation with Repetition
Page 201
6.4.2. Permutations with Identical Objects
Page 202
6.4.3. Combination with Repetition
Page 203
6.5. Binomial Coefficients
Page 206
6.6. Partition
Page 208
6.7. Pigeonhole Principle
Page 211
6.7.1. Generalized Pigeonhole Principle
Page 212
6.8. Arrangements with Forbidden Positions
Page 213
6.8.1. Rook Polynomial
Page 217
6.8.2. Derangement
Page 218
7. Fundamentals of Probability
Page 226
7.1. Introduction
Page 226
7.2. Random Experiment
Page 227
7.3. Sample Space
Page 227
7.4. Event
Page 227
7.4.1. Equally Likely Events
Page 228
7.4.2. Mutually Exclusive Events
Page 229
7.4.3. Exhaustive Events
Page 229
7.4.4. Independent Events
Page 229
7.4.5. Dependent Events
Page 230
7.4.6. Complementary Event
Page 230
7.5. Measurement of Probability
Page 231
7.5.1. Classical or a Priori Approach of Probability
Page 231
7.5.2. Relative Frequency Approach of Probability
Page 231
7.6. Axioms of Probability
Page 234
7.7. Conditional Probability
Page 238
7.8. Bayes' Theorem
Page 247
7.9. Discrete Probability Distributions
Page 248
7.9.1. Expectation of Random Variable
Page 250
7.9.2. Variance and Standard Deviation of Random Variables
Page 251
7.9.3. Binomial Distribution
Page 251
7.9.4. Poisson Distribution
Page 254
7.9.5. Negative Binomial Distribution
Page 256
7.9.6. Geometric Distribution
Page 256
8. Discrete Numeric Functions and Generating Functions
Page 263
8.1. Introduction
Page 263
8.2. Manipulation of Numeric Functions
Page 264
8.2.1. Sum and Product of Two Numeric Functions
Page 264
8.2.2. Multiplication with Scalar
Page 265
8.2.3. Modulus of Numeric Function
Page 265
8.2.4. \(S^i a_r\) and \(S^{-i} a_r\) of Numeric Function
Page 265
8.2.5. Forward and Backward Differences of Numeric Functions
Page 267
8.2.6. Accumulated Sum
Page 268
8.2.7. Convolution of Two Numeric Functions
Page 269
8.3. Generating Functions
Page 274
8.3.1. Properties of Generating Functions
Page 276
8.3.2. Solution of Combinatorial Problems Using Generating Functions
Page 283
9. Recurrence Relations
Page 293
9.1. Introduction
Page 293
9.2. Recursive Definition
Page 294
9.2.1. Recursively Defined Functions
Page 295
9.2.2. Recursively Defined Sets
Page 295
9.3. Recurrence Relation
Page 296
9.4. Solution of Recurrence Relations
Page 298
9.4.1. Iterative Method
Page 298
9.4.2. Recursive Method
Page 301
9.4.3. Generating Function
Page 305
9.5. Structural Induction
Page 306
9.6. Order and Degree of Recurrence Relations
Page 306
9.7. Linear Recurrence Relation with Constant Coefficients
Page 307
9.7.1. Linear Homogeneous Recurrence Relation with Constant Coefficients
Page 307
9.7.2. Linear Non-homogeneous Recurrence Relation with Constant Coefficients
Page 310
10. Algebraic Structures
Page 322
10.1. Introduction
Page 322
10.2. Binary Operations
Page 322
10.2.1. Semi-Group
Page 324
10.2.2. Monoid
Page 325
10.2.3. Group
Page 326
10.3. Addition and Multiplication Modulo m
Page 330
10.4. Subgroup
Page 331
10.4.1. Cosets
Page 333
10.5. Permutations and Symmetric Group
Page 335
10.5.1. Cyclic Permutation
Page 336
10.5.2. Stabilizer of an Element
Page 337
10.5.3. Orbit of an Element
Page 337
10.5.4. Invariant Elements under Permutation
Page 337
10.6. Cyclic Group
Page 339
10.7. Normal Subgroup
Page 343
10.8. Quotient Group
Page 345
10.9. Dihedral Group
Page 345
10.10. Homomorphism and Isomorphism
Page 346
10.10.1. Kernel of Homomorphism
Page 347
10.11. Ring
Page 349
10.11.1. Commutative Ring
Page 350
10.11.2. Ring with Unity
Page 350
10.11.3. Zero Divisor of a Ring
Page 351
10.11.4. Subrings
Page 351
10.11.5. Ring Homomorphism
Page 351
10.12. Integral Domain
Page 351
10.13. Division Ring or Skew Field
Page 352
10.14. Field
Page 352
10.15. Polynomial Ring
Page 354
10.16. Boolean Algebra
Page 354
10.16.1. Duality
Page 356
10.16.2. Boolean Functions
Page 358
10.16.3. Simplification of Boolean Functions
Page 358
10.16.4. Canonical Form
Page 359
10.16.5. Standard Form
Page 361
10.16.6. Other Logic Operations
Page 362
10.16.7. Karnaugh Map
Page 362
10.16.8. Quine–McCluskey Method
Page 366
10.16.9. Free Boolean Algebra
Page 368
11. Posets and Lattices
Page 374
11.1. Introduction
Page 374
11.2. Partially Ordered Set
Page 375
11.3. Diagrammatic Representation of Poset (Hasse Diagram)
Page 375
11.4. Elements in Posets
Page 376
11.4.1. Least and Greatest Elements
Page 377
11.4.2. Minimal and Maximal Elements
Page 377
11.4.3. Lower and Upper Bounds
Page 377
11.4.4. Greatest Lower Bound and Least Upper Bound
Page 377
11.5. Linearly Ordered Set
Page 380
11.6. Well-Ordered Set
Page 380
11.7. Product Order
Page 381
11.8. Lexicographic Order
Page 382
11.9. Topological Sorting and Consistent Enumeration
Page 383
11.10. Isomorphism
Page 384
11.11. Lattices
Page 386
11.12. Properties of Lattices
Page 386
11.12.1. Principle of Duality
Page 387
11.12.2. Sublattice
Page 390
11.13. Some Special Lattices
Page 390
11.13.1. Modular Lattice
Page 390
11.13.2. Distributive Lattice
Page 391
11.13.3. Bounded Lattice
Page 392
11.13.4. Complemented Lattice
Page 395
11.13.5. Complete Lattice
Page 396
11.14. Product of Lattices
Page 396
11.15. Lattice Homomorphism
Page 396
11.16. Boolean Algebra and Lattices
Page 397
11.17. Stone's Representation Theorem
Page 399
12. Formal Languages and Finite Automata
Page 409
12.1. Introduction
Page 409
12.2. Alphabet and Words
Page 409
12.3. Language
Page 410
12.4. Operations on Languages
Page 410
12.5. Finite Automata
Page 411
12.5.1. Deterministic Finite State Automata
Page 412
12.5.2. Non-Deterministic Finite Automata
Page 416
12.5.3. Conversion From Non-Deterministic Finite Automata to Deterministic Finite Automata
Page 418
12.5.4. Minimization of Finite Automata
Page 421
12.6. Finite Automata with Outputs
Page 423
12.6.1. Mealy Machine
Page 423
12.6.2. Moore Machine
Page 425
12.6.3. Equivalence of Mealy and Moore Machines
Page 426
12.6.4. Conversion From Mealy to Moore Machine
Page 426
12.6.5. Conversion From Moore to Mealy Machine
Page 428
12.7. Regular Expression
Page 430
12.8. Regular Expression and Finite Automata
Page 432
12.9. Generalized Transition Graph
Page 439
12.10. Grammar of Formal Languages
Page 440
12.10.1. Phrase Structure Grammar
Page 440
12.10.2. Chomsky Hierarchy
Page 442
12.11. Other Machines
Page 443
13. Graph Theory
Page 453
13.1. Introduction
Page 453
13.2. Graph and its Related Definitions
Page 454
13.3. Different Types of Graphs
Page 457
13.3.1. Simple Graph
Page 457
13.3.2. Multigraph, Trivial Graph, and Null Graph
Page 457
13.3.3. Complete Graph
Page 457
13.3.4. Regular Graph
Page 457
13.3.5. Bipartite Graph
Page 458
13.3.6. Weighted Graph
Page 458
13.4. Subgraphs
Page 459
13.5. Operations on Graphs
Page 460
13.5.1. Union of Two Graphs
Page 460
13.5.2. Intersection of Two Graphs
Page 461
13.5.3. Ring Sum of Two Graphs
Page 461
13.5.4. Decomposition of a Graph
Page 461
13.5.5. Deletion of a Vertex
Page 461
13.5.6. Deletion of an Edge
Page 462
13.5.7. Complement of a Graph
Page 462
13.6. Walk, Path, and Circuit
Page 462
13.6.1. Walk
Page 463
13.6.2. Path
Page 463
13.6.3. Circuit
Page 463
13.7. Connected Graph, Disconnected Graph, and Components
Page 463
13.8. Homomorphism and Isomorphism of Graphs
Page 466
13.9. Homeomorphic Graphs
Page 467
13.10. Euler and Hamiltonian Graphs
Page 468
13.10.1. Euler Line and Euler Graph
Page 468
13.10.2. Hamiltonian Path and Hamiltonian Circuit
Page 469
13.10.3. Travelling Salesman Problem
Page 469
13.11. Planar Graph
Page 470
13.11.1. Kuratowski's Two Graphs
Page 470
13.11.2. Region and its Degree
Page 471
13.11.3. Euler's Formula
Page 471
13.12. Tree
Page 472
13.12.1. Rooted Tree
Page 473
13.12.2. Binary Tree
Page 473
13.12.3. Height of Binary Tree
Page 475
13.12.4. Spanning Tree
Page 476
13.12.5. Branch and Chord
Page 476
13.12.6. Rank and Nullity
Page 476
13.12.7. Fundamental Circuits
Page 477
13.12.8. Finding All Spanning Trees of a Graph
Page 477
13.12.9. Spanning Trees in a Weighted Graph
Page 477
13.12.10. Kruskal's Algorithm
Page 478
13.12.11. Prim's Algorithm
Page 479
13.12.12. Dijkstra Algorithm
Page 479
13.12.13. Binary Search Tree
Page 482
13.13. Cut Set and Cut Vertex
Page 482
13.14. Colouring of Graphs
Page 484
13.14.1. Chromatic Number
Page 484
13.14.2. Chromatic Partitioning
Page 485
13.14.3. Independence Set and Maximal Independence Set
Page 485
13.14.4. Maximum Independence Set and Independence Number
Page 485
13.14.5. Clique and Maximal Clique
Page 485
13.14.6. Maximum Clique and Clique Number
Page 486
13.14.7. Perfect Graph
Page 486
13.14.8. Chromatic Polynomial
Page 486
13.14.9. Applications of Graph Colouring
Page 488
13.15. Matching
Page 489
13.15.1. Maximal Matching, Maximum Matching, and Matching Number
Page 489
13.15.2. Perfect Matching
Page 489
13.16. Matrix Representation of Graphs
Page 490
13.16.1. Incidence Matrix
Page 490
13.16.2. Circuit Matrix
Page 491
13.16.3. Cut Set Matrix
Page 492
13.16.4. Path Matrix
Page 493
13.16.5. Adjacency Matrix
Page 494
13.17. Traversal of Graphs
Page 494
13.17.1. Breadth-First Search
Page 494
13.17.2. Depth-First Search
Page 496
13.18. Traversing Binary Trees
Page 498
13.18.1. Pre-Order Traversal
Page 498
13.18.2. In-Order Traversal
Page 498
13.18.3. Post-Order Traversal
Page 499
13.19. Digraph or Directed Graph
Page 499
13.20. Network Flow
Page 500
13.20.1. Cut in a Transport Network
Page 501
13.20.2. Flow Augmenting Path
Page 503
13.21. Enumeration of Graphs
Page 505
14. Applications of Discrete Mathematical Structures
Page 523
14.1. Introduction
Page 523
14.2. Asymptotic Behaviour of Numeric Functions
Page 524
14.2.1. Big-Oh (O) Notation
Page 524
14.2.2. Omega (Ω) Notation
Page 529
14.2.3. Theta (Θ) Notation
Page 529
14.3. Analysis of Algorithms
Page 530
14.3.1. Space Complexity
Page 530
14.3.2. Time Complexity
Page 531
14.4. Analysis of Sorting Algorithms
Page 534
14.4.1. Insertion Sort
Page 534
14.4.2. Bubble Sort
Page 537
14.4.3. Selection Sort
Page 539
14.5. Divide-and-Conquer Approach
Page 542
14.5.1. Merge Sort
Page 542
14.5.2. Quick Sort
Page 548
14.6. Analysis of Searching Algorithms
Page 552
14.6.1. Linear Search
Page 552
14.6.2. Binary Search
Page 553
14.7. Tractable and Intractable Problems
Page 555
14.8. Logic Gates
Page 556
14.8.1. Switching Circuits and Logic Gates
Page 557
14.8.2. NAND and NOR Implementations
Page 558
14.9. Combinational Circuits
Page 560
14.9.1. Half Adder
Page 561
14.9.2. Full Adder
Page 561
14.9.3. Half Subtractor
Page 563
14.9.4. Full Subtractor
Page 563
14.10. Information and Coding Theory
Page 565
14.10.1. Discrete Information Sources
Page 565
14.10.2. Entropy
Page 566
14.10.3. Mutual Information
Page 567
14.10.4. Coding Theory
Page 567
14.10.5. Hamming Distance
Page 567
14.10.6. Error-Detecting and Error-Correcting Codes
Page 568
14.10.7. Group Codes
Page 573
14.10.8. Generator Matrices
Page 575
14.10.9. Parity Check Matrices
Page 576
14.10.10. Coset Decoding
Page 578
14.10.11. Prefix Codes
Page 578
14.10.12. Cyclic Code
Page 579
Appendices
Page 585
Bibliography
Page 593
Index
Page 594
About the Authors
Page 601

Classifications

Library of Congress
QA76.9.M35

Edition Identifiers

Open Library
OL28588349M
Internet Archive
discretemathemat0000bish_0
ISBN 13
9780199452798
OCLC/WorldCat
928929389

Work Identifiers

Work ID
OL21119900W

Community Reviews (0)

No community reviews have been submitted for this work.

Lists

History

Download catalog record: RDF / JSON
September 22, 2025 Edited by ImportBot import existing book
December 19, 2022 Edited by MARC Bot import existing book
August 4, 2020 Created by ImportBot import new book