Transcription
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 2014 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 . 1Topics in Discrete Mathematics . 1PART 1: SETS, RELATIONS, AND FUNCTIONS . 22.Sets . 3Set – Definition . 3Representation of a Set. 3Cardinality of a Set . 4Types of Sets . 4Venn Diagrams . 6Set Operations . 7Power Set . 8Partitioning of a Set . 93.Relations . 10Definition and Properties . 10Domain and Range . 10Representation of Relations using Graph . 10Types of Relations . 114.Functions . 12Function – Definition . 12Injective / One-to-one function . 12Surjective / Onto function . 12Bijective / One-to-one Correspondent . 12Composition of Functions . 13PART 2: MATHEMATICAL LOGIC . 145.Propositional Logic . 15Prepositional Logic – Definition . 15Connectives . 15Tautologies . 17Contradictions . 17Contingency . 17Propositional Equivalences . 18Inverse, Converse, and Contra-positive. 18Duality Principle. 19Normal Forms . 19ii
Discrete Mathematics6.Predicate Logic . 20Predicate Logic – Definition . 20Well Formed Formula . 20Quantifiers . 20Nested Quantifiers . 217.Rules of Inference . 22What are Rules of Inference for? . 22Addition . 22Conjunction . 22Simplification . 23Modus Ponens . 23Modus Tollens . 23Disjunctive Syllogism . 24Hypothetical Syllogism . 24Constructive Dilemma . 24Destructive Dilemma . 25PART 3: GROUP THEORY . 268.Operators and Postulates . 27Closure . 27Associative Laws . 27Commutative Laws . 28Distributive Laws . 28Identity Element . 28Inverse . 29De Morgan’s Law . 299.Group Theory . 30Semigroup . 30Monoid . 30Group . 30Abelian Group . 31Cyclic Group and Subgroup . 31Partially Ordered Set (POSET) . 32Hasse Diagram . 32Linearly Ordered Set . 33Lattice . 33Properties of Lattices . 35Dual of a Lattice . 35PART 4: COUNTING & PROBABILITY . 3610. Counting Theory .
Discrete Mathematics i About the Tutorial 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 .
