Flashcards
Discrete Structures - Inclusion / Exclusion Principles
Cards in this deck (3)
- 1Inclusion / Exclusion Principle- With 2 sets, A and B, the formula is:
|A∪B| = |A| + |B| - |A∩B|
With 3 sets, the formula is:
|A∪B∪C| = |(A∪B)∪C| =
|A∪B| + |C| - |(A∪B)∩C| =
|A|+|B| - |A∩B| + |C| - (|C∩(A∪B)| =
|A|+|B|+|C|-|A∩B|-(|C∩A|+|C∩B|-|(C∩A)∩(C∩B)|)
|A|+|B|+|C|-|A∩B|-|A∩C|-|B∩C|+|A∩B∩C|
- Sum of the cardinalities where the even sets are preceded by negative and odd sets are preceded by positive - 2Inclusion / Exclusion Principle (Example 1)In a group of 42 tourists, everyone speaks English or French; there are 35 english speakers and 18 french speakers.
How many speak both English and French?
E - Set of English Speakers
F - Set of French Speakers
|E| = 35
|F| = 18
|EUF| = 42
|EnF| = x
|EUF| = |E| + |F| - |EnF|
|EnF| = |E| + |F| - |EUF|
|EnF| = 35 + 18 - 42
|EnF| = 11 - 3Inclusion / Exclusion Principle (Example 2)In a group of 24 people who like rock, country, and classical music; 14 like rock, 17 like classical, 11 like both rock and country, 6 like rock and classical, 13 like country and classical, and 8 like rock, country, and classical.
How many like country?
R = Set of people who like Rock
C = Set of people who like Country
L = Set of people who like Classical
|R| = 14
|L| = 17
|C| = X
|RnC| = 11
|RnL| = 9
|CnL| = 13
|RnCnL| = 8
|RUCUL| = 24
|RUCUL| = |R| + |L| + |C| - |RnC| - |RnL| - |CnL| + |RnCnL|
|C| = |RUCUL| - |R| - |L| + |RnC| + |RnL| + |CnL| - |RnCnL|
|C| = 24 - 14 - 17 + 11 + 6 + 13 - 8
|C| = 15
Information
- Description
- Flashcards on Discrete Structures - Inclusion / Exclusion Principles, created by Spencer Ross on 17/12/2018.
- Created by
- Spencer Ross
- Views
- 0
- Rating