WIXLIB

Discrete MathematicsAbout the TutorialDiscrete Mathematics is a branch of mathematics involving discrete elements that usesalgebra and arithmetic. It is increasingly being applied in the practical fields ofmathematics and computer science. It is a very good tool for improving reasoning andproblem-solving capabilities.This tutorial explains the fundamental concepts of Sets, Relations and Functions,Mathematical Logic, Group theory, Counting Theory, Probability, Mathematical Inductionand Recurrence Relations, Graph Theory, Trees and Boolean Algebra.AudienceThis tutorial has been prepared for students pursuing a degree in any field of computerscience and mathematics. It endeavors to help students grasp the essential concepts ofdiscrete mathematics.PrerequisitesThis tutorial has an ample amount of both theory and mathematics. The readers areexpected to have a reasonably good understanding of elementary algebra and arithmetic.Copyright & Disclaimer Copyright 2016 by Tutorials Point (I) Pvt. Ltd.All the content and graphics published in this e-book are the property of Tutorials Point (I)Pvt. Ltd. The user of this e-book is prohibited to reuse, retain, copy, distribute or republishany contents or a part of contents of this e-book in any manner without written consentof the publisher.We strive to update the contents of our website and tutorials as timely and as precisely aspossible, however, the contents may contain inaccuracies or errors. Tutorials Point (I) Pvt.Ltd. provides no guarantee regarding the accuracy, timeliness or completeness of ourwebsite or its contents including this tutorial. If you discover any errors on our website orin this tutorial, please notify us at contact@tutorialspoint.comi

Discrete MathematicsTable of ContentsAbout the Tutorial . iAudience . iPrerequisites . iCopyright & Disclaimer . iTable of Contents . ii1.Discrete Mathematics – Introduction . 1PART 1: SETS, RELATIONS, AND FUNCTIONS . 22.Sets . 3Set – Definition . 3Representation of a Set. 3Cardinality of a Set . 4Types of Sets . 5Venn Diagrams . 7Set Operations . 7Power Set . 9Partitioning of a Set . 93.Relations . 11Definition and Properties . 11Domain and Range . 11Representation of Relations using Graph . 11Types of Relations . 124.Functions . 14Function – Definition . 14Injective / One-to-one function . 14Surjective / Onto function . 14Bijective / One-to-one Correspondent . 14Inverse of a Function . 15Composition of Functions . 15PART 2: MATHEMATICAL LOGIC . 175.Propositional Logic . 18Prepositional Logic – Definition . 18Connectives . 18Tautologies . 20Contradictions . 20Contingency . 20Propositional Equivalences . 21Inverse, Converse, and Contra-positive. 22Duality Principle. 22Normal Forms . 22ii

Discrete Mathematics6.Predicate Logic . 24Predicate Logic – Definition . 24Well Formed Formula . 24Quantifiers . 24Nested Quantifiers . 257.Rules of Inference . 26What are Rules of Inference for? . 26Table of Rules of Inference . 26Addition . 27Conjunction . 27Simplification . 27Modus Ponens . 27Modus Tollens . 28Disjunctive Syllogism . 28Hypothetical Syllogism . 28Constructive Dilemma . 29Destructive Dilemma . 29PART 3: GROUP THEORY . 308.Operators and Postulates . 31Closure . 31Associative Laws . 31Commutative Laws . 32Distributive Laws . 32Identity Element . 32Inverse . 33De Morgan’s Law . 339.Group Theory . 34Semigroup . 34Monoid . 34Group . 34Abelian Group . 35Cyclic Group and Subgroup . 35Partially Ordered Set (POSET) . 36Hasse Diagram . 37Linearly Ordered Set . 37Lattice . 38Properties of Lattices . 39Dual of a Lattice . 39PART 4: COUNTING & PROBABILITY .

Discrete Mathematics is a branch of mathematics involving discrete elements that uses algebra and arithmetic. It is increasingly being applied in the practical fields of mathematics and computer science. It is a very good tool for improving reasoning and problem-solving capabilities. This tutorial explains the fundamental concepts of Sets, Relations and Functions,