Discrete Mathematics

Written with a strong pedagogical focus, the third edition of the book continues to provide an exhaustive presentation of the fundamental concepts of discrete mathematical structures and their applications in computer science and mathematics. It aims to develop the ability of the students to apply mathematical thought in order to solve computation-related problems. The book is intended not only for the undergraduate and postgraduate students of mathematics but also, most importantly, for the students of Computer Science & Engineering and Computer Applications. The book is replete with features which enable the building of a firm foundation of the underlying principles of the subject and also provides adequate scope for testing the comprehension acquired by the students. Each chapter contains numerous worked-out examples within the main discussion as well as several chapter-end Supplementary Examples for revision. The Self-Test and Exercises at the end of each chapter include a large number of objective type questions and problems respectively. Answers to objective type questions and hints to exercises are also provided. All these pedagogic features, together with thorough coverage of the subject matter, make this book a readable text for beginners as well as advanced learners of the subject. New To This Edition Question Bank consisting of questions from various University Examinations Updated chapters on Boolean Algebra, Graphs and Trees as per the recent syllabi followed in Indian Universities Target Audience BE/B.Tech (Computer Science and Engineering) MCA M.Sc (Computer Science/Mathematics) Title Discrete Mathematics, Third Edition Copyright Contents Preface Preface to the Second Edition Preface to the First Edition 1. Foundations 1.1 Logic 1.1.1 Connectives 1.1.2 Predicates and Quantifiers 1.2 Methods of Proof 1.3 Set Theory 1.3.1 Definition and Representation of Sets 1.3.2 Operations on Sets 1.3.3 Representation by Venn Diagram 1.3.4 Multisets 1.4 Relations 1.4.1 Relations and Sets Arising From Relations 1.5 Functions 1.5.1 Definition of a Function and Examples 1.5.2 One-to-One and ONTO Functions 1.5.3 Permutations 1.6 Basics of Counting 1.6.1 Addition and Multiplication Principles 1.7 Integers and Induction 1.7.1 Well-Ordering Principle 1.7.2 Division in Z 1.7.3 Fundamental Theorem of Arithmetic 1.7.4 Modular Arithmetic 1.7.5 Principle of Mathematical Induction and Pigeonhole Principle 1.8 Pigeonhole Principle 1.9 Tuples, Strings and Matrices 1.9.1 n-Tuples and Strings 1.9.2 Matrices 1.9.3 Boolean Matrices 1.10 Algebraic Structures 1.10.1 Operations on Sets 1.10.2 Properties of Binary Operations 1.10.3 Algebraic Structures 1.10.4 Structure-Preserving Functions 1.11 Graphs 1.11.1 Definition of Graph and Examples 1.11.2 Edge Sequences, Walks, Paths and Circuits 1.11.3 Directed Graphs 1.11.4 Subgraphs and Operations on Graphs 1.11.5 Isomorphisms of Graphs Supplementary Examples Self-Test Exercises 2. Predicate Calculus 2.1 Well-Formed Formulas 2.2 Truth Table of Well-Formed Formula 2.3 Tautology, Contradiction and Contingency 2.4 Equivalence of Formulas 2.5 Algebra of Propositions 2.5.1 Quine’s Method 2.6 Functionally Complete Sets 2.7 Normal Forms of Well-Formed Formulas 2.8 Rules of Inference for Propositional Calculus 2.9 Well-Formed Formulas of Predicate Calculus 2.10 Rules of Inference for Predicate Calculus 2.11 Predicate Formulas Involving Two or More Quantifiers Supplementary Examples Self-Test Exercises 3. Combinatorics 3.1 Permutations 3.2 Combinations 3.3 Permutations with Repetitions 3.4 Combinations with Repetition 3.5 Permutations of Sets with Indistinguishable Objects 3.6 Miscellaneous Problems on Permutations and Combinations 3.7 Binomial Identities and Binomial Theorem 3.7.1 Binomial Identities 3.7.2 Generating Functions of Permutations and Combinations Supplementary Examples Self-Test Exercises 4. More on Sets 4.1 Set Identities 4.2 Principle of Inclusion–Exclusion Supplementary Examples Self-Test Exercises 5. Relations and Functions 5.1 Binary Relations 5.1.1 Operations on Relations 5.2 Properties of Binary Relations in a Set 5.3 Equivalence Relations and Partial Orderings 5.4 Representation of a Relation by a Matrix 5.5 Representation of a Relation by a Digraph 5.6 Closure of Relations 5.7 Warshall’s Algorithm for Transitive Closure 5.8 More on Functions 5.9 Some Important Functions 5.10 Hashing Functions Supplementary Examples Self-Test Exercises 6. Recurrence Relations 6.1 Formulation as Recurrence Relations 6.2 Solving Recurrence Relation by Iteration 6.3 Solving Recurrence Relations 6.4 Solving Linear Homogeneous Recurrence Relations of Order Two 6.5 Solving Linear Nonhomogeneous Recurrence Relations 6.6 Generating Functions 6.6.1 Partial Fractions 6.6.2 Generating Function of a Sequence 6.6.3 Solving Recurrence Relations Using Generating Functions 6.7 Divide-and-Conquer Algorithms 6.7.1 Recurrence Relation for Divide-and-Conquer Algorithm Supplementary Examples Self-Test Exercises 7. Algebraic Structures 7.1 Semigroups and Monoids 7.1.1 Definition and Examples 7.1.2 Subsemigroups and Submonoids 7.1.3 Homomorphism of Semigroups and Monoids 7.2 Groups 7.2.1 Definitions and Examples 7.2.2 Subgroups 7.2.3 Group Homomorphisms 7.2.4 Cosets and Lagrange’s Theorem 7.2.5 Normal Subgroups and Quotient Groups 7.2.6 Permutation Groups 7.3 Algebraic Systems with Two Binary Operations 7.3.1 Rings 7.3.2 Some Special Classes of Rings 7.3.3 Subrings and Homomorphisms Supplementary Examples Self-Test Exercises 8. Lattices 8.1 Definition and Examples 8.2 Properties of Lattices 8.3 Lattices as Algebraic Systems 8.4 Sublattices and Lattice Isomorphisms 8.5 Special Classes of Lattice 8.6 Distributive Lattices and Boolean Algebras Supplementary Examples Self-Test Exercises 9. Boolean Algebras 9.1 Boolean Algebra as Lattice 9.2 Boolean Algebra as an Algebraic System 9.3 Properties of a Boolean Algebra 9.4 Subalgebras and Homomorphisms of Boolean Algebras 9.5 Boolean Functions 9.5.1 Boolean Expressions 9.5.2 Sum-of-Products Canonical Form 9.5.3 Values of Boolean Expressions and Boolean Functions 9.5.4 Switching Circuits and Boolean Functions 9.5.5 Half-Adders and Full-Adders Supplementary Examples Self-Test Exercises 10. Graphs 10.1 Connected Graphs 10.2 Examples of Special Graphs 10.3 Euler Graphs 10.4 Hamiltonian Circuits and Paths 10.5 Planar Graphs 10.6 Matrix Representation of Graphs 10.6.1 Incidence Matrix 10.6.2 Adjacency Matrix Supplementary Examples Self-Test Exercises 11. Trees 11.1 Properties of Trees 11.2 Special Classes of Trees 11.2.1 Rooted Trees 11.2.2 Binary Trees 11.2.3 Binary Search Trees 11.2.4 Decision Trees 11.3 Spanning Trees 11.3.1 Definition and Properties of Spanning Trees 11.3.2 Algorithms on Spanning Trees 11.4 Minimal Spanning Trees Supplementary Examples Self-Test Exercises Question Bank (Additional Exercises for Practice Further Readings Index Back cover