Set operation:

Union:Let A and B be sets.The union of the sets A and B ,denoted by A∪B,is the set that
contains those elements that are either in A or in B ,or in both

A∪B={x|xЄA v xЄB }

Example: The union of sets {1,3,5}and {1,2,3}is {1,2,3,5}

Intersection: 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

A∩B={x|xЄA ∧ xЄB }

Example: The intersection of sets {1,3,5}and {1,2,3}is {1,3}

Disjoint sets:Two sets are called disjoint if their intersection is empty

Example:Let A={1,3,5,7,9}andB={2,4,6,8,10}since A∩B=∅ so A and B are disjoint.

Principle of Inclusion-Exclusion:
ІA∪BІ=ІAІ+ІBІ-ІA∩ BІ

Difference of two sets:Let A and B be two 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.

A−¿B={x|xЄA ∧ x∉B }

Symmetric Difference of two sets

Symmetric difference of two sets A and B, denoted by A ⨁ B is the set of those elements in
either A or B but not in both

A ⨁ B={x / x ∈ A ⨁ x ∈ B }
Example:If A={1,2,3}, B={1,3,5} then
A⨁B={2,5}

Note: A ⨁ B=(A-B)U(B-A)

Complement of a set: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 U-A

Á = ={x|x∉A}

Example:let A={a,e,i,o,u} (where the universal set is the set of letters of the English
alphabet).Then Á ={b,c,d,f,g,h,j,k,l,m,n,p,q,r,s,t,v,w,x,y,z}

Example:let A be the set positive integers greater than 10.Then Á={1,2,3,4,5,6,7,8,9,10}

Set identities:

Set Identities
identity name
AU∅=A Identity laws
A∩U=A
AUU=U Domination laws
A∩ ∅=∅
AUA=A Idempotent laws
A∩ A= A
 ´ =A
