### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# Honors Discrete Mathematics MAD 2104

FAU

GPA 3.65

### View Full Document

## 45

## 0

## 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.

## Similar to MAD 2104 at FAU

## Popular in Mathematics Discrete

## Reviews for Honors Discrete Mathematics

### 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

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### 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'

## Why people love StudySoup

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

#### "I bought an awesome study guide, which helped me get an A in my Math 34B class this quarter!"

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

#### "It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.