Discrete Math EECS 203
Popular in Course
Popular in Engineering Computer Science
This 15 page Class Notes was uploaded by Ophelia Ritchie on Thursday October 29, 2015. The Class Notes belongs to EECS 203 at University of Michigan taught by Staff in Fall. Since its upload, it has received 18 views. For similar materials see /class/231553/eecs-203-university-of-michigan in Engineering Computer Science at University of Michigan.
Reviews for Discrete Math
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 10/29/15
Recursive de nitions of sets 0 We saw last time how to de ne the set of proposi tional expressions recursively o The method extends to other kinds of sets Let S be the subset of N de ned by the following rules 1 3 E S 2 imeSandyESthenstryES 3 No number is in S unless it can be shown to be there using 1 and 0 Example 3 Srule1 63368by1andrule2 96SESby2 andrule2 Using induction along with recursive de nitions Proposition The set S on the last sltde ts the set of postttve multiples of 5 Proof Let P be the set of positive multiples of 3 We show P g S and S g P For the rst inclusion7 we show that every integer of the form 3717 for n 2 17 is in S We do this by induction on n Basis When n 17 the number 3 1 E S by rule 1 Induction step Assume that 3k is in S We want 3k 1 E S But 3k l 3k 3 By inductive hypothesis 3k E S7 and 3 is already in S7 so 3k 3 E S by rule 2 Proof continued S g P To show this7 we rely on rule 37 which says nothing is in S unless you can show it in a nite number of uses of rules 1 and 2 Let n be the number of uses of these rules We show by induction on n that the integer proved to be in S is in fact a positive multiple of 3 Basis We just apply one rule7 which has to be rule 1 This rule shows 3 E S7 and 3 is a positive multiple of 3 Induction step strong form Assume that when ever we show that p E S by using k or fewer steps7 then p is a positive multiple of 3 Consider a proof using k 1 steps The last rule used in this proof is rule 27 which says that if 13 and y are in S7 so is 33 11 Now 13 was shown in S by g k steps7 and so was y By inductive hypothesis twice7 we know that 13 and y are positive multiples of 37 and therefore so is a y Relations Chapter 6 o lntuitively7 relations are properties that hold among things in a world 0 For example loves uncleof friend of left of small 0 All except the last of these hold between two things They are called binary relations Small is a unamy relation 0 You can also have ternary relations7 etc Relations involving more than one world 0 For example7 students and courses John EECSSOS Ed EECS 37 6 John EECS28O Mary Math606 Mary Math747 Paul Math747 John Math606 0 You can look at each row of the table as an ordered pair7 and the table as a set of ordered pairs 0 That7s the o icial de nition of binary relation be tween two sets77 Of cial Relation De nitions 0 De nition Let AB be sets A binary relation between A and B is a subset R of A x B A binary relation on A is a subset ofA X A 0 Example S J0hn Ed Mary Paul C E203 E376 E280 M606 M747 ENROLLED John E203 John E376 Ed E280 Mary M606 Mary M747 Paul M747 0 The relation ENROLLED g S X C 0 Notation we write a B b to mean 11 E B Thus John ENROLLED E376 Picturing Relations COU RS ES STU D ENTS EECS203 J h EECSS76 Ed EECSZSO Mary Math606 Math747 Paul Enrollment a relation between students and courses EECSZOS EECS376 EECS EECSZBO 39 ath Math606 Ling Math747 COURSES DEPARTMENTS quotOfferedbyquot a relation between courses and departments Array matrix representation of relations 0 The enrolled information can be presented SC E203 E376 E280 M606 M747 John 1 1 O O 0 Paul O O O O 1 Mary 0 O O 1 1 Ed 0 O 1 O O o This can be seen as a function from S X C to 0 1 1 if 56 E ENR 0 otherwise FENRltS C Relations as maps to a powerset o A relation from A to B can be thought of as a func tion from A to 733 John H E203 E376 Paul gt M 606 Mary H M606 M747 Ed H E280 c There are lots of mathematical ways to model rela tions Relations on a set 0 The set can be in nite 0 Example A N DIV m n m divides 0 Some ordered pairs 11036420 0 We write m I n to indicate that mm E DIV Thus110 36 420 o The less than or equal td7 relation on R is another example of a binary relation on an in nite set Picturing a relation on a nite set A Don tneedtwocopiesof theset A V SupposeAabcdeand Rdadcabbcbeee JustworkwithonecopyofA Properties of Relations on a set 0 De nition A binary relation R on a set A is said to be reflexive if Va E Aa R a o In terms of the graph picture7 there is a self loop at every node 0 O 0 Example On every set A there is the identity relation idA aa la E A o Other examples the less than or equal td7 relation 3 on R the subset relation on 73X7 because Y g Y for any set Y the divides relation on N5 Symmetric Relations 0 De nition A binary relation R on a set A is said to he symmetric if VabEAaRb gtbRa o In terms of pictures Symmetric Not Symm elric Got Symmetric 0 Example The mutual friend 0 relation is symmetric The sister relation isn t The sib ling relation is The identity relation is The relation isn t 77 Transitive Relations 0 De nition A binary relation R on a set A is said to be transitive if Vabc AaRbbRc gtaRc o The pictures This picture holds evenwhere This is ok This isn t
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'