Discrete Mathematics for Computing and Data Science

Mr. Dumpa Sreepal is currently working as an Assistant Professor at Loyola Academy Degree and PG College Hyderabad. He is also pursuing a Ph.D. in Mathematics from RTMNU (Nagpur state university). He holds multiple postgraduate degrees including M.Sc., MBA, M.A., M.S.C. (Mathematics) and M.Sc. (statistics). Mr. Sreepal has over 12 years of teaching experience, with expertise spanning both technical and management subjects. He has authored several research articles published in reputed national and international journals. His areas of interest include Mathematics, Management, and Technical research, and he actively contributes to academic literature in these fields. In addition to his publications, he also holds two patents, reflecting his innovative contributions to academia and applied research.

Mrs. Kundanapalli Vennela is an Assistant Professor of Mathematics at Vishwa Vishwani Institute of Systems and Management with 5 years of teaching experience in higher education. She holds an M.Sc. in Mathematics and B.Ed. Her areas of expertise include Calculus, Linear Algebra, Real Analysis, Discrete Mathematics, and Business Statistics. She is passionate about simplifying mathematical concepts through effective teaching methodologies. She actively mentors students and promotes analytical thinking and problem-solving skills. As an author, she has contributed to the preparation of academic content and study materials for undergraduate students. She regularly participates in seminars, workshops, and faculty development programs to enhance her knowledge and teaching practices. Dedicated to academic excellence, she strives to inspire students and foster a strong foundation in mathematics

Preface v
1. Sets, Relation and Function 1
♦ Operations and Laws of Sets 2
♦ Cartesian Products 6
♦ Binary Relation 9
♦ Partial Ordering Relation 11
♦ Equivalence Relation 12
♦ Image of a Set 15
♦ Sum and Product of Functions 17
♦ Bijective functions 20
♦ Inverse and Composite Function 23
♦ Size of a Set 25
♦ Cardinality of an Infinite Set 25
♦ Recursive Definitions 32
♦ Cardinality of a Countable Set 48
♦ Cardinality of an Uncountable Set 48
♦ Cantor’s diagonal argument 49
♦ The Power Set theorem 51
♦ Schroeder-Bernstein theorem 52
♦ Division algorithm 57
♦ Prime Numbers 59
♦ Greatest Common Divisor (GCD) 60
♦ Euclidean Algorithm 62
♦ Fundamental Theorem of Arithmetic 65
♦ Proof of the Fundamental Theorem of Arithmetic 66

2. Basic Counting Techniques 77
♦ Inclusion and Exclusion 78
♦ Pigeon-hole Principle 82
♦ Pigeonhole Principle Theorem 87
♦ Pigeonhole Principle Strong Form Theorem 87
♦ Permutation and Combination 88

3. Propositional Logic 93
♦ Propositional Logic 94
♦ Mathematical Logic or Symbolic Logic 95
♦ Connectives 96
♦ Truth Table for Negation 97
♦ Truth Tables 105
♦ Tautology 109
♦ Equivalence of Formula Implication 111
♦ Duality Law 112
♦ Logical Implication: 115
♦ Tautological Implications 115
♦ Functionally Complete Set of Connectives 118
♦ Other Connectives 119
♦ NAND 120
♦ Disjunctive Normal Forms 122
♦ Logical Connectives 128
♦ Logical Equivalence and Laws of Logic 132
♦ Logical Implication 134
♦ Rules of Inference 134
♦ Use of Quantifiers 146
♦ Predicates 149
♦ Predicate Logic 149
♦ Free and Bound Variables 153
♦ Automatic Theorem Proving 159
♦ Formulation of Rules of Inference Theory 159
♦ Procedure for Automatic Theorem Proving System 163
♦ Proof Techniques 167
♦ Types of Mathematical Proofs 168
♦ Proof by Contradiction 168
♦ Indirect Proof (Proof by Contraposition) 171
♦ Proof of Necessity and Sufficiency 175

4. Algebraic Structures and Morphism 179
♦ Algebraic Structures 180
♦ Algebraic Structures with one Binary Operation 181
♦ Semigroup 183
♦ Monoids 184
♦ Groups 187
♦ Congruence Relation and Quotient Structures 188
♦ Free and Cyclic Monoids and Groups 191
♦ Permutation Groups 194
♦ Substructures 196
♦ Normal subgroup 197
♦ Algebraic Structures with Two Binary Operations 198
♦ Rings 198
♦ Integral Domain and fields 200
♦ Boolean Algebra 201
♦ Boolean Ring 208
♦ Identities of Boolean Algebra 211
♦ Principle of Duality 213
♦ Representation of Boolean Function 214
♦ Disjunctive Normal Form 217
♦ Conjunctive Normal Form (CNF) 218

5. Graphs and Trees 221
♦ Graphs and their properties 222
♦ Connectivity 227
♦ Isomorphism 231
♦ Graph Complements 233
♦ Eulerian and Hamiltonian Walks 236
♦ Hamiltonian Circuit 239
♦ Graph Coloring and Planar Graphs 241
♦ Graph Representation of a Map 245
♦ Rooted tree 248
♦ Trees and Sorting 249
♦ Weighted Trees and Prefix Codes 250
♦ Bi-connected component 253
♦ Articulation Points 257
♦ Shortest distances 258
♦ Bibliography 262