It looks like you're offline.

An edition of Discrete Mathmatics (2015)

Discrete Mathmatics

by R. K. Bisht and H. S. Dhami

1 Want to read

Cover of: Discrete Mathmatics by R. K. Bisht, H. S. Dhami, R. K. Bisht, H. S. Dhami

Preview

Borrow

My Reading Lists:

Use this Work

Create a new list

1 Want to read

Check nearby libraries

WorldCat

Buy this book

Last edited by ImportBot

September 22, 2025 | History

Edit

An edition of Discrete Mathmatics (2015)

Discrete Mathmatics

by R. K. Bisht and H. S. Dhami

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

2015

Publisher

Oxford University Press India

Language

English

Pages

628

Check nearby libraries

WorldCat

Buy this book

Previews available in: English

Edition	Availability
1 Discrete Mathmatics 2015, Oxford University Press India in English 0199452792 9780199452798	aaaa Borrow Listen Locate

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

1.1. Discrete Mathematics: A Brief Introduction

1.2. Introduction to Propositional Logic

1.3. Proposition

1.4. Logical Operators

1.4.1. Negation (~)

1.4.2. Disjunction (OR/∨)

1.4.3. Exclusive OR

1.4.4. Conjunction (and/∧)

1.4.5. Conditional (→)

1.4.6. Biconditional (↔)

1.4.7. NAND (↑)

1.4.8. NOR (↓)

1.4.9. Well-formed Formula

1.4.10. Rules of Precedence

1.6. Contradiction

1.7. Logical Equivalence

1.8. Tautological Implication

1.9. Converse, Inverse, and Contrapositive

1.10. Functionally Complete Set of Connectives

1.11. Normal Forms

1.11.1. Elementary Product

1.11.2. Elementary Sum

1.11.3. Disjunctive Normal Form

1.11.4. Conjunctive Normal Form

1.11.5. Principal Disjunctive Normal Form

1.11.6. Principal Conjunctive Normal Form

1.12.1. Checking the Validity of an Argument by Constructing Truth Table

1.12.2. Checking the Validity of an Argument Without Constructing Truth Table

1.13. Predicates

1.13.1. Quantifiers

1.13.2. Free and Bound Variables

1.13.3. Negation of Quantifiers

1.13.4. Removing Quantifiers from Predicates

1.14. Nested Quantifiers

1.14.1. Effect of Order of Quantifiers

1.15. Inference Theory of Predicate Calculus

1.15.1. Universal Specification

1.15.2. Existential Specification

1.15.3. Universal Generalization

1.15.4. Existential Generalization

1.15.5. Substitution

1.15.6. First-order and Second-order Logic

1.16. Methods of Proof

1.16.1. Trivial Proof

1.16.2. Vacuous Proof

1.16.3. Direct Proof

1.16.4. Proof by Contradiction

1.16.5. Proof by Contraposition

1.16.6. Proof by Cases

1.16.7. Exhaustive Proof

1.16.8. Proof by Mathematical Induction

1.16.9. Proof by Minimal Counter Example

1.17. Satisfiability and Consistency

1.18. Mechanization of Reasoning

1.18.1. Russell's Paradox

2.1. Introduction

2.2.1. Roster Notation

2.2.2. Set-builder Notation

2.2.3. Cardinality of Sets

2.3. Some Standard Sets

2.3.1. Empty Set

2.3.2. Singleton Set

2.3.3. Finite and Infinite Sets

2.3.4. Countable and Uncountable Sets

2.3.5. Universal Set

2.4. Subset and Proper Subset

2.5. Equality of Sets

2.7. Venn Diagrams

2.8. Operations on Sets

2.8.2. Intersection

2.8.3. Difference of Two Sets

2.8.4. Symmetric Difference of Two Sets

2.8.5. Complement of a Set

2.8.6. Generalized Union and Intersection

2.9. Some Other Classes of Sets

2.9.1. Disjoint Sets

2.9.2. Partition

2.9.3. Ordered Set

2.9.4. Cartesian Product of Sets

2.10. Algebra of Sets

2.11. Multisets

2.12. Fuzzy Sets

2.12.1. Operations on Fuzzy Sets

2.12.2. α-Cut and Strong α-Cut

2.12.3. Support, Core, and Height of Fuzzy Sets

3.1. Introduction

3.2.1. Domain and Range

