Discrete Mathematics by R. K. BishtDiscrete Mathematics by R. K. Bisht

Discrete Mathematics

byR. K. Bisht, H. S. Dhami

Paperback | November 29, 2015

Pricing and Purchase Info


Earn 208 plum® points

Prices and offers may vary in store


Ships within 1-3 weeks

Ships free on orders over $25

Not available in stores


Discrete Mathematics is a textbook designed for the students of computer science engineering, information technology, and computer applications to help them develop their foundations of theoretical computer science. With a detailed introduction to the propositional logic, set theory, and relations, the book in further chapters explores the mathematical notions of functions, integers, counting techniques, probability, discrete numeric functions and generating functions, recurrence relations, algebraicstructures, poset and lattices. The discussion ends with the chapter on theory of formal and finite automata, graph theory and applications of discrete mathematics in various domains. Adopting a solved problems approach to explaining the concepts, the book presents numerous theorems, proofs, practice exercises, and multiple choice questions.
Dr R. K. Bisht is Associate Professor, Department of Computer Science and Applications, Amrapali Institute, Uttarakhand. He has qualified national eligibility test (NET) conducted by CSIR and has around 8 years of teaching experience. He has also published research papers published in various national and international journals. He has...
Title:Discrete MathematicsFormat:PaperbackDimensions:628 pages, 12.28 × 6.14 × 0 inPublished:November 29, 2015Publisher:Oxford University PressLanguage:English

The following ISBNs are associated with this title:

ISBN - 10:0199452792

ISBN - 13:9780199452798


Table of Contents

