Set Operations

This Presentation is a Courtesy of bilalAmjad

1. Discrete
Structures
(Discrete Mathematics)
Topic: Set Operations
©bilalAmjad
[email protected]

2. Set operations: Union
Formal definition for the union of two sets:
A U B = { x | x Î A or x Î B } or
A U B = { x Î U| x Î A or x Î B }
Further examples
{1, 2, 3} È {3, 4, 5} = {1, 2, 3, 4, 5}
{a, b} È {3, 4} = {a, b, 3, 4}
{1, 2} È Æ = {1, 2}
Properties of the union operation
A È Æ = A Identity law
A È U = U Domination law
A È A = A Idempotent law
A È B = B È A Commutative law
A È (B È C) = (A È B) È CAssociative law

3. 05/26/12

4. Set operations: Intersection
Formal definition for the intersection of two sets:
A B = {
∩
x | x Î A and x Î B }
Examples
{1, 2, 3} ∩ {3, 4, 5} = {3}
{a, b} ∩ {3, 4} = Æ
{1, 2} ∩ Æ = Æ
Properties of the intersection operation
A ∩ U = A Identity law
A ∩ Æ = Æ Domination law
A ∩ A = A Idempotent law
A ∩ B = B ∩ A Commutative law
A ∩ (B ∩ C) = (A ∩ B) ∩ CAssociative law

5. Exercise-intersection
05/26/12

6. Exercise-union
05/26/12

7. Disjoint sets
Formal definition for disjoint sets:
two sets are disjoint if their intersection is the
empty set
Further examples
{1, 2, 3} and {3, 4, 5} are not disjoint
{a, b} and {3, 4} are disjoint
{1, 2} and Æ are disjoint
•Their intersection is the empty set
Æ and Æ are disjoint!
•Because their intersection is the empty set

8. Set operations: Difference
Formal definition for the difference of two sets:
A - B = { x | x Î A and x Ï B }
Further examples
{1, 2, 3} - {3, 4, 5} = {1, 2}
{a, b} - {3, 4} = {a, b}
{1, 2} - Æ = {1, 2}
•The difference of any set S with the empty set will be the
set S

9. Complement sets
Formal definition for the complement of a set:
A = { x | x Ï A } = A
c
Or U – A, where U is the universal set
Further examples (assuming U = Z)
{1, 2, 3}
c
= { …, -2, -1, 0, 4, 5, 6, … }
{a, b}
c
= Z
Properties of complement sets
(A
c
)
c
= A Complementation law
A È A
c
= U Complement law
A ∩ A
c
= Æ Complement law

10. Set identities
AÈÆ = A
AÇU = A
Identity Law
AÈU = U
AÇÆ = Æ
Domination law
AÈA = A
AÇA = A
Idempotent
Law
(A
c
)
c
= A
Complementation
Law
AÈB = BÈA
AÇB = BÇA
Commutative
Law
(AÈB)
c
= A
c
ÇB
c
(AÇB)
c
= A
c
ÈB
c
De Morgan’s Law
AÈ(BÈC)
= (AÈB)ÈC
AÇ(BÇC)
= (AÇB)ÇC
Associative
Law
AÇ(BÈC) =
(AÇB)È(AÇC)
AÈ(BÇC) =
(AÈB)Ç(AÈC)
Distributive Law
AÈ(AÇB) =
A
AÇ(AÈB) =
A
Absorption
Law
A È A
c
= U
A Ç A
c
= Æ
Complement Law

11. How to prove a set identity
For example: A∩B=B-(B-A)
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

12. What we are going to prove…
A B=B-(B-A)
∩
A B
A∩B
B-A
B-(B-A)

13. Proof by Set Identities
A Ç B = A - (A - B) = B – (B – A)
Proof: A - (A - B) = A - (A Ç B
c
)
= A Ç (A Ç B
c
)
c
= A Ç (A
c
È B)
= (A Ç A
c
) È (A Ç B)
= Æ È (A Ç B)
= A Ç B

14. Showing each is a subset of the others
(A Ç B)
c
= A
c
È B
c
Proof: Want to prove that
(A Ç B)
c
Í A
c
È B
c
and A
c
È B
c
Í (A Ç B)
c

(i) x Î (A Ç B)
c
Þ x Ï (A Ç B)
Þ Ø (x Î A Ç B)
Þ Ø (x Î A Ù x Î B)
Þ Ø (x Î A) Ú Ø (x Î B)
Þ x Ï A Ú x Ï B
Þ x Î A
c
Ú x Î B
c
Þ x Î A
c
È B
c
(ii) Similarly we show that A
c
È B
c
Í (A Ç B)
c

15. Exercise