3.2.2. Inverse of Relation

3.3. Combining Relations

3.3.1. Composition of Relations

3.4. Different Types of Relations

3.4.1. Reflexive Relation

3.4.2. Symmetric Relation

3.4.3. Transitive Relation

3.4.4. Compatible Relation

3.4.5. Equivalence Relation

3.4.6. Irreflexive Relation

3.4.7. Asymmetric Relation

3.4.8. Anti-symmetric Relation

3.4.9. Partial Order Relation

3.5. Pictorial or Graphical Representation of Relations

3.6. Matrix Representation of Relations

3.7. Closure of Relations

3.7.1. Reflexive Closure

3.7.2. Symmetric Closure

3.7.3. Transitive Closure

3.8. Warshall's Algorithm

3.9. n-Ary Relations

4.1. Introduction

4.2. Definition of Function

4.3. Relations vs Functions

4.4. Types of Functions

4.4.1. One-One Function

4.4.2. Many-One Function

4.4.3. Onto Function

4.4.4. Identity Function

4.4.5. Constant Function

4.4.6. Invertible Function

4.5. Composition of Functions

4.6. Sum and Product of Functions

4.7. Functions Used in Computer Science

4.7.1. Floor Function

4.7.2. Ceiling Function

4.7.3. Remainder Function / Modular Arithmetic

4.7.4. Characteristic Function

4.7.5. Hash Function

4.8. Collision Resolution

4.8.1. Open Addressing

4.8.2. Chaining

4.9. Investigation of Functions

5. Properties of Integers

5.1. Introduction

5.2. Basic Properties of Z

5.3. Well-Ordering Principle

5.4. Elementary Divisibility Properties

5.5. Greatest Common Divisor

5.6. Least Common Multiple

5.7. Linear Diophantine Equation

5.8. Fundamental Theorem of Arithmetic

5.8.1. Primes and Composites

5.8.2. Relatively Prime Integers

5.9. Congruence Relation

5.10. Residue Classes

5.11. Linear Congruence

6. Counting Techniques

6.1. Introduction

6.2. Basic Counting Principle

6.2.1. Sum Rule

6.2.2. Product Rule

6.2.3. Inclusion-Exclusion Principle

6.3. Permutations and Combinations

6.3.1. Permutation

6.3.2. Combination

6.4. Generalized Permutation and Combination

6.4.1. Permutation with Repetition

6.4.2. Permutations with Identical Objects

6.4.3. Combination with Repetition

6.5. Binomial Coefficients

6.7. Pigeonhole Principle

6.7.1. Generalized Pigeonhole Principle

6.8. Arrangements with Forbidden Positions

6.8.1. Rook Polynomial

6.8.2. Derangement

7. Fundamentals of Probability

7.1. Introduction

7.2. Random Experiment

7.3. Sample Space

7.4.1. Equally Likely Events

7.4.2. Mutually Exclusive Events

7.4.3. Exhaustive Events

7.4.4. Independent Events

7.4.5. Dependent Events

7.4.6. Complementary Event

7.5. Measurement of Probability

7.5.1. Classical or a Priori Approach of Probability

7.5.2. Relative Frequency Approach of Probability

7.6. Axioms of Probability

7.7. Conditional Probability

7.8. Bayes' Theorem

7.9. Discrete Probability Distributions

7.9.1. Expectation of Random Variable

7.9.2. Variance and Standard Deviation of Random Variables

7.9.3. Binomial Distribution

7.9.4. Poisson Distribution

7.9.5. Negative Binomial Distribution

7.9.6. Geometric Distribution

8. Discrete Numeric Functions and Generating Functions

8.1. Introduction

8.2. Manipulation of Numeric Functions

8.2.1. Sum and Product of Two Numeric Functions

8.2.2. Multiplication with Scalar

8.2.3. Modulus of Numeric Function

8.2.4. \(S^i a_r\) and \(S^{-i} a_r\) of Numeric Function

8.2.5. Forward and Backward Differences of Numeric Functions

8.2.6. Accumulated Sum

8.2.7. Convolution of Two Numeric Functions

8.3. Generating Functions

8.3.1. Properties of Generating Functions

8.3.2. Solution of Combinatorial Problems Using Generating Functions

9. Recurrence Relations

9.1. Introduction

9.2. Recursive Definition

9.2.1. Recursively Defined Functions

