Honors Discrete Mathematics
Honors Discrete Mathematics MAD 2104
Popular in Course
Popular in Mathematics Discrete
This 18 page Class Notes was uploaded by Chaya Botsford II on Monday October 12, 2015. The Class Notes belongs to MAD 2104 at Florida Atlantic University taught by Jorge Viola-Prioli in Fall. Since its upload, it has received 45 views. For similar materials see /class/221637/mad-2104-florida-atlantic-university in Mathematics Discrete at Florida Atlantic University.
Reviews for Honors Discrete Mathematics
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/12/15
110PERATIONS WITH SETS We will devote this section to three basic operations with set and to the analysis of the InclusionExclusion Formula which is an additional counting principle Given sets A and B the union of A and B is the set de ned as x39 x E A or x EB This set is denoted by A U B J Viola Prioli 3 395 m 038 303 Em gmmsio 33 3 gt C m u m C gt B gt C gt u gt gtC ugt gtmgtcmm3mmgtcm C 30336 The union of A and B can be represented by the following Venn diagram J Viola Prioli The dual notion intersection is introduced next Given sets A and B we de ne the intersection ofA and B as x39 x E A and x E B This set is denoted by A D B It follows at once from the de nition that 1 A D B B D A 2 A D A A 3 A D Q Q 4A BQA andA BQB J Viola Prioli The intersection of A and B can be represented by the following Venn diagram A J Viola Prioli Theorem 113 gives the most basic properties involving these two operations Let us pose to state and prove for instance one of them as an illustration Claim given sets A B and Cwe have A U B n C A U B n A U C You are invited to visualize the statement with the help of a Venn diagram Proof of our claim Call X A U B D C and Y A U B D A U C and proceed to show that X Y To that end we must prove that X Q Y and also Y Q X To see that X Q Y we must prove that quotif x E X then x E Y This is ofthe form quotif P then Q where P means x E X and Q means x E Y J Viola Prioli Unravel P x E A U B D C equivalently x E A or x E B D C Equivalently xEAorxEB andeC Unravel Q x E A U B D A U C equivalently x E A U B and x E A U C Equivalently xEA or xE B and xEA or xEC In we must explore the two possible cases to produce the link from P to Q Case a x E A Therefore x E A or x E B clearly Likewise x E A or x E C Thus x E A or x E B and x E A or x E C hence holds Case b x E B and x E C Since x E B we have that x E A or x E B and since x E C it follows that x E A or x E C Given that this is occurring simultaneously we have that x E A or x E B and x E A or x E C so holds also in this second case Having proved that X Q Y we leave the other containment that is Y Q X as a good practice exercise J Viola Prioli Recall that with A we denote the number of elements of the set A We are interested in computing the size of the union of two arbitrary sets that is IA U BThe answer is given in TH Let A and B be sets with nitely many elements Then AUB IA B A B Proof Recall that in any set the elements must be different If any ofthe sets is empty the equality follows at once do you see why We might then assume they are nonempty say A a1 an and B b1 bm Since some elements may appear in both sets we rearrange all the elements by writing A C1 cp a1 at and Bc1 cp b1 b5 where c1 cp denotes the common elements J Viola Prioli Observethatptn A ps m B and p A BOntheotherhand AUB c1cpa1atU c1cpb1bsc1cpa1atb1bs Therefore AU B pts ptp s p A B A 0 BI and the formula has been proved REMARK Notice that in general A U B at A B What the theorem shows is that by computing A B we are quotover counting that is we are counting twice the elements of the intersection so we must adjust the calculation by subtracting IA 0 Bl Two sets A and B are called disjoint when A D B is empty Hence A and B are disjoint ifand only A D B Q and this occurs if and only if IA 0 Bl 0 Therefore when dealing with nite sets A and B are disjoint if and only if AUB A B J Viola Prioli A survey reveals that 150 students either swim or jog 85 of them swim and 60 students swim and jog Find the number of students thatjog Solution Call 5 the set of students that swim and call J the set of students that jog Recall that in Math the g is inclusive Hence some of the 150 students that swim orjog may be involved in both activities Observe that we are looking for JSince 150 SUJ S J S ll 85 J 60 25 Jweinferthat J 125 The textbook leaves as an exercise the important InclusionExclusion formula for three sets AUBUC IA B IC A B IA CI IB CI IA B CI J Viola Prioli Hint to prove this formula call X A U B replace in the left hand side and use the previous theorem together with the De Morgan s Laws It is not hard Remarks a The theorem can be thought of as the InclusionExclusion formula for only two sets b The InclusionExclusion formula can be extended to more than three sets although we will not make use ofthat generalization in what follows APPLICATIONHow many numbers in the set 1 2 1000 are divisible by 2 by 3 or by 5 Solution Let all small cap letters indicate integers J Viola Prioli Set A 2n39 1 s 2n 51000 B 3k 1 s 3k s 1000 c 5t 1 S St 51000 Accordingly we are asked to compute IA U B U CI In A the values of n run from 1 to 500 so A 500 In B k runs from 1 to 333 and so B 333 Likewise C 200 A D B 2n39 1 S 2n S1000 0 3k39 1 S 3k S 1000 which is the set of multiples of six that are less than 1000 Hence A D B 6w 1 S 6w S1000 Therefore IA 0 Bl 166 In a similarfashion we have IA 0 CI 100 and IB 0 CI 66 Verify this On the other hand A D B D C 30y39 1 S 30y S1000 thus IA 0 B 0 CI 33 We apply next the InclusionExclusion formula and obtain A U B U C IA B C A B IA CI B C A B C500333 200 166 100 66 33 734 Therefore there are 734 numbers from 1 to 1000 that are divisible by 2 by 3 or by 5 J Viola Prioli Observe that we did not embark into listing those numbers we just computed how many there are thus answering our question Another operation is introduced next Given sets A and B their difference is de ned as x39 x E A and x i B This set is denoted by A B Please notice that the notation is suggestive quotremove from A those elements of B It should be emphasized that A B does not involve an algebraic operation but a symbol to denote the construction ofthis new set J Viola Prioli The difference can be represented by the following Venn diagram J Viola Prioli It follows at once from the de nition that 1 A A Q 2 A Q A 3 A B is different from B A in general Exercise By resorting to the de nitions prove that A B A A D B Make also a Venn diagram to visualize the statement CAUTION A B is not A B So how do we compute A B See the next PROPOSITION A B A IA 0 3 Proof We just need to observe that A B and A D B are disjoint sets whose union is A Therefore A A B IA 0 Bl from which we can solve for A B J Viola Prioli APPLICATION In a study of 260 patients and two drugs A and B it was found that 140 were affected by drug A 210 were affected by affected by B Find how many patients were a b c d affected by both affected by A but not by B affected by just one drug not affected by either drug VV VV at least one drug and 100 were Solution Call for simplicity A the set of patients affected by drug A and B those patients affected by drug B Recallthat A U B IA B IA 0 Bl Accordingly we have A140 B 100 A U El 210 Therefore we inferthat IA 0 Bl A B A U B 140 100 21030 J Viola Prioli a we look for IA 0 Bl which was found to be 30 b we must compute A B A IA B 140 30 110 c it means it could be A and not B orB and not AThus we must nd IABl B AA IA Bl B IA BI 110 10030180 d we search for those elements that are outside A and outside B So we must remove from the universe of patients those in A U B Hence the answer is 260 210 50 J Viola Prioli It follows at once from the de nition that 1 A A B B A A 2 A B B A and A D B are pairwise disjoint 3 A A B and A D B are disjoint PROPOSITION AABA U B A DB Proof Left as an exercise Another important operation with sets is the Cartesian product Given sets A and B we de ne the Cartesian product of A and B as a b a E A and b E B This set is denoted by A x B J Viola Prioli
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'