( Á) Double
complementation Law
AUB=BUA Commutative Laws
A∩B=B∩ A
AU(BUC)=(AUB)UC Associative Laws
A∩(B∩C)=(A∩B)∩C
A∩(BUC)=(A∩B)U(A∩C) Distributive Laws
AU(B∩C)=(AUB)∩(AUC)
´ = Á ∩ B́
AUB De Morgan`s Law
A∩´ B= Á U B́

Example Prove that A ∩

´ B= ÁU B́by showing that each set is a subset of other.

´ B.
Solution: First,suppose that x∈ A ∩

⟹x ∉ A ∩ B

⟹x ∉ A or x ∉ B

⟹x ∈ Á or x ∈ B́

⟹x ∈ Á U B́

´ B⊆ Á U B́
This implies that A ∩ …….(a)

Now suppose that y ∈ Á U B́ .

⟹y ∈ Á or y ∈ B́ ,

⟹ y ∉ A∨ y ∉ B

⟹y ∉ A ∩ B

⟹ y∈ A ∩
´ B

´ B . ………(b)
This implies that Á U B́⊆ A ∩

Thus by (a) and (b) ´ B= Á U B́

A∩

Example Use set builder notation and logical equivalences to show that A ∩
´ B= Á U B́ .

Solution: The following chain of equalities provides a demonstration of this Identity.

´ B={x│ x ∉ A ∩B}
A∩

={x│⇁(x∈(A∩B))}
 ={x│⇁(x∈A∧ x∈B)}

={x│x∉AVx∉B}

={ x│x ∈ Á Vx ∈ B́ }

´ B ={ x│x ∈ Á U B́}
A∩

Exapmle:Use a membership table to show that A∩(BUC)=(A∩B)U(A∩C)

A B C BUC A∩(BUC) (A∩B) (A∩C) (A∩B)U(A∩C)

1 1 1 1 1 1 1 1
1 1 0 1 1 1 0 1
1 0 1 1 1 0 1 1
1 0 0 0 0 0 0 0
0 1 1 1 0 0 0 0
0 1 0 1 0 0 0 0
0 0 1 1 0 0 0 0
0 0 0 0 0 0 0 0

Clearly from the column 5 and column 8

A∩(BUC)=(A∩B)U(A∩C)

Example:show that AU (B´ ∩C )=(ĆU B́ ¿∩ Á

Solution: AU (B´ ∩C )= Á ∩ ¿´¿) by the first De Morgan’s law

= Á ∩( B́U Ć ) by the Second De Morgan’s law

= ( B́U Ć )∩ Á by the commutative law for intersections

=(Ć U B́)∩ Á by the commutative law for unions

Computer representation of sets:

Example:let U={1,2,3,….10}
and A={1,3,5,7,9} and B={2,4,6,8,10}

then computer representation of A is the bit string 1010101010 and of B is 0101010101 and if
C={1,2,3,4,5} then computer representation of C is 1111100000

Example: let A={1,3,5,7,9} then what is the bit string for the complement of this set?
Solution: since A={1,3,5,7,9} then Á ={2,4,6,8,10} and its bit string is 0101010101

Exercise1.5:

Q1: let A be the set of students who live within one mile of the school and let B be the set of
students who walk to the classes.Describ the students in each of the following sets

a) (A∩B)
the set of students who live within one mile of the school and walk to the classes
b) (AUB)
the set of students who either live within one mile of the school or walk to the classes or
both.
c) A-B
the set of students who live within one mile of the school but do not walk to the classes
d) B-A
the set of students who walk to the classes but do not live within one mile of the school

Q2:suppose that A is the set of sophomores at your school and B is the set of students in discrete
mathematics at your school .Express each of the following sets in terms of A and B.

a)the set of sophomores taking discrete mathematics in your school

(A∩B)

b) the set of sophomores at your school who are not taking discrete mathematics

A-B

c)the set of students who either are sophomores or taking discrete mathematics

AUB

d)the set of somphomores at your school who either are not sophomores or not taking discrete
mathematics

A⊕B

Q3: Let A={1,2,3,4,5} and B={0,3,6} find

a)AUB b)A∩B

c)A-B d)B-A

try yourself

Q4:let A={a,b,c,d,e} and B={a,b,c, d,e,f,g,h} find

a)AUB b)A∩B

c)A-B d)B-A

try yourself

Q5:Let A be a set.show that Á =A

Proof:let x∈ Á

⇒x∉ Á

⇒ x∈A

⟹ Á ⊆A…(a)

Let y∈A

⇒y∉ Á

⟹y∉ Á

⟹ A ⊆ Á ……(b)

By (a) and (b) we get Á =A

Q8:Find the sets A and B if A-B ={1,5,7,8},B-A={2,10} and A∩B={3,6,9}

Solution: We’ll solve this problem by using Venn diagram
 2,1
0
1,5,7,8
3,6,9

Clearly from the figure A={1,3,5,6,7,8,9}and B={2,3,6,9,10}

´ = Á ∩ B́
Q9:Show that if A and B are sets then AUB

a)by showing that each side is a subset of the other side

b)using a membership table

´
a)let x∈ AUB

⟹ x ∉ AUB.

⟹ x ∉ Aandx ∉B

⟹ x ∈ Á andx ∈ B́ .

⟹ x ∈ Á ∩ B́ .
´ ⊆ Á ∩ B́ ……(a)
⟹ AUB

let y ∈ Á ∩ B́ .
⟹ y ∈ Á andy ∈ B́ .

⟹ y ∉ Aand y ∉B

⟹ y ∉ AUB.

⟹y∈ AUB
´

´ ….(b)
⟹ Á ∩ B́ ⊆ AUB
´ = Á ∩ B́
Combining (a)and (b) we get AUB

b)

A B AUB ´
AUB Á B́ Á ∩ B́
1 1 1 0 0 0 0
1 0 1 0 0 1 0
0 1 1 0 1 0 0
0 0 0 1 1 1 1

Clearly from the column 4th and 7th AUB

´ = Á ∩ B́

´ C = Á U B́ U Ć
Q11;Show that if A,B,C are sets ,then A ∩ B∩

a)by showing that each side is a subset of the other side

b)using a membership table

´ ∩C
a)let x∈ A ∩ B

⟹ x ∉ A ∩ B ∩C.

⟹ x ∉ Aorx ∉Borx ∉ C

⟹ x ∈ Á orx ∈ B́ orx ∈ Ć .

⟹ x ∈ Á U B́ U Ć .

⟹ A ∩B´ ∩C ⊆ Á U B́ U Ć .……(a)

let y ∈ Á U B́ U Ć .

⟹ y ∈ Á ory ∈ B́ ory ∈ Ć .

⟹ y ∉ Aor y ∉Bor y ∉C

⟹ y ∉ A ∩B ∩C.
⟹ y∈ A ∩ B
´ ∩C

⟹ Á U B́ U Ć ⊆ A ∩B´ ∩C ….(b)
´ C = Á U B́ U Ć
Combining (a)and (b) we get A ∩ B∩

b)membership table

A B C A∩ B ∩C ´ C Á
A ∩ B∩ B́ Ć Á U B́ U Ć
1 1 1 1 0 0 0 0 0
1 1 0 0 1 0 0 1 1
1 0 1 0 1 0 1 0 1
1 0 0 0 1 0 1 1 1
0 1 1 0 1 1 0 0 1
0 1 0 0 1 1 0 1 1
0 0 1 0 1 1 1 0 1
0 0 0 0 1 1 1 1 1
Clearly from column 5th and 9th A ∩ B∩
´ C = Á U B́ U Ć

Q13:Show that if A and B are sets then A-B=A∩ B́

Proof:letx ∈A-B

⟹ x ∈A but x∉B

⟹ x ∈Aand x ∈ B́

⟹ x ∈A∩ B́

⟹ A-B⊆ A ∩ B́……(a)

lety ∈A∩ B́

⟹ y ∈Aand y ∈ B́

⟹ y ∈A and y∉B

⟹ y ∈A-B

⟹ A ∩ B́⊆ A−B……(b)

Combining (a)and(b)we get A-B=A∩ B́

Q14.Show that if A and B are sets then (A∩B)U(A∩ B́)=A

A B A∩B B́ A∩ B́ (A∩B)U(A∩ B́)

1 1 1 0 0 1
1 0 0 1 1 1
 0 1 0 0 0 0
0 0 0 1 0 0
rd th
Clearly from the column 3 and 5 (A∩B)U(A∩ B́)=A

Q15.Let A,B,C be sets .show that

a)AU(BUC)=(AUB)UC

b)A∩(B∩C)=(A∩B)∩C

c) AU(B∩C)=(AUB)∩¿AUC)

Solution:try it yourself

Hint:use membership tables

Q16 Let A,B,C be sets .show that(A-B)-C=(A-C)-(B-C)

Solution:

A B C A-B(A-B)- A-C B-C (A-C)-(B-C)

C
1 1 1 0 0 0 0 0
1 1 0 0 0 1 1 0
1 0 1 1 0 0 0 0
1 0 0 1 1 1 0 1
0 1 1 0 0 0 0 0
0 1 0 0 0 0 1 0
0 0 1 0 0 0 0 0
0 0 0 0 0 0 0 0
th th
Clearly from column 5 and 7 (A-B)-C=(A-C)-(B-C)

Q17:let A={0,2,4,6,8,10},B={0,1,2,3,4,5,6}and C={4,5,6,7,8,9,10}.Find

a) A ∩ B∩ C

b)AUBUC

c)( AUB)∩C

d)( A ∩ B)UC

solution:try yourself

Q18.Draw the venn diagram for each of the following combinations of the sets A,B,C