9.2.2. Recursively Defined Sets

9.3. Recurrence Relation

9.4. Solution of Recurrence Relations

9.4.1. Iterative Method

9.4.2. Recursive Method

9.4.3. Generating Function

9.5. Structural Induction

9.6. Order and Degree of Recurrence Relations

9.7. Linear Recurrence Relation with Constant Coefficients

9.7.1. Linear Homogeneous Recurrence Relation with Constant Coefficients

9.7.2. Linear Non-homogeneous Recurrence Relation with Constant Coefficients

10. Algebraic Structures

10.1. Introduction

10.2. Binary Operations

10.2.1. Semi-Group

10.3. Addition and Multiplication Modulo m

10.5. Permutations and Symmetric Group

10.5.1. Cyclic Permutation

10.5.2. Stabilizer of an Element

10.5.3. Orbit of an Element

10.5.4. Invariant Elements under Permutation

10.6. Cyclic Group

10.7. Normal Subgroup

10.8. Quotient Group

10.9. Dihedral Group

10.10. Homomorphism and Isomorphism

10.10.1. Kernel of Homomorphism

10.11.1. Commutative Ring

10.11.2. Ring with Unity

10.11.3. Zero Divisor of a Ring

10.11.4. Subrings

10.11.5. Ring Homomorphism

10.12. Integral Domain

10.13. Division Ring or Skew Field

10.15. Polynomial Ring

10.16. Boolean Algebra

10.16.1. Duality

10.16.2. Boolean Functions

10.16.3. Simplification of Boolean Functions

10.16.4. Canonical Form

10.16.5. Standard Form

10.16.6. Other Logic Operations

10.16.7. Karnaugh Map

10.16.8. Quine–McCluskey Method

10.16.9. Free Boolean Algebra

11. Posets and Lattices

11.1. Introduction

11.2. Partially Ordered Set

11.3. Diagrammatic Representation of Poset (Hasse Diagram)

11.4. Elements in Posets

11.4.1. Least and Greatest Elements

11.4.2. Minimal and Maximal Elements

11.4.3. Lower and Upper Bounds

11.4.4. Greatest Lower Bound and Least Upper Bound

11.5. Linearly Ordered Set

11.6. Well-Ordered Set

11.7. Product Order

11.8. Lexicographic Order

11.9. Topological Sorting and Consistent Enumeration

11.10. Isomorphism

11.11. Lattices

11.12. Properties of Lattices

11.12.1. Principle of Duality

11.12.2. Sublattice

11.13. Some Special Lattices

11.13.1. Modular Lattice

11.13.2. Distributive Lattice

11.13.3. Bounded Lattice

11.13.4. Complemented Lattice

11.13.5. Complete Lattice

11.14. Product of Lattices

11.15. Lattice Homomorphism

11.16. Boolean Algebra and Lattices

11.17. Stone's Representation Theorem

12. Formal Languages and Finite Automata

12.1. Introduction

12.2. Alphabet and Words

12.4. Operations on Languages

12.5. Finite Automata

12.5.1. Deterministic Finite State Automata

12.5.2. Non-Deterministic Finite Automata

12.5.3. Conversion From Non-Deterministic Finite Automata to Deterministic Finite Automata

12.5.4. Minimization of Finite Automata

12.6. Finite Automata with Outputs

12.6.1. Mealy Machine

12.6.2. Moore Machine

12.6.3. Equivalence of Mealy and Moore Machines

12.6.4. Conversion From Mealy to Moore Machine

12.6.5. Conversion From Moore to Mealy Machine

12.7. Regular Expression

12.8. Regular Expression and Finite Automata

12.9. Generalized Transition Graph

12.10. Grammar of Formal Languages

12.10.1. Phrase Structure Grammar

12.10.2. Chomsky Hierarchy

12.11. Other Machines

13. Graph Theory

13.1. Introduction

13.2. Graph and its Related Definitions

13.3. Different Types of Graphs

13.3.1. Simple Graph

13.3.2. Multigraph, Trivial Graph, and Null Graph

13.3.3. Complete Graph

13.3.4. Regular Graph

13.3.5. Bipartite Graph

13.3.6. Weighted Graph

13.4. Subgraphs

13.5. Operations on Graphs

13.5.1. Union of Two Graphs

13.5.2. Intersection of Two Graphs

