Discrete Math Concepts and Set Operations Explained
CSE 20
DISCRETE MATH
C
l
i
c
k
e
r
f
r
e
q
u
e
n
c
y
:
C
A
Todays topics
•
Set operations
•
Vs
•
Venn diagrams
•
Sets equality and how to prove it
•
Power set, Cartesian product
Set operations
JS p. 47
Vs
•
Which one of the following is true?
A.
1
{1,2,3}B.
1
{1,2,3}C.
{1}
{1,2,3}D.
{1}
1,2,3
E.
None/other/more than one
Vs
•
Recall:
•
x
A: x is an
element
in the set A
•
A
B: A is a
subset
of B (all elements of A are also elements of B)
•
Examples:
•
1
{1,2,3}•
{5,7}
{5,6,7}•
Elements can also be set!
•
{1,3}
{{2}, 4, {1,3}}•
We can have set of sets of sets of sets …
Vs
•
Which one of the following is true?
A.
1
{{1},{2},{3}}B.
1
{{1},{2},{3}}C.
{1}
{{1},{2},{3}}D.
{1}
{{1},{2},{3}}E.
None/other/more than one
Vs
•
Which one of the following is true?
{
,{
},{{
}}}
{
,{
},{{
}}}
C.
{
}
{
,{
},{{
}}}
D.
{
}
{
,{
},{{
}}}
E.
None/other/more than one
Venn diagrams
•
An useful way to understand sets intersection & union
•
Generic Venn diagram for 3 sets:
•
Describes all possible
8=2
3
combinations
for whether an
element is in A or not; in B or not; in C or not
Venn diagrams
Venn diagrams
U
B
A
C
Venn diagrams
U
B
A
C
Venn diagrams
U
B
A
C
Set equality
Proving set equality
Proving set equality: simple example
•
X = {n N: n is even}
•
Y = {n N: n+1 is odd}
•
Claim: X=Y
•
Proof that X
Y:
If n X, then n is even, hence n+1 is odd, hence n+1Y
•
Proof that Y
X:
If n Y, then n+1 is odd, hence n is odd, hence nX
Proving set equality: another example
Power Set
JS p. 45
Power Set
•
Which one of the following is always true?
A.
A
P(A)
B.
A
P(A)
C.
{A} P(A)
D.
{A} P(A)
E.
None/other/more than one
Cartesian product
JS p. 48
Cartesian product
Next class
•
More about sets
•
R
e
a
d
s
e
c
t
i
o
n
2
.
1
i
n
J
e
n
k
y
n
s
,
S
t
e
p
h
e
n
s
o
n
Explore key concepts in discrete math, including set operations, Venn diagrams, and proofs of set equality. Learn about unions, intersections, differences, complements, and more through visual aids and examples. Enhance your understanding of elements, subsets, and set relationships with comprehensive explanations and illustrations.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Clicker frequency: CA CSE 20 DISCRETE MATH Prof. Shachar Lovett http://cseweb.ucsd.edu/classes/wi15/cse20-a/
Todays topics Set operations Vs Venn diagrams Sets equality and how to prove it Power set, Cartesian product
Set operations JS p. 47 Union: ? ? = {?:? ? ? ?} Intersection: ? ? = {?:? ? ? ?} Difference: ?\? = ? ??= {? ?: ? ?} ?? = {? ?: ? ?} Complement: (important to know the universe U!) Empty set:
Vs Which one of the following is true? A. 1 {1,2,3} B. 1 {1,2,3} C. {1} {1,2,3} D. {1} 1,2,3 E. None/other/more than one
Vs Recall: x A: x is an element in the set A A B: A is a subset of B (all elements of A are also elements of B) Examples: 1 {1,2,3} {5,7} {5,6,7} Elements can also be set! {1,3} {{2}, 4, {1,3}} We can have set of sets of sets of sets
Vs Which one of the following is true? A. 1 {{1},{2},{3}} B. 1 {{1},{2},{3}} C. {1} {{1},{2},{3}} D. {1} {{1},{2},{3}} E. None/other/more than one
Vs Which one of the following is true? A. { ,{ },{{ }}} B. { ,{ },{{ }}} C. { } { ,{ },{{ }}} D. { } { ,{ },{{ }}} E. None/other/more than one
Venn diagrams An useful way to understand sets intersection & union Generic Venn diagram for 3 sets: U B A C Describes all possible 8=23 combinations for whether an element is in A or not; in B or not; in C or not
Venn diagrams We will use it to prove the following theorem: For any 3 sets A, B, C ?\? ?\? ?\? = U B A C
Venn diagrams Which area(s) represent ?\? ? A. 1,2 B. 2,5,8 C. 1,2,3,4 D. 3,4 E. Other/none/more U B A C
Venn diagrams Which area(s) represent ?\? ? A. 1,4 B. 2,3 C. 8,7 D. 5,6 E. Other/none/more U B A C
Venn diagrams Goal: prove ?\? ?\? ?\? = Which area(s) represent ?\? ? A: 2,3,5,6 B: 3,4,6,7 A\B: 2,5 U B A A\C: 2,3 B\C: 3,4 A\B: 2,5 There is no number that appears in all three lists, so the intersection is empty set C
Algebraic proof of ?\? ?\? ?\? = ?\? ?\? ?\? = (? ??) (? ??) (? ??) (by definition of set difference) = ? ?? ? ?? ? ?? (by associative law removing parentheses) = ? ?? ?? ? (?? ?) (by commutative law, and by associative law adding parentheses) = ? ?? ?? ? (by complement law: any set intersect its complement is empty) = (any set intersect the empty set is the empty set)
Set equality Given sets X and Y X = Y means: ?, ? ? ? ? X Y means: ?, ? ? ? ? Y X means: ?, ? ? ? ? Recall: ? ? is equivalent to ? ? (? ?) So: X=Y is equivalent to X Y and Y X
Proving set equality One way to prove X=Y is in two steps Step 1: prove X Y That is, ?, ? ? ? ? Step 2: prove Y X That is, ?, ? ? ? ?
Proving set equality: simple example X = {n N: n is even} Y = {n N: n+1 is odd} Claim: X=Y Proof that X Y: If n X, then n is even, hence n+1 is odd, hence n+1 Y Proof that Y X: If n Y, then n+1 is odd, hence n is odd, hence n X
Proving set equality: another example Claim: (Ac)c = A Recall definitions: ? ? Equivalently: ? ?? ? ?? ? ? Proof that A (Ac)c: If x A, then x Ac, hence x (Ac)c Proof that (Ac)c A: If x (Ac)c, then x Ac, hence x A
Power Set JS p. 45 Set A P(A) = set of all subsets of A = {?:? ?} What is P({1,2})? A. {1, 2, {1,2}} B. {{1}, {2}, {1,2}, } C. {1, 2, {1,2}, {2,1}} D. None/other/more than one
Power Set Which one of the following is always true? A. A P(A) B. A P(A) C. {A} P(A) D. {A} P(A) E. None/other/more than one
Cartesian product JS p. 48 ? ? = { ?,? :? ?,? ?} What is {1,2} x {1,2,3} ? A. {1, 2, 3} B. {(1,1), (2,2), ( ,3)} C. {(1,1),(1,2),(1,3),(2,1),(2,2),(2,3)} D. {(1),(1,2),(1,3),(2),(2,3)} E. None/other/more than one
Cartesian product ? ? = { ?,? :? ?,? ?} Is {1,2} x {1,2,3} = {1,2,3} x {1,2} ? A. Yes B. No
Next class More about sets Read section 2.1 in Jenkyns, Stephenson
