Discrete Mathematics and
Graph Theory_Unit-II
Dr. Amit Kumar Singh
Assistant Professor
Department of Applied Science
Applications of Set
▪ Mathematics: Sets are fundamental in mathematics
and are used in various mathematical operations and
theories. They are used to define and study functions,
relations, and mappings.
▪ Set theory forms the foundation of other branches of
mathematics, such as combinatory, probability
theory, and discrete mathematics.
▪ Database Management: Sets are used in database
management to handle collections of unique items
efficiently.
▪ Computer Science: Sets are widely used in data
structures like hash sets, trees, and graphs. It also play
a crucial role in various algorithms, such as
searching, sorting, and graph traversal.
▪ Programming: Sets are used in programming
languages to handle unique collections of items.
Many programming languages provide built-in set
data structures or support set operations to manipulate
data effectively.
▪ Cryptography: Sets are used in cryptographic
algorithms for various purposes, such as creating
unique keys and handling data securely. Set
operations like union and intersection are employed
in some encryption techniques.
▪ Statistics: Sets are used in statistics to represent
sample spaces, events, and probability distributions.
Probability theory uses sets to model events and
outcomes in experiments, and set operations are used
to calculate probabilities.
▪ Artificial Intelligence: Sets are used in AI and
machine learning algorithms for tasks like data
classification, clustering, and feature selection. Set
theory concepts are applied in data preprocessing and
analysis.
Unit-II
Set Theory
➢ Sets
➢ Combination of Sets
➢ Venn Diagram
➢ Finite and Infinite Sets
➢ Cardinality
➢ Principle of Inclusion and Exclusion
What is a set?
The theory of sets was developed by German mathematician
Georg Cantor in 1874.
Definition:
❖ A set is a well defined collection of objects.
These objects in a set are called the elements or members of the
set. A set will be denoted by an upper case letters A, B, C,…, X,
Y, Z. Elements will be denoted by lower case letters a, b, c, …,
x, y, z.
For example: S={x, y, z} is a set. Here x is an element of the set S or x
belongs to S, it is represented as x S. Similarly a S means that a is not an
element of S.
Other examples are
◼ People in a class: { Abhishek, Kunal, Chetna }
◼ Courses offered by a department: {EM-I, EM-II, DMPT, … }
◼ Colors of a rainbow: {violet, indigo, red, orange, yellow, green,
blue }
◼ States of matter { solid, liquid, gas, plasma }
◼ Sets can contain non-related elements: { 3, a, red, DMPT}
Although a set can contain (almost) anything, we will most often use
sets of numbers
◼ All positive numbers less than or equal to 5: {1, 2, 3, 4, 5}
◼ A few selected real numbers: { 2.1, π, 0, -6.32, e }
Order does not matter
◼ We often write them in order because it is easier for humans to
understand it that way
◼ {1, 2, 3, 4, 5} is equivalent to {3, 5, 2, 4, 1}
Often used sets
N = {1, 2, 3, …} is the set of natural numbers
W = {0, 1, 2, 3, …} is the set of whole numbers
Z = {…, -2, -1, 0, 1, 2, …} is the set of integers
Z+ = {1, 2, 3, …} is the set of positive integers
Q = {p/q | p Z, q Z, q ≠ 0} is the set of rational numbers
◼ Any number that can be expressed as a fraction of two integers (where
the bottom one is not zero)
◼ Q* is the set of nonzero rational numbers
R is the set of real numbers
R+ is the set of positive real numbers
R* is the set of nonzero real numbers
C is the set of complex numbers
Set properties
Sets do not have duplicate elements
◼ Consider the set of vowels in the alphabet.
It makes no sense to list them as {a, a, a, e, i, o, o, o, o, o, u}
What we really want is just {a, e, i, o, u}
Note that a list is like a set, but order does matter and
duplicate elements are allowed
◼ We won’t be studying lists much in this class
Sets can contain other sets
◼ S = { {1}, {2}, {3} }
◼ T = { {1}, {{2}}, {{{3}}} }
◼ V = { {{1}, {{2}}}, {{{3}}}, { {1}, {{2}}, {{{3}}} } }
Note that 1 ≠ {1} ≠ {{1}} ≠ {{{1}}}
◼ They are all different
Representation of a Set
Mainly there are two ways of representing a set.
1. Roster or Tabular Form: In this form all the
elements or members of the set are listed and being
separated by commas and are enclosed in braces {}.
For example:
(i) The set of odd positive integers less than 12 can be
written as:
S={1,3,5,7,9,11}.
(ii) The set of all vowels in English alphabet can be
written as :
S={a, e, i, o, u}.
To be cont….
2. Set Builder Form: We define the elements of the
set by specifying a property that they have in
common.
For example:
(i) The set S consisting of elements a, e, i, o, u can be
written as:
S={x | x is a vowel in the English alphabets}.
(ii) The set S={1, 4, 9, 16, 25} can be written as :
S={ x | x=n² , where n is a natural number < 5}.
Types of Sets
❑ Empty Set or Null Set: A set with no element is
called an empty set or null set or void set and is
denoted by = { }.
For example:
(i) {x | x is a real number satisfying x² =-5}= .
(ii) {x | x is an integer satisfying 3x+5 =6}= .
Singleton Set: A set consisting of a single elements
is called a singleton set.
For example:
(i) S={3}
(ii) {x | 1<x<3 and x N}={2}
To be cont….
Finite sets: A set witch contains a finite number of
elements is called a finite set.
◼ Examples:
❑ A = {1, 2, 3, 4}
❑ B = {x | x is an integer, 1 < x < 4}
❑ The set of students in a class.
❑ Infinite sets: A set witch contains an infinite number
of elements is called an infinite set
❑ Examples:
❑ Z = {x | x is an integer} = {…, -3, -2, -1, 0, 1, 2, 3,…}
❑ S={x | x is a real number and 1 < x < 4} = {1, 1.1. 1.2,….,4}
To be cont….
Universal set: The set which contains all the objects
or elements under consideration is called universal set
and denoted as U.
◼ For the set {-2, 0.4, 2}, U would be the real
numbers
◼ For the set {0, 1, 2}, U could be the whole
numbers (zero and up), the integers, the rational
numbers, or the real numbers, depending on the
context
◼ For the set of the vowels of the alphabet, U would
be all the letters of the alphabet.
Equality or Equal Set
Two sets are equal if they have the same elements
◼ {1, 2, 3, 4, 5} = {5, 4, 3, 2, 1}
Remember that order does not matter!
Two sets are not equal if they do not have the same
elements
◼ {1, 2, 3, 4, 5} ≠ {1, 2, 3, 4}
Subset
Let S and T are two sets and all the elements of a set S are also
elements of a set T then S is a subset of T.
◼ For example, if S = {2, 4, 6} and T = {1, 2, 3, 4, 5, 6, 7}, then S is a
subset of T
◼ This is specified by ST
Or by {2, 4, 6} {1, 2, 3, 4, 5, 6, 7}
If S is not a subset of T, it is written as such:
ST
For example, {1, 2, 8} {1, 2, 3, 4, 5, 6, 7}
Remark:
(i) Every set is a subset of itself.
(ii) The empty set is a subset of all sets
To be cont….
◼ If a set contain n-elements then the number of subset is
2n.
For example:
S = {a, b, c} so that S has 23 =8 subsets, which are
, {a}, {b}, {c}, {a, b}, {b, c}, {a, c}, {a, b, c}.
Proper Subset
Let S and T be two sets. The set S is called the proper subset
of T if and only if every element of S is the element of T and
there is at least one element of T which is not an element of
the set S i.e., : S T but S≠T.
For example:
◼ Let T = {0, 1, 2, 3, 4, 5} and S = {1, 2, 3}, S is not equal to
T, and S is a subset of T
◼ Let R = {0, 1, 2, 3, 4, 5}. R is equal to T, and thus is a
subset (but not a proper subset) or T
Can be written as: R T .
Let Q = {4, 5, 6}. Q is neither a subset or T nor a proper subset of
T.
Power set
If S is a set, then power set of S is the set of all subsets
of the set S. It is denoted by P(S).
For example:
Let S = {0, 1, 2}. The P(S) = { , {0}, {1}, {2},
{0,1}, {0,2}, {1,2}, {0,1,2} }
Note that |S| = 3 and |P(S)| = 8
P() = { }
Note that || = 0 and |P()| = 1
If a set has n elements, then the power set will have 2n
elements n
If |A|=n, then |P(A)|=2 .
Venn diagram
❖ Set can be represented graphically by means of Venn
diagrams in which the universal set is represented by the
interior of a rectangle and other sets are represented by
the interior of circles that lie inside the rectangle.
Represents sets graphically b c d f
◼ The box represents the universal set
U
g h j
◼ Circles represent the set(s)
S
k l m
Consider set S, which is the set of all
n p q a e i
vowels in the alphabet
r s t
o u
v w x
y z
Operations on Sets:
Union of Two Sets: Let A and B be two sets then the union of
two sets A and B is denoted by AUB is the set of elements
which are in A or in B or in both, i.e.
A U B = { x | x A or x B }
Example: Let A={1, 2, 3, 4, 5, 6} and B={5, 7, 4, 3, 9} then
AUB ={1, 2, 3, 4, 5, 6, 7, 9}.
To be Cont….
Intersection of Two Sets: The intersection of two sets A and B,
denoted by A B, is the set of elements that belongs to both
A and B. i.e. A B = { x | x A and x B}
Example: Let A={1, 2, 3, 4, 5, 6}
and B={5, 7, 4, 3, 9} then
A B ={3, 4, 5}.
Disjoint Set: If A and B do not have any
element in common, then the sets A and B are said to be disjoint.
i.e. A B =
Example: Let A={1, 2, 3, 4} and B={5, 7, 9} then
AB=
To be Cont….
examples
◼ {1, 2, 3} U {3, 4, 5} = {1, 2, 3, 4, 5}
◼ {New York, Washington} U {3, 4} = {New York,
Washington, 3, 4}
◼ {1, 2} U = {1, 2}
◼ {1, 2, 3} ∩ {3, 4, 5} = {3}
◼ {1, 2, 3} and {3, 4, 5} are not disjoint
◼ {New York, Washington} ∩ {3, 4} =
No elements in common, these sets are disjoint
◼ {1, 2} ∩ =
Any set intersection with the empty set yields the empty
set
To be Cont….
Complement: If U is the universal set and A is any set, then the
set of elements which belong to U but which do not belong to
c
A is called the complement of A and is denoted by Aʹ or A or A
i.e. Aʹ = { x | x U and x A }
U
A
Relative complement or difference of Two Sets: If A and B are
any two sets, then the set of elements that belongs to A but do not
belong to B is called the difference of A and B or relative
complement of B with respect to A and is denoted by A-B or A\B.
To be Cont…..
i.e. A — B = { x | x A and x B }
Example: Let A = {a, b, c, d} and
B = {a, c, f, g}
A — B = {b, d} B — A = {f, g}
A-B B-A
Set Operations: Symmetric Difference
Definition:
The symmetric Difference of sets A and B, denoted AB or A B,
consists of those elements which belong to A or B but not to both.
i.e.
A Δ B = { x | (x A or x B) and x A ∩ B}
A Δ B = (A U B) – (A ∩ B) Important!
Note that the pink region is the required
symmetric difference
If A = {1,2,3} and B = {2,5,6,7}
Then A B = { 1,3,5,6,7}
Set operations: Complement and
symmetric difference
examples
◼ {1, 2, 3} - {3, 4, 5} = {1, 2}
◼ {New York, Washington} - {3, 4} = {New York, Washington}
◼ {1, 2} - = {1, 2}
The difference of any set S with the empty set will be the set
(assuming U = Z)
◼ Complement of {1, 2, 3} = { …, -2, -1, 0, 4, 5, 6, … }
◼ {1, 2, 3} Δ {3, 4, 5} = {1, 2, 4, 5}
◼ {New York, Washington} Δ {3, 4} = {New York,
Washington, 3, 4}
◼ {1, 2} Δ = {1, 2}
The symmetric difference of any set S with the empty
set will be the set S
Proper subsets: Venn diagram
What is the meaning of S R and S≠ R ?
S is a proper subset of R
SR
U
R
S
Example
If X={1, 4, 7, 10}, Y={1, 2, 3, 4, 5}
◼ X Y = {1, 2, 3, 4, 5, 7, 10}
◼ X Y = {1, 4}
◼ X – Y = {7, 10}
◼ Y – X = {2, 3, 5}
◼ X Δ Y = (X Y) – (X Y) = {2, 3, 5, 7, 10}
Properties of Set operations
Properties of the union operation
◼ AU=A Identity law
◼ AUU=U Domination law
◼ AUA=A Idempotent law
◼ AUB=BUA Commutative law
◼ A U (B U C) = (A U B) U C Associative law
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) ∩ C Associative law
Properties cont…
Properties of complement sets
¯
¯ A
◼ A= Complementation law
◼ A
¯ UA=U Complement law
◼ A∩A ¯ = Complement law
Properties of set operations
Theorem : Let U be a universal set, and A, B and C
subsets of U. The following properties hold:
a) Associativity: (A B) C = A (B C)
(A B) C = A (B C)
b) Commutativity: A B = B A
AB=BA
c) Distributive laws:
A(BC) = (AB)(AC)
A(BC) = (AB)(AC)
d) Identity laws:
AU=A A = A
Properties cont…
e) Complement laws:
AAc = U AAc =
f) Idempotent laws:
AA = A AA = A
g) Bound laws:
AU = U A =
h) Absorption laws:
A(AB) = A A(AB) = A
Properties cont…
i) Involution law: (Ac)c = A
j) De Morgan’s laws for sets:
(AB)c = AcBc
(AB)c = AcBc
Computer representation of sets
When a universal set U is finite Say U = x1 , x2 , x3 , xn
then all subset U can be represented with the bit string of length n.
A bit string is a string over the alphabet {0,1}. If A is a subset of
U then A is represented by bit string of length n.
1, if xi A
it's bit in this string is = .
0, if xi A
Example.1: If U={1, 2, 3, 4, 5, 6}, A={1, 2, 3, 4} and
B={3, 4, 5, 6} then find the bit string for the set A & B.
Use bit string to find A', union and intersection of A &
B.
To be cont…
Solution:
U={1, 2, 3, 4, 5, 6}
Length of the bit string is 6
A={1, 2, 3, 4}, B={3, 4, 5, 6}
The representation of A and B are 111100, 001111
A B= 111100 001111=111111={1, 2, 3, 4, 5, 6}
A B= 111100 001111=001100={3, 4}
A' =000011= {5, 6}.
To be cont…
Example .2 : Let U be the alphabet i.e. set of letters and set A and
B represents the set of vowels in the alphabet and consonants in
the alphabet respectively. Use bit string to find the union and
intersection of sets A and B.
Solution: Bit string for the universal set
U={11111111111111111111111111}
A=The vowels in the alphabet:
abcdefghijklmnopqrstuvwxyz
10001000100000100000100000
B=The consonants in the alphabet:
abcdefghijklmnopqrstuvwxyz
01110111011111011111011111
Computer representation of set
A B= 10001000100000100000100000
01110111011111011111011111
A B= 11111111111111111111111111
AB = 10001000100000100000100000
01110111011111011111011111
AB = 00000000000000000000000000
Cardinality
Definition: If S be a set, then the number of elements
present in the set S is known as cardinality of S. It is
denoted by |S|.
Examples:
a) If A = {1, 2, 3} then |A| = 3
b) If B = {x | x is a natural number and 1< x< 9}
then |B| = 9
Example of Infinite cardinality
◼ Set of natural numbers, N={1, 2, 3, ………}.
◼ Set of integer numbers, Z ={…, -2, -1, 0, 1, 2, …}.
Principle of Inclusion and Exclusion
(1) If A and B are finite set then
| A B |= | A |+ | B |- | A B |
or n(A B )= n(A )+ n( B )- n(A B )
(2) If A and B are disjoint finite set then
| A B |= | A |+ | B |
or n(A B )= n(A )+ n( B)
(3) | A -B |= | A |- | A B |
(4) | B -A |= | B |- | A B |
(5) If A, B and C are finite set then
|A B C |= |A|+ |B|+ |C|-|A B|-|B C|- | A C |+ |A B C|.
Examples
Example.1: A computer company receives 350 applications from
computer graduates for a job planning a line of new Web
servers. Suppose that 220 of these people majored in
computer science, 147 majored in business, and 51majored
both in computer science and in business. How many of these
applicants majored neither in computer science nor in
business?
Solution: Let A be the set of students who majored in computer
science and B the set of students who majored in business.
Then we have , | A |=220, | B |=147, |A B |= 51
By the principle of inclusion and exclusion:
The number of students who majored either in computer science
or in business, | A B |= | A |+ | B |- | A B |
To be Cont…..
| A B |= 220+147-51=316
The number of applicants who majored neither in computer
science nor in business=350-316=34.
Example. 2: If A and B be two sets containing 3 and 6 elements
respectively, what can be the minimum number of elements
in A B ? Find also, the maximum number of elements in
AB.
Solution: Given | A |=3 , | B |=6
By the principle of inclusion and exclusion:
| A B |= | A |+ | B |- | A B | (1)
Case (i): When | A B | is minimum i.e., | A B | =0.
Hence Eq (1) becomes: | A B |= 3+6-0=9
⸫ maximum number of elements in A B is 9.
To be Cont…..
Case (ii): When | A B | is maximum i.e., | A B | =3.
Hence Eq (1) becomes: | A B |= 3+6-3=6
⸫ minimum number of elements in A B is 6.
Example.3: If A and B are two sets and U is universal set such
that |U|= 700, | A |=200 , | B |=300 and |A B| =100. Find
|A' B'| .
Solution: |A' B'| = |(A B )'|= |U|- |A B|
= |U|- {| A |+| B |- |A B|}
= 700- {200+300- 100} =300.
To be Cont…..
Example.4: If a survey of 110 students it was found that 50 used
the college library, 40 had their own library and 30 borrowed
books, of these 20 used both the college library and their
own, 15 used their own and borrowed books and 10 used the
college library and borrowed books. How many students used
all the three sources of books?
To be Cont…..
Solution: Let A: Students using the college library
B: Students using the their own library
C: Students using the borrow books
Given, | A |=50, |B |= 40, |C |= 30, | A B | =20, |B C| =15,
| A C | =10, |A B C |= 110.
By the principle of inclusion and exclusion:
|A BC|= |A|+ |B|+ |C|-|A B|-|B C|- |A C |+ |AB C|
110=50+40+30-20-15-10 + |AB C|
|AB C|=35.
Therefore the 35 students used all the three sources of books.
To be Cont…..
Example. 5: Among 100 students, 32 study Mathematics, 20
study Physics, 45 study Chemistry, 15 study Mathematics and
Chemistry, 7 study Mathematics and Physics, 10 study
Physics and Chemistry and 30 do not study any of the three
subjects.
(i) Find the no. of student studying all the three subjects.
(ii) Find the no. student studying exactly one of the three
subjects.
Solution: Let X denotes the set of all students in the class. Let M,
P, and C denotes the set of students studying Mathematics,
Physics and Chemistry respectively, then we have,
|X|=100, |M|=32, |P|=20, |C|=45, |MC| =15, |M P| =7,
|P C| =10, |(M P C)' |= 30.
To be Cont…..
| |M P C|=|X|-|(M P C)'|=100-30=70
(i) By the principle of inclusion and exclusion:
|MPC|= |M|+ |P|+ |C|-|M P|-|P C|- |M C |+ |MP C|
70=32+20+45-7-10-15 + | MP C |
| MP C |=5.
(ii) Let M₁, P₁, and C₁ be the set of students who studying only
Mathematics, Physics and Chemistry respectively.
Therefore M₁=M-P-C, P₁=P-M-C, C₁ =C-M-P
The number of students who study only Mathematics:
| M₁|= |M-P-C|= |M|- |M P|- |M C|+ |MP C|
=32-7-15+5=15
To be Cont…..
The number of students who study only Physics :
| P₁ |= | P-M-C |= |P|- |P M|- |P C|+ |MP C|
=20-7-10+5=8
The number of students who study only Chemistry :
| C₁|= |C-M-P|= |C|- |C M|- |C P|+ |MP C|
=45-15-10+5=25
Hence the number of students who study exactly one out of three:
= | M₁ |+ | P₁ |+ | C₁ |=15+8+25=48.
To be Cont…..
Example. 6: In the CSI conference held at SIT Pune, 500
delegates attended. 200 of them could take tea, 350 could
take coffee and 10 did not take either coffee or tea. Then
answer the following questions.
(i) How many can take both tea and coffee.
(ii) How many can take tea only and
(iii) How many can tale coffee only.
Solution: Let T: Set of persons who take tea.
C: Set of persons who take coffee.
U: Total number of delegates.
Hence , n(U)=500, n(T)=200, n(C)=350
Number of delegates did not take either coffee or tea=10
To be Cont…..
Therefore number of delegates who take either coffee or tea
= 500-10=490, i.e. n(T C)=490.
By the principle of inclusion and exclusion:
n(T C) = n(T) + n(C) - n(T C)
490=200+350- n(T C)
n(T C)=200+350-490=60
So, the number of persons who take both coffee and tea
i.e. n(T C)=60
The number of persons take tea only, n(T -C)= n(T) - n(T C)
n(T -C)= 200 – 60= 140
The number of persons take coffee only, n(C-T)= n(C) - n(T C)
n(C-T)= 350 – 60= 290.
To be Cont…..
Example. 7: If 65% of students like apples where 75% like
grapes then what percentage of students likes both apples and
grapes?
Solution: Total number of students = 100
n(A): Total number of students who like apples = 65
n(B): Total number of students who like grapes = 75
By the principle of inclusion and exclusion:
n(A B) = n(A) + n(B) - n(A B)
100=65+75- n(A B)
n(A B)=40.
So, 40% of students like both apples and grapes.
To be Cont…..
Example. 8: In a group of 191 students, 10 are taking English,
Commuter Science and Music; 36 are taking English and
Computer Science; 20 are taking English and Music; 18 are
taking Computer Science and Music; 65 are taking English;
76 are taking Computer Science and 63 are taking Music.
Then Find the followings
(i) How many are taking English and Music but not Computer
Science.
(ii) How many are taking Computer Science and Music but not
English.
(iii) How many are taking Computer Science and neither
English nor Music.
(iv) How many are taking none of three subjects.
To be Cont…..
Solution: Let S: Set of students
E: Set of students taking English
C: Set of students taking Computer Science
M: Set of students taking Music
Given that , n(S)=191; n(E)=65; n(C)=76; n(M)=63;
n(EC M)=10; n(EC )=36; n(EM )=20; n(CM )=18
(i) Number of students taking English and Music but not
Computer Science = n(EM )- n(EC M)=20-10=10
(ii) Number of students taking Computer Science and Music but
not English= n(CM )- n(EC M)=18-10=8
(iii) Number of students taking Computer Science and neither
English nor Music= n(C )- n(EC)- n(C M)+n(EC M)
To be Cont…..
=76-36-18+10
=32
(iv) Number of students taking none of the three subjects
= n(E C M ) ͨ
=n(S) - n(E C M )
= n(S) –[ n(E) + n(C)+ n(M) - n(E C)
-n( C M)- -n( E M)+ n(EC M )]
=191-[65+63+76-20-36-18+10]
=51.
Practice Problems
Q.1: In a group of 64 students 26 can speak Hindi only, 14 can
speak English only. How many can speak both Hindi and
English.
Ans: 24.
Q.2: In a survey about liking for colours, it was found that
everyone who was surveyed had a liking for at least one of
the three colours namely Red, Green and Blue. Further 30%
liked Red; 40% liked Green and 50% liked Blue. Further 10%
people liked both Red and Green, 5% liked both Green and
Blue and 10% liked both Red and Blue. Find the percentage
of the surveyed people who like all the colours.
Ans: 5%.
Recommended Books
Chung Laung Liu, Elements of Discrete Mathematics,
McGraw Hill Education India, 2008.
S. C. Gupta and V. K. Kapoor, Fundamentals of
Mathematical Statistics, Sultan Chand & Sons, 2020.
Kenneth H. Rosen, Discrete Mathematics and Its
Applications, McGraw-Hill Education, 2012.
Any Questions ???