13.5.3. Ring Sum of Two Graphs

13.5.4. Decomposition of a Graph

13.5.5. Deletion of a Vertex

13.5.6. Deletion of an Edge

13.5.7. Complement of a Graph

13.6. Walk, Path, and Circuit

13.6.3. Circuit

13.7. Connected Graph, Disconnected Graph, and Components

13.8. Homomorphism and Isomorphism of Graphs

13.9. Homeomorphic Graphs

13.10. Euler and Hamiltonian Graphs

13.10.1. Euler Line and Euler Graph

13.10.2. Hamiltonian Path and Hamiltonian Circuit

13.10.3. Travelling Salesman Problem

13.11. Planar Graph

13.11.1. Kuratowski's Two Graphs

13.11.2. Region and its Degree

13.11.3. Euler's Formula

13.12.1. Rooted Tree

13.12.2. Binary Tree

13.12.3. Height of Binary Tree

13.12.4. Spanning Tree

13.12.5. Branch and Chord

13.12.6. Rank and Nullity

13.12.7. Fundamental Circuits

13.12.8. Finding All Spanning Trees of a Graph

13.12.9. Spanning Trees in a Weighted Graph

13.12.10. Kruskal's Algorithm

13.12.11. Prim's Algorithm

13.12.12. Dijkstra Algorithm

13.12.13. Binary Search Tree

13.13. Cut Set and Cut Vertex

13.14. Colouring of Graphs

13.14.1. Chromatic Number

13.14.2. Chromatic Partitioning

13.14.3. Independence Set and Maximal Independence Set

13.14.4. Maximum Independence Set and Independence Number

13.14.5. Clique and Maximal Clique

13.14.6. Maximum Clique and Clique Number

13.14.7. Perfect Graph

13.14.8. Chromatic Polynomial

13.14.9. Applications of Graph Colouring

13.15. Matching

13.15.1. Maximal Matching, Maximum Matching, and Matching Number

13.15.2. Perfect Matching

13.16. Matrix Representation of Graphs

13.16.1. Incidence Matrix

13.16.2. Circuit Matrix

13.16.3. Cut Set Matrix

13.16.4. Path Matrix

13.16.5. Adjacency Matrix

13.17. Traversal of Graphs

13.17.1. Breadth-First Search

13.17.2. Depth-First Search

13.18. Traversing Binary Trees

13.18.1. Pre-Order Traversal

13.18.2. In-Order Traversal

13.18.3. Post-Order Traversal

13.19. Digraph or Directed Graph

13.20. Network Flow

13.20.1. Cut in a Transport Network

13.20.2. Flow Augmenting Path

13.21. Enumeration of Graphs

14. Applications of Discrete Mathematical Structures

14.1. Introduction

14.2. Asymptotic Behaviour of Numeric Functions

14.2.1. Big-Oh (O) Notation

14.2.2. Omega (Ω) Notation

14.2.3. Theta (Θ) Notation

14.3. Analysis of Algorithms

14.3.1. Space Complexity

14.3.2. Time Complexity

14.4. Analysis of Sorting Algorithms

14.4.1. Insertion Sort

14.4.2. Bubble Sort

14.4.3. Selection Sort

14.5. Divide-and-Conquer Approach

14.5.1. Merge Sort

14.5.2. Quick Sort

14.6. Analysis of Searching Algorithms

14.6.1. Linear Search

14.6.2. Binary Search

14.7. Tractable and Intractable Problems

14.8. Logic Gates

14.8.1. Switching Circuits and Logic Gates

14.8.2. NAND and NOR Implementations

14.9. Combinational Circuits

14.9.1. Half Adder

14.9.2. Full Adder

14.9.3. Half Subtractor

14.9.4. Full Subtractor

14.10. Information and Coding Theory

14.10.1. Discrete Information Sources

14.10.2. Entropy

14.10.3. Mutual Information

14.10.4. Coding Theory

14.10.5. Hamming Distance

14.10.6. Error-Detecting and Error-Correcting Codes

14.10.7. Group Codes

14.10.8. Generator Matrices

14.10.9. Parity Check Matrices

14.10.10. Coset Decoding

14.10.11. Prefix Codes

14.10.12. Cyclic Code

About the Authors

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

Source records

Community Reviews (0)

No community reviews have been submitted for this work.

Lists

History

Created August 4, 2020
3 revisions

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