1. Introduction to Discrete Mathematics and Propositional Logic 11.1 Discrete MathematicsA Brief Introduction1.2 Introduction to Propositional Logic1.3 Proposition1.4 Logical Operators1.4.1 Negation (~)1.4.2 Disjunction (OR/?)1.4.3 Exclusive OR1.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 Formula1.4.10 Rules of Precedence1.5 Tautology1.6 Contradiction1.7 Logical Equivalence1.8 Tautological Implication1.9 Converse, Inverse, and Contrapositive1.10 Functionally Complete Set of Connectives1.11 Normal Forms1.11.1 Elementary Product1.11.2 Elementary Sum1.11.3 Disjunctive Normal Form1.11.4 Conjunctive Normal Form1.11.5 Principal Disjunctive Normal Form1.11.6 Principal Conjunctive Normal Form1.12 Argument1.12.1 Checking the Validity of an Argument by Constructing Truth Table1.12.2 Checking the Validity of an Argument without Constructing Truth Table1.13 Predicates1.13.1 Quantifiers1.13.2 Free and Bound Variables1.13.3 Negation of Quantifiers1.13.4 Removing Quantifiers from Predicates1.14 Nested Quantifiers1.14.1 Effect of Order of Quantifiers1.15 Inference Theory of Predicate Calculus1.15.1 Universal Specification1.15.2 Existential Specification1.15.3 Universal Generalization1.15.4 Existential Generalization1.15.5 Substitution1.15.6 First-order and Second-order Logic1.16 Methods of Proof1.16.1 Trivial Proof1.16.2 Vacuous Proof1.16.3 Direct Proof1.16.4 Proof by Contradiction1.16.5 Proof by Contraposition1.16.6 Proof by Cases1.16.7 Exhaustive Proof1.16.8 Proof by Mathematical Induction1.16.9 Proof by Minimal Counter Example1.17 Satisfiability and Consistency1.18 Mechanization of Reasoning1.18.1 Russells Paradox2. Set Theory2.1 Introduction2.2 Sets2.2.1 Roster Notation2.2.2 Set-builder Notation2.2.3 Cardinality of Sets2.3 Some Standard Sets2.3.1 Empty Set2.3.2 Singleton Set2.3.3 Finite and Infinite Sets2.3.4 Countable and Uncountable Sets2.3.5 Universal Set2.4 Subset and Proper Subset2.5 Equality of Sets2.6 Power Set2.7 Venn Diagrams2.8 Operations on Sets2.8.1 Union2.8.2 Intersection2.8.3 Difference of Two Sets2.8.4 Symmetric Difference of Two Sets2.8.5 Complement of a Set2.8.6 Generalized Union and Intersection2.9 Some Other Classes of Sets2.9.1 Disjoint Sets2.9.2 Partition2.9.3 Ordered Set2.9.4 Cartesian Product of Sets2.10 Algebra of Sets2.11 Multisets2.12 Fuzzy Sets2.12.1 Operations on Fuzzy Sets2.12.2 ?? Cut and Strong ?? Cut2.12.3 Support, Core, and Height of Fuzzy Sets3. Relations3.1 Introduction3.2 Relation3.2.1 Domain and Range3.2.2 Inverse of Relation3.3 Combining Relations3.3.1 Composition of Relations3.4 Different Types of Relations3.4.1 Reflexive Relation3.4.2 Symmetric Relation3.4.3 Transitive Relation3.4.4 Compatible Relation3.4.5 Equivalence Relation3.4.6 Irreflexive Relation3.4.7 Asymmetric Relation3.4.8 Anti-symmetric Relation3.4.9 Partial Order Relation3.5 Pictorial or Graphical Representation of Relations3.6 Matrix Representation of Relations3.7 Closure of Relations3.7.1 Reflexive Closure3.7.2 Symmetric Closure3.7.3 Transitive Closure3.8 Warshalls Algorithm3.9 n-Ary Relations4. Functions4.1 Introduction4.2 Definition of Function4.3 Relations Vs Functions4.4 Types of Functions4.4.1 OneOne Function4.4.2 ManyOne Function4.4.3 Onto Function4.4.4 Identity Function4.4.5 Constant Function4.4.6 Invertible Function4.5 Composition of Functions4.6 Sum and Product of Functions4.7 Functions Used in Computer Science4.7.1 Floor Function4.7.2 Ceiling Function4.7.3 Remainder Function/Modular Arithmetic4.7.4 Characteristic Function4.7.5 Hash Function4.8 Collision Resolution4.8.1 Open Addressing4.8.2 Chaining4.9 Investigation of Functions5. Properties of Integers5.1 Introduction5.2 Basic Properties of Z5.3 Well-Ordering Principle5.4 Elementary Divisibility Properties5.5 Greatest Common Divisor5.6 Least Common Multiple5.7 Linear Diophantine Equation5.8 Fundamental Theorem of Arithmetic5.8.1 Primes and Composites5.8.2 Relatively Prime Integers5.9 Congruence Relation5.10 Residue Classes5.11 Linear Congruence6. Counting Techniques6.1 Introduction6.2 Basic Counting Principle6.2.1 Sum Rule6.2.2 Product Rule6.2.3 InclusionExclusion Principle6.3 Permutations and Combinations6.3.1 Permutation6.3.2 Combination6.4 Generalized Permutation and Combination6.4.1 Permutation with Repetition6.4.2 Permutations with Identical Objects6.4.3 Combination with Repetition6.5 Binomial Coefficients6.6 Partition6.7 Pigeonhole Principle6.7.1 Generalized Pigeonhole Principle6.8 Arrangements with Forbidden Positions6.8.1 Rook Polynomial6.8.2 Derangement7. Fundamentals of Probability7.1 Introduction7.2 Random Experiment7.3 Sample Space7.4 Event7.4.1 Equally Likely Events7.4.2 Mutually Exclusive Events7.4.3 Exhaustive Events7.4.4 Independent Events7.4.5 Dependent Events7.4.6 Complementary Event7.5 Measurement of Probability7.5.1 Classical or Priori Approach of Probability7.5.2 Relative Frequency Approach of Probability7.6 Axioms of Probability7.7 Conditional Probability7.8 Bayes Theorem7.9 Discrete Probability Distributions7.9.1 Expectation of Random Variable7.9.2 Variance and Standard Deviation of Random Variables7.9.3 Binomial Distribution7.9.4 Poisson Distribution7.9.5 Negative Binomial Distribution7.9.6 Geometric Distribution8. Discrete Numeric Functions and Generating Functions8.1 Introduction8.2 Manipulation of Numeric Functions8.2.1 Sum and Product of Two Numeric Functions8.2.2 Multiplication with Scalar8.2.3 Modulus of Numeric Function8.2.4 Siar and S-iar of Numeric Function8.2.5 Forward and Backward Differences of Numeric Functions8.2.6 Accumulated Sum8.2.7 Convolution of Two Numeric Functions8.3 Generating Functions8.3.1 Properties of Generating Functions8.3.2 Solution of Combinatorial Problems Using Generating Functions8. Recurrence Relations9.1 Introduction9.2 Recursive Definition9.2.1 Recursively Defined Functions9.2.2 Recursively Defined Sets9.3 Recurrence Relation9.4 Solution of Recurrence Relations9.4.1 Iterative Method9.4.2 Recursive Method9.4.3 Generating Function9.5 Structural Induction9.6 Order and Degree of Recurrence Relations9.7 Linear Recurrence Relation with Constant Coefficients9.7.1 Linear Homogeneous Recurrence Relation with Constant Coefficients9.7.2 Linear Non-homogeneous Recurrence Relation with Constant Coefficients10. Algebraic Structures10.1 Introduction10.2 Binary Operations10.2.1 Semi-Group10.2.2 Monoid10.2.3 Group10.3 Addition and Multiplication Modulo m10.4 Subgroup10.4.1 Cosets10.5 Permutations and Symmetric Group10.5.1 Cyclic Permutation10.5.2 Stabilizer of an Element10.5.3 Orbit of an Element10.5.4 Invariant Elements under Permutation10.6 Cyclic Group10.7 Normal Subgroup10.8 Quotient Group10.9 Dihedral Group10.10 Homomorphism and Isomorphism10.10.1 Kernel of Homomorphism10.11 Ring10.11.1 Commutative Ring10.11.2 Ring with Unity10.11.3 Zero Divisor of a Ring10.11.4 Subrings10.11.5 Ring Homomorphism10.12 Integral Domain10.13 Division Ring or Skew Field10.14 Field10.15 Polynomial Ring10.16 Boolean Algebra10.16.1 Duality10.16.2 Boolean Functions10.16.3 Simplification of Boolean Functions10.16.4 Canonical Form10.16.5 Standard Form10.16.6 Other Logic Operations10.16.7 Karnaugh Map10.16.8 QuineMccluskey Method10.16.9 Free Boolean Algebra11. Posets and Lattices11.1 Introduction11.2 Partially Ordered Set11.3 Diagrammatic Representation of Poset (Hasse Diagram)11.4 Elements in Posets11.4.1 Least and Greatest Elements11.4.2 Minimal and Maximal Elements11.4.3 Lower and Upper Bounds11.4.4 Greatest Lower Bound and Least Upper Bounds11.5 Linearly Ordered Set11.6 Well-Ordered Set11.7 Product Order11.8 Lexicographic Order11.9 Topological Sorting and Consistent Enumeration11.10 Isomorphism11.11 Lattices11.12 Properties of Lattices11.12.1 Principle of Duality11.12.2 Sublattice11.13 Some Special Lattices11.13.1 Modular Lattice11.13.2 Distributive Lattice11.13.3 Bounded Lattice11.13.4 Complemented Lattice11.13.5 Complete Lattice11.14 Product of Lattices11.15 Lattice Homomorphism11.16 Boolean Algebra and Lattices11.17 Stones Representation Theorem12. Formal Languages and Finite Automata12.1 Introduction12.2 Alphabet and Words12.3 Language12.4 Operations on Languages12.5 Finite Automata12.5.1 Deterministic Finite State Automata12.5.2 Non-Deterministic Finite Automata12.5.3 Conversion from Non-Deterministic Finite Automata to Deterministic Finite Automata12.5.4 Minimization of Finite Automata12.6 Finite Automata with Outputs12.6.1 Mealy Machine12.6.2 Moore Machine12.6.3 Equivalence of Mealy and Moore Machines12.6.4 Conversion from Mealy to Moore Machine12.6.5 Conversion from Moore to Mealy Machine12.7 Regular Expression12.8 Regular Expression and Finite Automata12.9 Generalized Transition Graph12.10 Grammar of Formal Languages12.10.1 Phrase Structure Grammar12.10.2 Chomsky Hierarchy12.11 Other Machines13. Graph Theory13.1 Introduction13.2 Graph and its Related Definitions13.3 Different Types of Graphs13.3.1 Simple Graph13.3.2 Multigraph, Trivial Graph, and Null Graph13.3.3 Complete Graph13.3.4 Regular Graph13.3.5 Bipartite Graph13.3.6 Weighted Graph13.4 Subgraphs13.5 Operations on Graphs13.5.1 Union of Two Graphs13.5.2 Intersection of Two Graphs13.5.3 Ring Sum of Two Graphs13.5.4 Decomposition of a Graph13.5.5 Deletion of a Vertex13.5.6 Deletion of an Edge13.5.7 Complement of a Graph13.6 Walk, Path, and Circuit13.6.1 Walk13.6.2 Path13.6.3 Circuit13.7 Connected Graph, Disconnected Graph, and Components13.8 Homomorphism and Isomorphism of Graphs13.9 Homeomorphic Graphs13.10 Euler and Hamiltonian Graphs13.10.1 Euler Line and Euler Graph13.10.2 Hamiltonian Path and Hamiltonian Circuit13.10.3 Travelling Salesman Problem13.11 Planar Graph13.11.1 Kuratowskis Two Graphs13.11.2 Region and its Degree13.11.3 Eulers Formula13.12 Tree13.12.1 Rooted Tree13.12.2 Binary Tree13.12.3 Height of Binary Tree13.12.4 Spanning Tree13.12.5 Branch and Chord13.12.6 Rank and Nullity13.12.7 Fundamental Circuits13.12.8 Finding All Spanning Trees of a Graph13.12.9 Spanning Trees in a Weighted Graph13.12.10 Kruskals Algorithm13.12.11 Prims Algorithm13.12.12 Dijkstra Algorithm13.12.13 Binary Search Tree13.13 Cut Set and Cut Vertex13.14 Colouring of Graphs13.14.1 Chromatic Number13.14.2 Chromatic Partitioning13.14.3 Independence Set and Maximal Independence Set13.14.4 Maximum Independence Set and Independence Number13.14.5 Clique and Maximal Clique13.14.6 Maximum Clique and Clique Number13.14.7 Perfect Graph13.14.8 Chromatic Polynomial13.14.9 Applications of Graph Colouring13.15 Matching13.15.1 Maximal Matching, Maximum Matching, and Matching Number13.15.2 Perfect Matching13.16 Matrix Representation of Graphs13.16.1 Incidence Matrix13.16.2 Circuit Matrix13.16.3 Cut Set Matrix13.16.4 Path Matrix13.16.5 Adjacency Matrix13.17 Traversal of Graphs13.17.1 Breadth-First Search13.17.2 Depth-First Search13.18 Traversing Binary Trees13.18.1 Pre-Order Traversal13.18.2 In-Order Traversal13.18.3 Post-Order Traversal13.19 Digraph or Directed Graph13.20 Network Flow13.20.1 Cut in a Transport Network13.20.2 Flow Augmenting Path13.21 Enumeration of Graphs14. Applications of Discrete Mathematical Structures14.1 Introduction14.2 Asymptotic Behaviour of Numeric Functions14.2.1 Big-Oh (O) Notation14.2.2 Omega (?) Notation14.2.3 Theta (q) Notation14.3 Analysis of Algorithms14.3.1 Space Complexity14.3.2 Time Complexity14.4 Analysis of Sorting Algorithms14.4.1 Insertion Sort14.4.2 Bubble Sort14.4.3 Selection Sort14.5 Divide-and-Conquer Approach14.5.1 Merge Sort14.5.2 Quick Sort14.6 Analysis of Searching Algorithms14.6.1 Linear Search14.6.2 Binary Search14.7 Tractable and Intractable Problems14.8 Logic Gates14.8.1 Switching Circuits and Logic Gates14.8.2 NAND and NOR Implementations14.9 Combinational Circuits14.9.1 Half Adder14.9.2 Full Adder14.9.3 Half Subtractor14.9.4 Full Subtractor14.10 Information and Coding Theory14.10.1 Discrete Information Sources14.10.2 Entropy14.10.3 Mutual Information14.10.4 Coding Theory14.10.5 Hamming Distance14.10.6 Error-Detecting and Error-Correcting Codes14.10.7 Group Codes14.10.8 Generator Matrices14.10.9 Parity Check Matrices14.10.10 Coset Decoding14.10.11 Prefix Codes14.10.12 Cyclic CodeAppendices