COMBINATIONS OF SETS,
MULTISETS AND VENN DIAGRAM
Prof. Vishal Jaiswal
Department of Information Technology
Pune Institute of Computer Technology, Pune
1
Belongs to
• Let
• S1 = {a, b}
• S2 = {{a, b}}
• S3 = {{{a, b}}}
• Some Facts
• a S1
• a S2
• a S3
• S1 S2
• S1 S3
• S2 S3
SUBSETS
Given two sets P and Q, we say that P is a SUBSET of Q if every
element in P is also an element of Q.
Examples:
1. Let A={1, 2, 4, 5} and B = { {1, 2, 3, 4, 5, 7 } } then is, A B.
2. Let A={a, b, c} and B = {a, b, c, d} then is A B
1. For any set P, P is a subset of P
2. The empty set is a subset of any set. However it is not always
an element of any set.
3. The set {Փ}, is not the subset of the set {{Փ}}, although it is an
element of the set {{Փ}}.
UNION OF SETS
The Union of two sets P and Q , denoted by P Q, is the set
whose elements are exactly in either P or Q or both.
Examples:
1. Let A={1, 2, 4, 5} and B = {2, 3, 5, 7} then A B = {1, 2, 3, 4, 5, 7}
2. Let A={a, b, c} and B = { } then A B = {a, b, c}
3. Let A={a, b} and B = {a, b} then A B = {a, b}
INTERSECTION OF SETS
The Intersection of two sets P and Q , denoted by P ∩ Q, is
the set whose elements are exactly those elements that are
in both P and Q.
Examples:
1. Let A={1, 2, 4, 5} and B = {2, 3, 5, 7} then A ∩ B = {2, 5 }
2. Let A={a, b, c} and B = { } then A ∩ B = { }
3. Let A={a, b} and B = {a, b} then A ∩ B = {a, b}
4. Let A={a, b} and B = {c, d} then A ∩ B = { }
Disjoint Sets
Two sets are said to be disjoint if they do not have
any common element.
For example, sets A= {1, 3, 5} and B = {2, 4, 6} are
disjoint sets.
In other words, the sets A and B are said to be
Disjoint if the intersection between these sets
results into a null set. i.e A ∩ B = { }
DIFFERENCE OF SETS
The Difference of two sets P and Q , denoted by P - Q, is the
set containing exactly those elements in P that are not in Q.
Examples:
1. Let A={1, 2, 4, 5} and B = {2, 3, 5, 7} then A - B = {1, 4}
2. Let A={a, b, c} and B = { } then A - B = {a, b, c}
3. Let A={a, b} and B = {a, b} then A - B = { }
4. Let A={a, b} and B = {c, d, e} then A - B = {a, b}
5. Let A={a, b, c} and B = {a} then A - B = {b, c}
If Q P, then the set P – Q is also called as the Complement
of Q with respect to P.
SYMMETRIC DIFFERENCE OF SETS
The Symmetric Difference of two sets P and Q , denoted by P
Q, is the set containing exactly those elements that are
either in P or Q but not in both.
P Q = (P Q) – (P ∩ Q)
Examples:
1. Let A={1, 2, 4, 5} and B = {2, 3, 5, 7} then A B = {1, 3, 4, 7}
2. Let A={a, b, c} and B = { } then A B = {a, b, c}
3. Let A={a, b} and B = {a, b} then A B={}
4. Let A={a, b} and B = {c, d, e} then A B = {a, b, c, d, e}
5. Let A={a, b, c} and B = {a} then A B = {b, c}
UNIVERSAL SET
Consider the following sets.
A = {x : x is a student of your school}
B = {y : y is a male student of your school}
C = {z : z is a female student of your school}
D = {a : a is a student of class XII in your school}
Clearly the sets B, C, D are all subsets of A. A can be considered as the
universal set for this example.
Universal set is generally denoted by U.
In a problem a set U is said to be a universal set if all the sets in that
problem are subsets of U.
Things to Remember:
i. Universal set does not mean a set containing all objects of the
universe.
ii. A set which is a universal set for one problem may not be a universal
set for another problem.
COMPLEMENT OF A SET
Let X denote the universal set and Y, Z its subset where
X = {x : x is any member of the family}
Y = {x : x is a male member of the family}
Z = {x : x is a female member of the family}
X − Y is a set having female members of the family..
X − Z is a set having male members of the family..
X − Y is said to be the complement of Y and is usually denoted by Y' or Yc .
X − Z is said to be complement of Z and denoted by Z' or Zc
If U is the universal set and A is its subset then the complement of A is a set
of those elements which are in U which are not in A. It is denoted by A' or
Ac .
A' = U − A = {x : x U and x A}
The complement of a set can be represented using Venn diagram as :
POWER SET
The Power set of set A, denoted by P(A), is the set that
contains exactly all the subsets of A
Let A = {a, b}
Subset of A are φ , {a}, {b} and {a, b}.
Then, P(A) = { φ ,{a},{b},{ a, b} }
Let B = {{}, {{}}}
Subsets of B are {}, {{}}, {{{}}}, and {{}, {{}}}
Then, P(B) = {{}, {{}}, {{{}}}, {{}, {{}}}} or
P(B) = {φ, {φ}, {{φ}}, {φ, {φ}}}
Set Properties
• Property 1 (Identities)
• A Ø =A A U =A
• A U = U AØ =Ø
• Property 2 ( The Idempotent properties)
• A
• Property 3 (The Commutative properties)
A
• Property 4 (The Associative properties)
A C) = (A C
A C) = (A B) C
• Property 5 (The Distributive properties)
A C) = (A B) C)
A C) = (A B) (A C)
• Property 6 (Properties of the complement)
ØC = U UC = Ø
A C = U A AC = Ø
• Property 7 (De Morgan's laws)
(A B)C = AC BC
(A B)C = AC BC
• Property 8 (Absorption laws)
A (A B) = A
A (A B) = A
• Property 9 (The Involution property)
(AC)C = A
MULTISETS
Multiset is an unordered collection of elements where the
elements can occur as the member more the once
P = { a, a, a, c, d, d } Q = { a, a, b, c ,c }
The following notations can be used to represent multisets:
S = {n1.a1, n2.a2, ….. , ni.ai, ….. }
Let the set A = { a, a, a, b, c, c, d, d}
which can also be expressed as A= {3.a, 1.b, 2.c, 2.d}
The number ni for i = 1, 2, 3, …. are called the multiplicities
of the element ai.
The multiplicity of an element in the multiset is defined as
the number of times the element appears in the multiset.
Operations on Multiset
Let A = {1, 1, 1, 2, 2, 3} and B = {1, 1, 3, 3, 4} be Multisets.
The Union of the Multisets A and B is the multiset where the
multiplicity of an element is maximum of its multiplicities in A
and B.
A U B = {1, 1, 1, 2, 2, 3, 3, 4}
The Intersection of the Multisets A and B is the multiset where
the multiplicity of an element is minimum of its multiplicities
in A and B.
A ∩ B = {1, 1, 3}
Operations on Multiset
Let A = {1, 1, 1, 2, 2, 3} and B = {1, 1, 3, 3, 4} be Multisets.
The Difference of the Multisets A and B is the multiset where
the multiplicity of an element in A less its multiplicity in B
unless the difference is negative, in which case the
multiplicity is zero.
A - B = {1, 2, 2} and B – A = {3, 4}
The Sum of the Multisets A and B is the multiset where the
multiplicity of an element is sum of multiplicities in set A and
set B denoted by A+B.
A + B = {1, 1, 1, 1, 1, 2, 2, 3, 3, 3, 4}
VENN DIAGRAM
British mathematician John Venn (1834 − 1883 AD)
introduced the concept of diagrams to represent sets.
According to him universal set is represented by the
interior of a rectangle and other sets are represented by
interior of circles.
For example if U= {1, 2, 3, 4, 5}, A = {2, 4} and B = {1,3},
then these sets can be represented as
Venn Diagrams for Combination of Sets
XUY XC
X-Y X∩Y X Y
Exercise
1. A (B’ C) = (A B’) C)
2. (A - B) - C = A - (B C)
3. (A - B) (A C) = A - (B - C)
4. A (B C) = (A B) C
5. A B C = A – [(A - B) (A - C)]
6. A B CA B) (A C
THANK YOU
