Transcript Set Operations

Section 1.7
Set Operations
1
Union
• The union of 2 sets A and B is the set
containing elements found either in A, or in
B, or in both
• The denotation for A union B is A  B
• Union is related to disjunction, as follows:
A  B = { x | (x  A)  (x  B) }
2
Venn Diagrams
A Venn diagram is a pictorial representation of sets and set
operations. The background of the diagram represents the universal
set, and each set involved in the operation is depicted as a circle
The shaded region of the diagram represents the operation shown
3
Intersection
• The intersection of 2 sets A & B is the set
containing only those elements found in
both A and B
• Intersection is denoted with the symbol 
• Intersection is related to conjunction as
union is related to disjunction:
A  B = { x | (x  A)  (x  B) }
• 2 sets are disjoint if their intersection is the
empty set
4
Intersection
The Venn diagram for intersection:
5
Cardinality of the Union of 2 Sets
• |A| + |B| is the sum of the number of elements in
both sets
• Since the sets may intersect, we need to subtract
the cardinality of the intersection in order to count
the elements in each set only once; Thus:
|A  B| = |A| + |B| - |A  B|
• Generalization of this result to an arbitrary number
of sets is called the principle of
inclusion/exclusion
6
Difference of 2 Sets
• Denoted A - B, is the set containing only
those elements that are in the first set but
not in the second set
• Therefore:
A - B = { x | (x  A)  (x  B) }
7
Difference of 2 Sets
8
Difference of 2 Sets
Let A = {a, b, c, d} and B = {c, d, e, f}
Then A - B = {a, b} and
B - A = {e, f }
9
Complement of a Set
• The complement of a set is the set of all
elements found in the universal set
EXCEPT the elements of the set in question
• The complement of set A is denoted as
follows:
A={x|xA}
10
Complement of a Set
11
Set Identities
• The next several slides introduce set
identities
• As will be evident from their names, these
identities are analogous to the the logical
equivalences we saw earlier
12
Identity Laws
A =A
AU=A
13
Domination Laws
AU=U
A=
14
Idempotent Laws
AA=A
AA=A
15
Complementation
(A) = A
16
Commutative Laws
AB=BA
AB=BA
17
Associative Laws
A  (B  C) = (A  B)  C
A  (B  C) = (A  B)  C
18
Distributive Laws
A  (B  C) = (A  B)  (A  C)
A  (B  C) = (A  B)  (A  C)
19
DeMorgan’s Laws
AB=AB
AB=AB
20
Proving Set Identities
• Method 1: Show that each set is a subset of
the other
• Method 2: Use set builder notation and the
rules of logic
• Method 3: Use membership tables
(analogous to truth tables)
21
Proving Set Identities: Subsets
The text provides a proof of DeMorgan’s second law; here is a proof
of DeMorgan’s first law: A  B = A  B
Suppose x  A  B. In other words, x  A  B - therefore,
x  A and x  B, and x  A  B. Thus, A  B  A  B
Now, suppose x  A  B. This means x  A and x  B, so
x  A  B, or x  A  B. Thus, A  B  A  B
Since each set is a subset of the other, the two sets must be equal
and the identity is proved.
22
Using Set Builder Notation &
Rules of Logic
Again, a proof of DeMorgan’s first law: A  B = A  B
AB={x|xAB}
= { x | ( x  A  B }
= { x | ( x  A  x  B) }
= { x | x A  x  B } by DeMorgan’s Law
= { x | x  A  x  B) }
={x|xAB }
23
Using Membership Tables
• Consider each combination of sets an
element can belong to
• A 1 indicates an element belongs to a set; a
0 indicates the element doesn’t belong
• Verify that elements in the same
combination of sets belong to both sets in
the identity
24
One more time, DeMorgan’s Law
AB=A B
A
1
1
0
0
B
1
0
1
0
A
0
0
1
1
B
0
1
0
1
AB
1
1
1
0
AB
0
0
0
1
AB
0
0
0
1
25
Generalized Unions &
Intersections
• The union of a collection of sets is the set
containing those elements that are members
of at least one set in the collection
• The intersection of a collection of sets is the
set that contains those elements that are
members of all sets in the collection
26
Example
Let A = {red, green, blue}
B = {red, orange, yellow}
C = {red, blue, yellow}
A  B  C = {red, green, blue, orange, yellow}
A  B  C = {red}
27
Generalized Unions &
Intersections
• The notation for A1  A2  …  An is:
n
i=1 Ai
• The notation for A1  A2  …  An is:
n
i=1  Ai
28
Computer Representation of Sets
• Two conditions necessary for set
representation using bit strings
– U must be finite
– we impose an arbitrary ordering on U
• We use 1 to mean the element is a member
of the set, and 0 to mean it is not
29
Example
Suppose
U = {a, b, c, … , z} and
S = {a, b, c, x, y, z}
We can represent S as: 1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1
The complement of S is the bit string with the bits reversed:
0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0
To find the union of 2 sets, check for 1 bits in the same position
in either of the 2 strings; to find the intersection, a 1 bit in the
same position of both strings represents an intersection
30
Section 1.7
Set Operations
- ends -
31