Set Operations
The main purpose for this lesson is to introduce the
following:
❑ define the operations of sets and examples.
❑Some concepts of set.
❑Computer Representation of Sets
The Union
DEFINITION 1
• Let A and B be sets. The union of the sets A and B ,
denoted by A U B , is the set that contains
those elements that are either in A or in B , or in both.
• An element x belongs to the union of the sets A and
B if and only if x belongs to A or x belongs to B .
• This tells us that
A U B = {x | x ϵ A V x ϵ B } .
EXAMPLE 1
The union of the sets {1,3,5} and {1,2,3} is the
set {1,2,3,5} ; that is,
{1,3,5} U {1,2,3} = {1,2,3,5} .
The Intersection
DEFINITION 2
Let A and B be sets. The intersection of the sets A
and B , denoted by A ∩ B , is the set
containing those elements in both A and B .
• An element x belongs to the intersection of the
sets A and B if and only if x belongs to A and x
belongs to B .
• This tells us that
A ∩ B = {x | x ϵ A Λ x ϵ B } .
EXAMPLE 2
The intersection of the sets {1,3,5} and {1,2,3} is
the set {1,3} ; that is, {1,3,5} ∩ {1,2,3} = {1,3} .
Disjoint Sets
DEFINITION 3
Two sets are called disjoint if their intersection
is the empty set.
EXAMPLE 3
Let A = {1,3,5,7,9} and B = {2, 4, 6, 8 , 10} .
Because 𝐴 ∩ 𝐵 = ∅, A and B are disjoint.
The Cardinality Of a Union Of Two Finite Sets
Note that I A I + I B I counts each element that is
in A but not in B or in B but not in A exactly
once, and each element that is in both A and B
exactly twice. Thus, if the number of elements
that are in both A and B is subtracted from
IAI+ IBI , elements in A∩B will be counted only
once.
Hence, |𝑨 ∪ 𝑩| = | 𝑨 | + | 𝑩 | − | 𝑨 ∩ 𝑩 | .
• The generalization of this result to unions of
an arbitrary number of sets is called the
principle of inclusion-exclusion.
The Difference Of Two Sets
DEFINITION 4
• 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 .
• The difference of A and B is also called the
complement of B with respect to A.
• An element x belongs to the difference of A and B if
and only if x ϵ A and x ɇ B . This tells us that
𝐴 − 𝐵 = {𝑥 | 𝑥 𝜖 𝐴 ∧ 𝑥 ∉ 𝐵 } .
Remark: The difference of sets A and B is sometimes
denoted by A\B.
EXAMPLE 4
The difference of {1,3,5} and {1,2,3} is the set
{5}; that is, {1,3,5} - {1,2,3} = {5} .
Caution!
This is different from the difference of {1,2,3}
and {1,3,5} , which is the set {2}.
{1,2,3}- {1,3,5} = {2}.
The Complement Of a Set
DEFINITION 5
• Let U be the universal set. The complement of
the set A , denoted by Ā , is the complement of A
with respect to U.
• In other words, the complement of the set A is
Ā = 𝑈 − 𝐴.
• An element belongs to Ā if and only if x ɇ A . This
tells us that
Ā = {𝒙 | 𝒙 ɇ 𝑨 } .
Example 5 (3/136)
Let A = {1, 2, 3, 4, 5} and B = {0, 3, 6}. Find
c) A-B d) B-A
Solution:
c) A-B =
d) B-A=
Remark:
It is left to the reader to show that we can
express the difference of A and B as the
intersection of A and the complement of B.
That is,
ത
A − B = A ∩ 𝐵.
Example: Use set builder notation and logical
equivalences to establish the first De Morgan law
𝐴 ∩ 𝐵 = 𝐴ҧ ∪ 𝐵ത
Example:
Generalized Unions and Intersections
Example:
Computer Representation of Sets
• Assume that the universal set U is finite.
• First, specify an arbitrary ordering of the
elements of U, for instance 𝑎1 , 𝑎2 , … , 𝑎𝑛 .
• Represent a subset A of U with the bit string
of length 𝑛, where the ith bit in this string is 1
if 𝑎𝑖 belongs to A and is 0 if 𝑎𝑖 does not belong
to A.
Example:
Let 𝑈 = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10},
• Represent the subset of All odd integers
{1,3,5,7,9} in U by 10 1010 1010.
• we represent the subset of all even integers in
U, namely, {2, 4, 6, 8, 10}, by the string
01 0101 0101.
• The set of all integers in U that do not exceed
5, namely, {1, 2, 3, 4, 5}, is represented by the
string 11 1110 0000.
Notes:
• Using bit strings to represent sets, it is easy to
find complements of sets and unions,
intersections, and differences of sets. To find
the bit string for the complement of a set from
the bit string for that set, we simply change
each 1 to a 0 and each 0 to 1,(see example 19
in book).
What about union and intersection ?
Example:
HomeWorks
Page 136/137
• 3
• 5
• 14
• 19
• 25
• 27
• 29
• 52,53
• 59