DISCRETE MATHEMATICAL STRUCTURES [As Per Choice Based .
15CS36DISCRETE MATHEMATICAL STRUCTURESDISCRETE MATHEMATICAL STRUCTURES[As per Choice Based Credit System (CBCS) scheme]SEMESTER - IIISubject Code15CS36IA Marks20Numberof Lecture04Exam Marks80Hours/WeekTotalNumberof50Exam Hours03Lecture HoursCourse objectives:. This course will enable students to· Prepare for a background in abstraction, notation, andcritical thinking for the mathematics most directly related to computer science.· Understand and apply logic, relations, functions, basic set theory, countability and countingarguments, proof techniques,· Understand and apply mathematical induction, combinatorics, discrete probability, recursion,sequence and recurrence, elementary number theory· Understand and apply graph theory and mathematical proof techniques.RBTTeachingModule -1LevelsHoursSet Theory: Sets and Subsets, Set Operations and the Laws of SetTheory, Counting and Venn Diagrams, A First Word on Probability,Countable and Uncountable Sets.10 HoursL2, L3Fundamentals of Logic: Basic Connectives and Truth Tables, LogicEquivalence –The Laws of Logic, Logical Implication – Rules ofInference.Module -2Fundamentals of Logic contd.: The Use of Quantifiers, Quantifiers,Definitions and the Proofs of Theorems, Properties of the Integers: 10 HoursL3, L4Mathematical Induction, The Well Ordering Principle –Mathematical Induction, Recursive DefinitionsModule – 3Relations and Functions: Cartesian Products and Relations,L3,L4,Functions – Plain and One-to-One, Onto Functions – Stirling10 HoursL5Numbers of the Second Kind, Special Functions, The Pigeon-holePrinciple, Function Composition and Inverse Functions.Module-4Relations contd.: Properties of Relations, Computer Recognition –L3,L4,10 HoursZero-One Matrices and Directed Graphs, Part ial Orders – HasseL5Diagrams, Equivalence Relations and Partitions.Module-5Groups: Definitions, properties, Homomrphisms, Isomorphisms,Cyclic Groups, Cosets, and Lagrange’s Theorem. Coding Theoryand Rings: Elements of CodingTheory, The Hamming Metric, TheParity Check, and Generator Matrices. Group Codes: Decodingwith Coset Leaders, Hamming Matrices. Rings and ModularArithmetic: The Ring Structure – Definition and Examples, RingProperties and Substructures, The Integer modulo n.DEPT. OF CSE, ACE10 HoursL3,L4,L5Page 1
DISCRETE MATHEMATICAL STRUCTURES15CS36Course outcomes:After studying this course, students will be able to:1. Verify the correctness of an argument using propositional and predicate logic and truth tables.2. Demonstrate the ability to solve problems using counting techniques and combinatorics in thecontext of discrete probability.3. Solve problems involving recurrence relations and generating functions.4. Perform operations on discrete structures such as sets, functions, relations, and sequences.5. Construct proofs using direct proof, proof by contraposition, proof by contradiction, proof bycases, and mathematical induction.Graduate Attributes (as per NBA)1. Engineering Knowledge2. Problem Analysis3. Conduct Investigations of Complex Problems4. Design/Development of SolutionsQuestion paper pattern:The question paper will have ten questions.There will be 2 questions from each module.Each question will have questions covering all the topics under a module.The students will have to answer 5 full questions, selecting one full question from each module.Text Books:1.Ralph P. Grimaldi: Discrete and Combinatorial Mathematics, , 5th Edition, Pearson Education.2004. (Chapter 3.1, 3.2, 3.3, 3.4, Appendix 3, Chapter 2, Chapter 4.1, 4.2, Chapter 5.1 to 5.6,Chapter 7.1 to 7.4, Chapter 16.1, 16.2, 16.3, 16.5 to 16.9, and Chapter 14.1, 14.2, 14.3).Reference Books:1. Kenneth H. Rosen: Discrete Mathematics and its Applications, 6th Edition, McGraw Hill,2007.2. JayantGanguly: A TreatCSE on Discrete Mathematical Structures, Sanguine-Pearson, 2010.3. D.S. Malik and M.K. Sen: Discrete Mathematical Structures: Theory and Applications,Thomson, 2004.4. Thomas Koshy: Discrete Mathematics with Applications, Elsevier, 2005, Reprint 2008.DEPT. OF CSE, ACEPage 2
DISCRETE MATHEMATICAL STRUCTURES15CS36INDEX SHEETModule sContentsPage No.Set Theory: Sets and Subsets, Set Operations and the Laws of SetTheory, Counting and Venn Diagrams, A First Word on Probability,Module -1Countable and Uncountable Sets.Fundamentals of Logic: Basic Connectives and Truth Tables, Logic04-26Equivalence –The Laws of Logic, Logical Implication – Rules ofInference.Fundamentals of Logic contd.: The Use of Quantifiers, Quantifiers,Module -2Definitions and the Proofs of Theorems, Properties of the Integers:Mathematical Induction, The Well Ordering Principle – Mathematical27-40Induction, Recursive DefinitionsRelations and Functions: Cartesian Products and Relations, FunctionsModule -3– Plain and One-to-One, Onto Functions – Stirling Numbers of theSecond Kind, Special Functions, The Pigeon-hole Principle, Function41-68Composition and Inverse Functions.Relations contd.: Properties of Relations, Computer Recognition –Module -4Zero-One Matrices and Directed Graphs, Partial Orders – Hasse69-76Diagrams, Equivalence Relations and Partitions.Groups: Definitions, properties, Homomrphisms, Isomorphisms,Cyclic Groups, Cosets, and Lagrange’s Theorem. Coding Theory andRings: Elements of CodingTheory, The Hamming Metric, The ParityModule -5Check, and Generator Matrices. Group Codes: Decoding with Coset77-114Leaders, Hamming Matrices. Rings and Modular Arithmetic: TheRing Structure – Definition and Examples, Ring Properties andSubstructures, The Integer modulo nDEPT. OF CSE, ACEPage 3
DISCRETE MATHEMATICAL STRUCTURES15CS36Module 1: Set Theory: Sets and Subsets, Set Operations and the Laws of Set Theory, Counting and Venn Diagrams, A First Word on Probability, Countable and Uncountable SetsFundamentals of Logic: Basic Connectives and Truth Tables, Logic Equivalence –The Laws of Logic, Logical Implication – Rules of Inference.DEPT. OF CSE, ACEPage 4
15CS36DISCRETE MATHEMATICAL STRUCTURESSet Theory:Sets and Subsets:A set is aof objects, called elements the set. setbcollectionofAcanbe y listingbetwee braces: A {1, 2, 3, 4, 5}. The symbol belongsits elements ne is (orto)a set.3 e A. Its negation is representede.g.finite,For instance by /e,7 /eA. If the set Is itsnumber of elements is represented A , e.g. if A {1, 2, 3, A 4, 5} then51. N {0, 1, 2, 3, ·· · } the set of natural numbers.2. Z {··· , -3, -2, -1, 0, 1, 2, 3, ··· } the set of integers.3. Q the set of rational numbers.4. R the set of real numbers.5. C the set of complex numbers.If S is one ofthose1. Sthen we also use the followingsets notations : elementset of positive s Z {1, 2, 3,··· } of negative2. S set elements {-1, -2, -3,Z ··· } 3. S setnumbers. ofinelements Sin S, forinstancethe set of positiveintegers.in S, for instanceset of negativetheintegers.excluding zero, forinstance R the set of non zero realAnway to define acalled setSet-builderalternativeset,builder notation, isnotation:bypropert (predicatverifie byitsstatinga ye)P (x) dexactlyelements,for instanceA {x e 1 x 5} “set ofx such that 1 5”—Z integersxi.e.: A {1, 2, 3,4,general: A {x e U p(x)},Uuniversof5}. In whereis the ediscourse in whichthemus be interpreted, or A {x P (x)} if the universe ofpredicateP (x) tdiscoursefor P (x) isunderstoodIn setthe term universalis often used in
implicitly .theoryplace of “universe of discourse” for a givenpredicate.Princip of Extension: Two sets are equal only ifif andtheyleA x (x e A x e B)elements, i.e.: BSubset: We say A is aof setthatsubsetB,if allof Ait “A B”, elementsareB {a, b, c, d, e} then A B.Proper subset:A is aDEPT. OF CSE,ACEsethave the same.or A iscontainedin B,and we representif A {a, b, c}in B, e.g.,andprope subse ofrepresentertB,d “A B”, if A Bi.e., there is some elementwhich isA B, in Bnot in A.Page5
15CS36DISCRETE MATHEMATICAL STRUCTURESEmpty Set: A set with no elements is called empty set(or null set, or void set ), and is represented by or {}.Note thatpreven a set from possiblynothingtsbeing anis not the same as being asubset!).For i n stanceif A i.e.,BeA.{1, a, {3, t}, { 1, 2, 3}} { 3, t}, tand B henelement ofanotherobvious lyBse (whict his an elem ent ofA,Pow Set:erThecollectio ofsubseA isthe power set ofn all tsof a set calledA,isP(A). For instance, if A {1, 2, 3},and represented thenP(A) { , {2}, {3}, {1, 2}, {1, 3}, {2, 3},{1},A} .MultCSEordinar setidentical if they havesamets:Twoysare theelements,so forinstance, {a, a, b} {a, b} theset becauseexactlandaresametheyhave ythe sameelements namelHoweve inapplication it might,some sbeuseful toya and b. r,elementaw us multCSEtarallow repeateds in set.In that case e es,which emathematical entities similar topossibl repeat elements Sosets, butwith yed.,asmultCSEts, {a, a, b} and {a, b} would be consi dered since in the first onedifferent,theelement a occurs twice in the second one it occurs onlyandonce.S et Oper atio ns:1. Intersection : The common elements of two sets:A B {x (x e A) (x e B)} .If A B , the sets are said to be disjoint.2. Union : The set of elements thatbelong to either of two sets:A B {x (x e A) (x e B)} .
3.Complement : The set of elements (in the universal set) that do notbelong to a given set:A {x e U x /e A} .4. Difference or Relative Complement : The set of elements that belong to aset but not to another:A - B {x (x e A) (x /e B)} A B .DEPT. OF CSE, ACEPage 6
DISCRETE MATHEMATICAL STRUCTURES15CS365. Symmetric Difference : Given two sets, their symmetric differ- ence is theset of elements that belong to either one or the other set but not both.A B {x (x e A) (x e B)} .It can be expressed also in the following way:A B A B - A B (A - B) (B - A) .Counti witnghA VenndiagramVennDiagra ms:withintersecting the most general way divides thensetsinplaneninto 2 regions. If we haveinformationofthethe diagram, nuse thatinformationplane.theofof someabout numberelementsportionswefind theof in each of the regionscannumberelements andfor theofothe portions ofobtaining numberelements in rtheExample : Let M ,be the sets oftakinmaticPand C studentsg Mathes courses,Physics courses andScience courses respecComputertivelyin a university. Assume M 300, P 350, C 450, M P 100, M C 150, P C 75, M P C 10. Howman student are taking exactly one of thoseyscourses?We see that (M P )-(M P C ) 100-10 90, (M C )-(M P C ) 150 - 10 140 and (P C) - (M P C) 75 10 65.Then the region corresponding t300- 60. Analogously wenumbey(90 10 140) computethe rof studentstakincoursesan takinComputer coursegPhysicsonly (185) dgScience sonly (235).The sum 60 185 235 480 is thetakingnumberof students exactlyoneo f thosecourses.
DEPT. OF CSE, ACEPage 7
DISCRETE MATHEMATICALSTRUCTURES15CS36Ven Diangrams:Ven diagrams are graphicenclosed areas innrepresentations of sets asthe plane.For instance, in figure 2.1, therepresents the universal set (therectangleset of allelements con- sidered in a giventheregion represents seproblem)and shadeda t A.The other figures represent various set operations.CountingwithA VenndiagramnVen Diagranms:with set intersecting th most general way divides thensine planeinto 2 regions. If we have informationth number ofe elementsof some portionsthewe can find the number ofnelements in each of the regions andfortheofobtainingnumberelements in other portions of theaboutof thediagram,use thatinformationplane.Example : Let M ,bePand C thesets of studentstaking Mathe- matics courses,
Physics courses andComputerScience courses respec- tively in a university.Assume M 300, P 350, C 450, M P 100, M C 150, P C 75, M P C 10. Howmany students are taking exactly one of those courses? (fig.2.7)DEPT. OF CSE, ACEPage8
15CS36DISCRETE MATHEMATICAL STRUCTURESWe see that (M P )-(M P C ) 100-10 90, (M C )-(M P C ) 150 - 10 140 and (P C) - (M P C) 75 10 65.Then the region corresponding to students taking Mathematics courses onlyhas cardinality 300-(90 10 140) 60. Analogously we compute thenumber of students taking Physics courses only (185) and taking ComputerScience courses only (235).Gene ral ized Un ionand Inters ec ti on: Given acollec- tion of sets A1 , A2, . . . ,AN , their union is defined as the set of elements that belong to at least oneof the sets (here n represents an integer in the range from 1 to N ):
DEPT. OF CSE, ACEPage 9
15CS36DISCRETE MATHEMATICAL STRUCTURESAnalogously, their intersection is the set ofelements thatthe setssimultaneously:belong to allThese definitions can be applied to infinite collections of sets aswell. For instance assume that Sm {kn k 2, 3, 4, . . . } set ofmultiples of n greater than n. ThenP artitions: Aa set X is a collection S of non overlapping nonpartitionof emptysubsets of X whosethe whole X . For instance a partition of X {1,unionis 2, 3, 4, 5,6, 7, 8, 9, 10} could be S {{1, 2, 4, 8}, {3, 6}, {5, 7, 9, 10}} .Given a partition S of a set X , every element of X belongs to exactly onemember of S.Example : The division of the integers Z into even and odd numbers is apartition: S {E, O}, where E { 2n n e Z}, O { 2n 1 n e Z}.Example : Thepositive integers and zero is a divisions of Z in negativeintegers,-p art itio n: S {Z , Z , {0 }}.Order ed PC ar tes Prodairs,ianuct:ordinar pai {a,setw elementAn yrb}is a twith os.In a set the order of theel ements is irrelevant, {a, b} {b,elemenso a}.If the order of the tsis relevant,the we use a differentcalledrepresented (a, b). Now (a, b) nobjectorderedpair, (b,!!!a) (unless a b). In general (a, b) (a , b ) iff a a!and b b .
Given two sets A, B,Cartesian product A B set of alltheiris theorderedpairs (a, b)such that a e A and b e B :A B {(a, b) (a e A) (b eB)} .Analogously we can define triples or 3-tuples (a, b, c), 4-tuples(a, b, c, d),(a1 , a2, . . . , am ), the. . . , n3-fold, 4-fold,. . .tuplesandcorresponding,DEPT. OF CSE,ACEPage10
DISCRETE MATHEMATICAL STRUCTURES15CS36n-fold Cartesian products:A1 A2 ··· Am {(a1 , a2, . . . , am ) (a1e A1) (a2 e A2) ··· (am e Am )} . A A A, etc. Ingeneral:If all the sets in a Cartesianproduct2the same, then we can use an exponent: A3A A, A(m times) m A A ··· A .A First Word on Probability:I ntroAssumeweexperiment such tossingduction:thatperforman asacoinorrolling a die.se of possibleis calledsampleThet outcomesthespaceof theexperiment.An event is aof the sample space. instanc if wesubsetFor e,tossa cointhreetimes,sample spacethe isS — {H H H, H H T , H T H, H T T , T H H, T H T ,T T H, T T T } .Th eventleast two heads in a row” would bee “atthesubsetE — {H H H, H HT, T HH}.If all possible outcomesexperimentof anhave the same likelihood ofoccurrence,thentheprobabilityof an event A S is give n by Laplace’s rule:For instance, the probability of getting at least two heads in arow in the above experiment is 3/8.are
DEPT. OF CSE, ACE11Page
DISCRETE MATHEMATICAL STRUCTURESThen: Prop er ties of probab ili ty:Let P be a probability15CS36func- tion on a samplespace S.THE CONCEPT OF PROBALITY:Pr(A) A / S where A is an event and S is sample spacePr(A) A / S ( S - A )/ S 1- ( A / S ) 1-Pr(A).Pr(A) 0 if and only if Pr(A) 1 and Pr(A) 1 if and only ifPr(A) 0ADDITION THEROM:Suppose A and B are 2 events is a sample space S then A UB is an event in S consisting ofoutcomes that are in A or B or both and A B is an event is S consisting of outcomes thatarecommon to A and B. accordingly by the principle of addition we have AUB A B - A B and formula 1 givesP r(AUB) AUB / S ( A B - A B )/ S A / S B / S - A B / S P r(AUB) Pr(A) Pr(B)-Pr(A B)DEPT. OF CSE, ACE12Page
DISCRETE MATHEMATICAL STRUCTURES15CS36MUTUALY EXCLUSIVE EVENTS:Two events A and B in a sample space are said to be mutual exclusive if A B Ø then Pr(A B) 0 and the addition theorem reduces to P r(AUB) Pr(A) Pr(B)If A1, A2 .An are mutualy exclusive events, then Pr(A1UA2U .UAn) Pr(A1) Pr(A2) . Pr(An)COND ITIONAL PROBABILITY:If E is an event in a finite sample S with Pr(E) 0 then the probability that an event A in Soccurs when E has already occurred is called the probability of A relative to E or theconditional p robability of A , given EThis p robability, denoted by Pr(A E) is defined by Pr(A E) A E / E from this A E E . Pr(A E) Pr(A E) A E / S E / S . Pr(A E) Pr(E) . Pr(A E)Example : Find the probability of obtaining a sum of 10 after rolling two fair dice. Find theprobability of that event if we know that at least one of the dice shows 5 points.Answer : We call E — “obtaining sum 10” and F — “at least one of the dice shows 5points”. The number of possible outcomes is 6 6 — 36. The event “obtaining a sum 10” is E— {(4, 6), (5, 5), (6, 4)}, so E — 3. Hence the probability is P (E) — E / S — 3/36 — 1/12.Now, if we know that at least one of the dice shows 5 points then the samplespace shrinks toF — {(1, 5), (2, 5), (3, 5), (4, 5), (5, 5), (6, 5), (5, 1), (5, 2), (5, 3), (5, 4), (5, 6)} ,so F — 11, and the ways to obtain a sum 10 are E n F — {(5, 5)}, E n F — 1, so the probability is P (E F ) — P (E n F )/P (F ) — 1/11.MUTUALLY INDEPENDENT EVENTS:The event A and E in a sample space S are said to be mutually independent if the probability ofthe occurrence of A is independent of the probability of the occurrence of E, So thatPr(A) Pr(A E). For such events Pr(A E) Pr(A).Pr(E)This is known as the product rule or the multiplication theorem for mutually independentevents .
A gen eralization of expression is if A1,A2,A3 .An are mutually in dependent events ina sample space S thenPr(A1 A2 An) Pr(A1).Pr(A2) .Pr(An)Example : Assume that the probability that a shooter hits a target is p — 0.7, and that hittingthe target in different shots are independent events. Find:1. The probability that the shooter does not hit the target2. The probability that the shooter does not hit the targetDEPT. OF CSE,ACEin one shot.three times in a row.Page13
DISCRETE MATHEMATICAL STRUCTURES15CS363. The probability that the shooter hits the target at least once after shooting three times.Answer :1. P (not hitting the target in one shot) — 1 — 0.7 — 0.3.32. P (not hitting the target three times in a row) — 0.3 — 0.027.3. P (hitting the target at least once in three shots) — 1—0.027 —0.973.COUNTABLE AND UNCOUNTABLE SETSA set A is said to be the c ountable if A is a finite set. A set which is not countable is called anuncountable set.THE ADDITION PRINCIPLE: AUB A B - A B is the addition principle rule or the principle of inclusion –exclusion. A-B A - A B A B U - A - B A B AUBUC A B C - A B - B C - A C A B C is extended additionprinciple NOTE: A B C AUBUC U - AUBUC U - A - B - C B C A B A C - A B C A-B-C A - A B - A C A B C Fundamentals of Logic:Intr oduction:Propositi ons:A proposition is a declarative sentence that is eithertrue or false (but not both). Forinstance, the following are propositions: “Paris is in France” (true), “London is inDenmark” (false), “2 4” (true), “4 7 (false)”.However the following are notpropositions: “what is your name?” (this is a question), “do your homework” (thisis a command),“this sentence is false” (neither true nor false), “x is an evennumber” (it depends on what x represents),“So crates” (it is not even a sentence).The truth or falsehood of a proposition is called its truth value.Basic Connectives and Truth Tables:DEPT. OF CSE, ACE14Page
DISCRETE MATHEMATICALSTRUCTURES15CS36Connectives are usedfor making compound propositions.the following (p and q represent given clusive OrImplicationBiconditi
OF CSE, ACE Page 5. DISCRETE MATHEMATICAL STRUCTURES 15CS3 6 Empty Set: A set with no elements is called empty set (or null set, or void set ), and is represented by or {}. Note that nothing preven ts a set from possibly being an element of another se t (whic h is not the same as being a subset!). For i n stance
2.1 Sampling and discrete time systems 10 Discrete time systems are systems whose inputs and outputs are discrete time signals. Due to this interplay of continuous and discrete components, we can observe two discrete time systems in Figure 2, i.e., systems whose input and output are both discrete time signals.
6 POWER ELECTRONICS SEGMENTS INCLUDED IN THIS REPORT By device type SiC Silicon GaN-on-Si Diodes (discrete or rectifier bridge) MOSFET (discrete or module) IGBT (discrete or module) Thyristors (discrete) Bipolar (discrete or module) Power management Power HEMT (discrete, SiP, SoC) Diodes (discrete or hybrid module)
Discrete Mathematics is the part of Mathematics devoted to study of Discrete (Disinct or not connected objects ) Discrete Mathematics is the study of mathematical structures that are fundamentally discrete rather than continuous . As we know Discrete Mathematics is a back
Computation and a discrete worldview go hand-in-hand. Computer data is discrete (all stored as bits no matter what the data is). Time on a computer occurs in discrete steps (clock ticks), etc. Because we work almost solely with discrete values, it makes since that
What is Discrete Mathematics? Discrete mathematics is the part of mathematics devoted to the study of discrete (as opposed to continuous) objects. Calculus deals with continuous objects and is not part of discrete mathematics. Examples of discrete objects: integers, distinct paths to travel from point A
Definition and descriptions: discrete-time and discrete-valued signals (i.e. discrete -time signals taking on values from a finite set of possible values), Note: sampling, quatizing and coding process i.e. process of analogue-to-digital conversion. Discrete-time signals: Definition and descriptions: defined only at discrete
2.1 Discrete-time Signals: Sequences Continuous-time signal - Defined along a continuum of times: x(t) Continuous-time system - Operates on and produces continuous-time signals. Discrete-time signal - Defined at discrete times: x[n] Discrete-time system - Operates on and produces discrete-time signals. x(t) y(t) H (s) D/A Digital filter .
CSE 1400 Applied Discrete Mathematics cross-listed with MTH 2051 Discrete Mathematics (3 credits). Topics include: positional . applications in business, engineering, mathematics, the social and physical sciences and many other fields. Students study discrete, finite and countably infinite structures: logic and proofs, sets, nam- .
