Checking Elements of Disjoint Sets: The Addition Rule

0
0
1504 days ago, 534 views
PowerPoint PPT Presentation
Including Elements Disjoint Sets. Hypothesis: Let {A1,

Presentation Transcript

Slide 1

Tallying Elements of Disjoint Sets: The Addition Rule Lecture 29 Section 6.3 Mon, Mar 19, 2007

Slide 2

Counting Elements in Disjoint Sets Theorem: Let { A 1 , … , A n } be a segment of a set A . At that point |A | = |A 1 | + … + |A n |. Culmination: Let { A 1 , … , A n } be a gathering of pairwise disjoint limited sets. At that point |A 1  …  A n | = |A 1 | + … + |A n |.

Slide 3

Counting Elements in Subsets Theorem: Let An and B be limited sets with B  A . At that point |A – B | = |A | – |B |. Verification: { B , A – B } is a parcel of A . In this way, |B | + |A – B | = |A |. In this way, |A – B | = |A | – |B |.

Slide 4

Counting Elements in Unions of Sets Theorem: Let An and B be any limited sets. At that point |A  B | = |A | + |B | – |A  B |. Verification: One can check that ( A  B ) – B = A – ( A  B ). Moreover, B  A  B and A  B  A . In this way, |A  B | – |B | = |A | – |A  B |. In this way, |A  B | = |A | + |B | – |A  B |.

Slide 5

Putnam Problem A-1 (1983) what number positive whole numbers n are there to such an extent that n is a correct divisor of no less than one of the numbers 10 40 , 20 30 ? Let A = { n | n partitions 10 40 }. Let B = { n | n separates 20 30 }. At that point |A  B | = |A | + |B | – |A  B |.

Slide 6

Putnam Problem A-1 (1983) Prime factorization: 10 40 = 2 40  5 40 . Hence, n | 10 40 if and just if n = 2 a 5 b where 0  a  40 and 0  b  40. There are 41  41 = 1681 such numbers. Also, 20 30 = 2 60 5 30 , so there are 61  31 = 1891 divisors of 20 30 .

Slide 7

Putnam Problem A-1 (1983) Finally, a number is in A  B on the off chance that it partitions both 10 40 and 20 30 . That implies that it partitions the gcd of 10 40 and 20 30 . The gcd of 2 40  5 40 and 2 60  5 30 is 2 40  5 30 . Thusly, there are 41  31 = 1271 such numbers.

Slide 8

Putnam Problem A-1 (1983) Thus, 1681 + 1891 – 1271 = 2301 numbers partition either 10 40 or 20 30 .

Slide 9

Number of Elements in the Union of Three Sets Theorem: Let A , B , and C be any three limited sets. At that point |A  B  C | = |A | + |B | + |C | – |A  B | – |A  C | – |B  C | + |A  B  C |. Include sets each one in turn, Subtract sets two at any given moment, Add sets three at any given moment.

Slide 10

Number of Elements in the Union of Three Sets Theorem: Let A , B , and C be any three limited sets. At that point |A  B  C | = |A | + |B | + |C | – |A  B | – |A  C | – |B  C | + |A  B  C |. Include sets each one in turn, Subtract sets two at any given moment, Add sets three at any given moment.

Slide 11

Number of Elements in the Union of Three Sets Theorem: Let A , B , and C be any three limited sets. At that point |A  B  C | = |A | + |B | + |C | – |A  B | – |A  C | – |B  C | + |A  B  C |. Include sets each one in turn, Subtract sets two at any given moment, Add sets three at any given moment.

Slide 12

Proof, proceeded with Proof: |A  B  C | = |A  B | + |C | – | ( A  B )  C |.

Slide 13

Proof, proceeded with Proof: |A  B  C | = |A  B | + |C | – | ( A  B )  C | = |A | + |B | – |A  B | + |C | – | ( A  B )  C |.

Slide 14

Proof, proceeded with Proof: |A  B  C | = |A  B | + |C | – | ( A  B )  C | = |A | + |B | – |A  B | + |C | – | ( A  B )  C | = |A | + |B | – |A  B | + |C | – | ( A  C )  ( B  C )| .

Slide 15

Proof, proceeded with Proof: |A  B  C | = |A  B | + |C | – | ( A  B )  C | = |A | + |B | – |A  B | + |C | – | ( A  B )  C | = |A | + |B | – |A  B | + |C | – | ( A  C )  ( B  C )| = |A | + |B | – |A  B | + |C | – |A  C | – |B  C | + | ( A  C )  ( B  C )| .

Slide 16

Proof, proceeded with Proof: |A  B  C | = |A  B | + |C | – | ( A  B )  C | = |A | + |B | – |A  B | + |C | – | ( A  B )  C | = |A | + |B | – |A  B | + |C | – | ( A  C )  ( B  C )| = |A | + |B | – |A  B | + |C | – |A  C | – |B  C | + | ( A  C )  ( B  C )| = |A | + |B | – |A  B | + |C | – |A  C | – |B  C | + |A  B  C | .

Slide 17

Proof, proceeded with Proof: |A  B  C | = |A  B | + |C | – | ( A  B )  C | = |A | + |B | – |A  B | + |C | – | ( A  B )  C | = |A | + |B | – |A  B | + |C | – | ( A  C )  ( B  C )| = |A | + |B | – |A  B | + |C | – |A  C | – |B  C | + | ( A  C )  ( B  C )| = |A | + |B | – |A  B | + |C | – |A  C | – |B  C | + |A  B  C |. = |A | + |B | + |C | – |A  B | – |A  C | – |B  C | + |A  B  C |.

Slide 18

Proof, proceeded with Proof: |A  B  C | = |A  B | + |C | – | ( A  B )  C | = | A | + |B | – |A  B | + |C | – | ( A  B )  C | = |A | + |B | – |A  B | + |C | – | ( A  C )  ( B  C )| = |A | + |B | – |A  B | + |C | – |A  C | – |B  C | + | ( A  C )  ( B  C )| = |A | + |B | – |A  B | + |C | – |A  C | – |B  C | + |A  B  C |. = |A | + |B | + |C | – |A  B | – |A  C | – |B  C | + |A  B  C |.

Slide 19

The Inclusion/Exclusion Rule Theorem: Let A 1 , … , A n be limited sets. At that point |A 1  …  A n | =  i |A i | –  i  j > i |A i  A j | +  i  j > i  k > j |A i  A j  A k | :  |A 1  …  A n |.

Slide 20

The Inclusion/Exclusion Rule The Inclusion/Exclusion Rule can be demonstrated by enlistment.

Slide 21

Number of Elements in the Union of Four Sets Let U be the arrangement of all sets of particular cards from a deck of 52 playing cards. What number of sets are there in which no less than one of the two cards is dark or a face card?

Slide 22

Number of Elements in the Union of Four Sets Let A = all sets where 1 st card is dark. B = all sets where 1 st card is a face card. C = all sets where 2 nd card is dark. D = all sets where 2 nd card is a face card. Locate the quantity of components in | A  B  C  D |.

Slide 23

Number of Elements in the Union of Four Sets what number sets are there in which no less than one of the two cards is dark or a face card?

Slide 24

A B E D C The Inclusion/Exclusion Rule Suppose five sets converge as showed in the accompanying Venn graph.

Slide 25

A B E D C The Inclusion/Exclusion Rule State the condition of the consideration/rejection administer for these sets.

Slide 26

D A B C The Inclusion/Exclusion Rule Do the same for these sets.

SPONSORS