CSD101 - Discrete Structures
(Discrete Mathematics)
Spring 2016
Lecture - 9
Set Operations
Set Operations
Two sets can be combined in many different ways.
Set operations can be used to combine sets.
Union
Let A and B be sets.
The union of A and B, denoted by A B, is the set
containing those elements that are either in A or in B, or in
both.
A B = {x | x A x B}
Intersection
Let A and B be sets.
The intersection of A and B, denoted by A B, is the set
containing those elements in both A and B.
A B = {x | x A x B}
Union (example)
Let A = {1,2,3}
B = {2,4,6,8}
A B = {1,2,3,4,6,8}
Let A = {x | x Z x is even}
B = {x |x Z x is odd}
AB =Z
Intersection (example)
Let A = {1,2,3}
B = {2,4,6,8}
AB ={2}
Let A = Z
B = {x |x Z x is odd}
A B = {x |x Z x is odd}
Disjoint Sets
Two sets are called disjoint if their intersection is empty.
Let A = {x | x Z x is even}
B = {x |x Z x is odd}
AB =
The Cardinality of the Union of Sets
|A B|=?
Solution:
Let A = {1,2,3}
B = {2,3,4}
A B = {1,2,3,4}
|A| = 3
|B| = 3
|A B|=4
|A B| = |A| + |B| - |A B|
Difference
Let A and B be sets.
The difference of A and B, denoted by A - B, is the set
containing those elements that are in A but not in B. (also
called complement of B with respect to A).
A - B = {x | x A x B}
Difference (example)
Let A = {1,2,3}
B = {2,4}
A B = {1,3}
Let A = Z
B = { x | x Z x is odd }
A B = { x | x Z x is even }
Complement
Let U be the universal set and A be a set.
The complement of A, denoted by A, is the complement
of A with respect to U (which is U - A).
A=
x xA}
Complement (example)
Let A = { a, b, c, d } and
U is the set of English alphabet
A = { e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z }
Let A = { x | x Z x is odd } and
U is Z
A = { x | x Z x is even }
Summary Set Operations
Operation
Notation
Union
A B = {x | x A x B}
Intersection
A B = {x | x A x B}
Difference
A - B = {x | x A x B}
Complement (U - A)
A= x xA}
Set Identities
A=A
AU=A
Identity Laws
AU=U
A=
Domination Laws
AA=A
AA=A
Idempotent Laws
(A) = A
Complementation Law
A A=U
AA=
Complement Laws
Set Identities
AB=BA
AB=BA
Commutative Laws
A (B C) = (A B) C
A (B C) = (A B) C
Associative Laws
A (A B) = A
A (A B) = A
Absorption Laws
Set Identities
A B=A B
A B=A B
De Morgans Law
A (B C) = (A B) (A C)
A (B C) = (A B) (A C)
Distributive Law
How to Prove a Set Identity
Four methods:
Use the basic set identities
Use membership tables
Prove each set is a subset of each other
Use set builder notation and logical equivalences
Set Identities (example)
( ) = ( ) .
Solution:
( ) =
=
=
( ) =
( )
( )
( )
( )
( )
What is a membership table
Membership tables show all the combinations of sets an
element can belong to
1 means the element belongs, 0 means it does not
Consider the following membership table:
AB
AB
A-B
Membership Table
A (B C) = (A B) (A C)
A (B C) = (A B) (A C)
Distributive Law
A
BC
A (B C)
AB
AC
(A B) (A C)
Proof by showing each set is a subset of the
other
Assume that an element is a member of one of
the identities
Then show it is a member of the other
Example
Show =
Solution:
Part 1:
Ass
( )
Definition of Intersection
( )
Definition of Union
( ) Distributive Law
( ) ( ( ))
Definition of Intersection
( ) ( )
Definition of Union
,
Example
Show =
Solution:
Part 2:
Ass
( )
Definition of Union
( ) Definition of Intersection
( )
Distributive Law
( )
Definition of Union
( )
Definition of Intersection
,
,
Proof by set builder notation and logical
equivalences
First, translate both sides of the set identity into
set builder notation
Then use one side (or both) to make it identical to
the other
Do this using logical equivalences
Set Builder Notation and Logical Equivalences
(Example)
Show A B = A B
Solution:
= {| }
=
=
=
=
=
= {| }
=
Definition of Complement
Definition of does not belong symbol
Definition of intersection
DeMorgans Law
Definition of does not belong symbol
Definition of Complement
Defintion of Union
By meaning of Set Builder Notation
Exercise
Let A, B and C be sets, use membership table method,
set identities method and set builder notation method to
show that
=
=
( ) =
=
2 and 3 - Set Venn Diagram
|A B| = |A| + |B| - |A B|
|A B C | = |A| + |B| +|C| - |A B| - |A C| - |B C| +
|A B C |
Example
Suppose a list A contains the 30 students in a mathematics
class, and a list B contains the 35 students in an English
class, and suppose there are 20 names on both lists.
Find the number of students:
only on list A
only on list B
on list A or B (or both),
on exactly one list.
Example
Solution:
30 20 = 10 names are only on list A.
35 20 = 15 are only on list B.
|A B|= |A|+ |B| |A B| = 30 + 35 20 = 45.
10 + 15 = 25 names are only on one list; that is,
|A B| = 25.
Example
Consider the following data for 120 mathematics students
at a college concerning the languages French, German,
and Russian:
65 study French,
45 study German,
42 study Russian , 20 study French and German,
25 study French and Russian,
15 study German and Russian.
8 study all three languages.
Determine how many students study exactly 1 subject and
fill the correct numbers of students in each eight region of
Venn diagram shown in figure.
Example
Total number of students exactly registered in one course
= 28+18+10=56
Exercise Questions
Chapter # 2
Topic # 2.2
Question # 1, 2, 3,4,5,6,15,16,17,18,
19,20,21,22,23,24,25
