Discrete Mathematics

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, algebraic structures, 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.

Table of Contents:
1. Introduction to Discrete Mathematics and Propositional Logic 1; 1.1 Discrete MathematicsA 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.5 Tautology; 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 Argument; 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 Russells Paradox; 2. Set Theory; 2.1 Introduction; 2.2 Sets; 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.6 Power Set; 2.7 Venn Diagrams; 2.8 Operations on Sets; 2.8.1 Union; 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.Relations; 3.1 Introduction; 3.2 Relation; 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 Warshalls Algorithm; 3.9 n-Ary Relations; 4. Functions; 4.1 Introduction; 4.2 Definition of Function; 4.3 Relations Vs Functions; 4.4 Types of Functions; 4.4.1 OneOne Function; 4.4.2 ManyOne 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 InclusionExclusion 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.6 Partition; 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 Event; 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 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 Siar and S-iar 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.2.2 Monoid; 10.2.3 Group; 10.3 Addition and Multiplication Modulo m; 10.4 Subgroup; 10.4.1 Cosets; 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 Ring; 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.14 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 QuineMccluskey 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 Bounds; 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 Stones Representation Theorem; 12. Formal Languages and Finite Automata; 12.1 Introduction; 12.2 Alphabet and Words; 12.3 Language; 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.1 Walk; 13.6.2 Path; 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 Kuratowskis Two Graphs; 13.11.2 Region and its Degree; 13.11.3 Eulers Formula; 13.12 Tree; 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 Kruskals Algorithm; 13.12.11 Prims 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 (q) 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; Appendices

About the Author :
Dr R K Bisht is Associate Professor, Department of Computer Science & 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 been awarded the Young Scientist Award from Uttarakhand Science Congress during its 7th edition. His research area includes formal language and automata, Mathematical models in Natural Language Processing and Information Retrievals. Prof. Hoshiyar Singh Dhami is the Vice Chancellor, Kumaon University, Uttarakhand. He had been a professor of Mathematics and coordinator of center of excellence in mathematical sciences, Uttarakhand. He has been selected among the 2000 outstanding intellectuals of the 21st century by the International Biographical Centre, Cambridge, England. Prof. Dhami has more than 35 years of teaching experience and more than 150 national and international published research papers, 6 books to his credit. He is also the editor of International Journal of Engineering Science and Technology and reviewer of other national and international journals. He is also the fellow of Vikram Mathematical Society and member of several other societies. He has delivered several key note, invited and theme lectures in India and abroad. His research interest includes Special Function, Mathematical Linguistics, Mathematical models in Natural Language Processing and Information Retrievals.