Discrete Mathematics

 Discrete Mathematics is a branch of mathematics

involving discrete elements that uses algebra and
arithmetic. It is increasingly being applied in the
practical fields of mathematics and computer science.
 The word :Discrete

Adjective: Individually separate and distinct.

Synonyms: separate - detached - distinct - abstract.
Prerequisite
Before learning Discrete Mathematics, you must have
the basic knowledge of Elementary Algebra and
Mathematics.
Topics in Discrete Mathematics
 Sets, Relations and Functions
 Mathematical Logic

 Group theory

 Counting Theory

 Probability

 Mathematical Induction and Recurrence Relations

 Graph Theory

 Trees

 Boolean Algebra

We will discuss each of the above concepts in the

subsequent lectures.
Sets Theory
German mathematician G. Cantor introduced the concept of sets. He
had defined a set as a collection of definite and distinguishable
objects selected by the means of certain rules or description.
Set theory forms the basis of several other fields of study like
counting theory, relations, graph theory . In this lecture we will
cover the different aspects of Set Theory.

 Sets Introduction
 Types of Sets
 Sets Operations
 Algebra of Sets
 Multisets
 Inclusion-Exclusion Principle
 Mathematical Induction
Introduction of Sets

 A set is defined as a collection of distinct objects of the same

type or class of objects. The purposes of a set are called
elements or members of the set. An object can be numbers,
alphabets, names, etc.
Examples of sets are:
 A set of rivers of India.
 A set of vowels.
 A set of all positive integers
 A set of all the planets in the solar system
 A set of all the states in India
 A set of all the lowercase letters of the alphabet

 We broadly denote a set by the capital letter A, B, C, etc. while

the fundamentals of the set by small letter a, b, x, y, etc.
 If A is a set, and a is one of the elements of A,
then we denote it as a ∈ A. Here the symbol ∈
means -"Element of.“
and if we write a ∉ A ,it means a does not belong
to set A.
Sets Representation:
Sets are represented in two forms:-
a) Roster or tabular form: In this form of representation we list
all the elements of the set within braces { } and separate them
by commas.
Example: If A= set of all odd numbers less then 10 then in the
roster from it can be expressed as A={ 1,3,5,7,9}.
Example: − Set of vowels in English alphabet, A={a,e,i,o,u}.

b) Set Builder form: In this form of representation, the set is

defined by specifying a property that elements of the set have
in common.
The set is described as A={x:p(x)}
Example: If B= {2, 4, 8, 16, 32}, then the set builder
representation will be: B={x: x=2n, where n ∈ N and 1≤ n <6}.
 Example : The set {a,e,i,o,u} is written as −
A={x:x is a vowel in English alphabet}

 Example:  The set {1,3,5,7,9}  is written as −

B={x:1≤x<10 and (x%2)≠0}

Some Important Sets

 N − the set of all natural numbers = {1,2,3,4,.....}
 Z − the set of all integers = {.....,−3,−2,−1,0,1,2,3,.....}
 Z+ − the set of all positive integers
 Q − the set of all rational numbers
 R − the set of all real numbers
 W − the set of all whole numbers
Cardinality of a Sets
 The total number of unique elements in the set say A is called
the cardinality of the set ,denoted by|A|.
The cardinality of the countably infinite set is countably infinite.
 The cardinality of sets is denoted by|A|, # A, card (A) or n (A).

Examples:
1. Let P = {k, l, m, n}
The cardinality of the set P is 4.

2. Let A is the set of all non-negative even integers, i.e.

A = {0, 2, 4, 6, 8, 10......}.
As A is countably infinite set hence the cardinality.
Types of Sets
Sets can be classified into many categories.
Some of which are finite, infinite, subset,
universal, proper, power, singleton set, etc.
1. Finite Sets: A set is said to be finite if it
contains exactly n distinct element where n is a
non-negative integer. Here, n is said to be
"cardinality of sets." Example:
 Cardinality of empty set θ is 0 and is denoted

by |θ| = 0
 Sets of even positive integer is not a finite set.
2. Infinite Set
A set which contains infinite number of elements is called an infinite
set.
Example − S={x| x ∈ N and x>10}
3. Subset
 A set X is a subset of set Y (Written as X⊆Y) if every element of X

is an element of set Y.
 Example 1 − Let, X={1,2,3,4,5,6} and Y={1,2}. Here set Y is a

subset of set X as all the elements of set Y is in set X. Hence, we can

write Y⊆X
 Example 2 − Let, X={1,2,3} and Y={1,2,3}. Here set Y is a subset

(Not a proper subset) of set X as all the elements of set Y is in set X.

Hence, we can write Y⊆X.
4. Proper Subset
 The term “proper subset” can be defined as “subset of but not equal to”.
A Set X is a proper subset of set Y (Written as X⊂Y) if every element of
X is an element of set Y and |X|<|Y|.
 Example − Let, X={1,2,3,4,5,6} and Y={1,2}. Here set Y⊂X since all
elements in Y are contained in X too and X has at least one element is
more than set Y.
5. Universal Set
 It is a collection of all elements in a particular context or
application. All the sets in that context or application are
essentially subsets of this universal set. Universal sets are
represented as U.
 Example − We may define U as the set of all animals on
earth. In this case, set of all mammals is a subset of U, set of
all fishes is a subset of U, set of all insects is a subset of U,
and so on.
6. Empty Set or Null Set
 An empty set contains no elements. It is denoted

by ∅. As the number of elements in an empty set

is finite, empty set is a finite set. The cardinality
of empty set or null set is zero.
 Example − S={x|x∈N and 7<x<8}=∅

7. Singleton Set or Unit Set

 Singleton set or unit set contains only one

element. A singleton set is denoted by {s}.

 Example − S={x|x∈N, 7<x<9} = {8}
8. Equal Set
 If two sets contain the same elements they are said to

be equal.
 Example − If A={1,2,6} and B={6,1,2}, they are equal

as every element of set A is an element of set B and

every element of set B is an element of set A.
9. Equivalent Set
 If the cardinalities of two sets are same, they are

called equivalent sets.

 Example − If A={1,2,6}and B={16,17,22}, they are

equivalent as cardinality of A is equal to the

cardinality of B. i.e. |A|=|B|=3
10. Disjoint Set
 Two sets A and B are called disjoint sets if

they do not have even one element in

common. Therefore, disjoint sets have the
following properties −
 n(A∩B)=∅
 n(A∪B)=n(A)+n(B)
 Example − Let, A={1,2,6} and B={7,9,14},
there is not a single common element, hence
these sets are disjoint sets.
Venn Diagrams

 Venn diagram, invented in 1880 by John

Venn, is a schematic diagram that shows all
possible logical relations between different
mathematical sets.
 Examples
Set Operations

Set Union
The union of sets A and B (denoted byA∪B) is the set of
elements which are in A, in B, or in both A and B.
Hence, A∪B={x|x∈A OR x∈B}.
Example
If A={10,11,12,13} and B = {13,14,15},
then A∪B={10,11,12,13,14,15}. (The common element
occurs only once)
Set Intersection
 The intersection of sets A and B (denoted by A∩B)
is the set of elements which are in both A and B.
Hence, A∩B={x|x∈A AND x∈B}.
 Example − If A={e,f,g} and B={f,g,h} then A∩B={f}.
Set Difference/ Relative Complement
 The set difference of sets A and B (denoted by A–B) is
the set of elements which are only in A but not in B.
Hence, A−B={x|x∈A AND x∉B}.
 Example − If A={10,11,12,13} and B={13,14,15},
then (A−B)={10,11,12} and (B−A)={14,15}. Here, we can
see (A−B)≠(B−A).
Symmetric Difference of Sets: 
The symmetric difference of two sets A and B is the set containing
all the elements that are in A or B but not in both and is denoted
by A ⨁ B i.e.
A ⨁ B = (A ∪ B) - (A ∩ B)  

Example: Let A = {a, b, c, d}
B = {a, b, l, m}
A ⨁ B = {c, d, l, m}
Complement of a Set
 The complement of a set A (denoted by A′) is the

set of elements which are not in set A. Hence, A

′={x|x∉A}.
 More specifically, A′=(U−A) where U is a universal

set which contains all objects.

 Example −Let U is the set of all natural numbers.

A = {1, 2, 3}
Ac = {all natural numbers except 1, 2, and 3}.
Cartesian Product / Cross Product

 The Cartesian Product of two sets P and Q in that order is

the set of all ordered pairs whose first member belongs
to the set P and second member belong to set Q and is
denoted by P x Q, i.e.,
P x Q = {(x, y): x ∈ P, y ∈ Q}.  
If n(A) =n1 &n(B)= n2,then n(A×B)=n1*n2

Example − If we take two sets A={a,b} and B={1,2},

 The Cartesian product of A and B is written as

− A×B={(a,1),(a,2),(b,1),(b,2)}
 The Cartesian product of B and A is written as

− B×A={(1,a),(1,b),(2,a),(2,b)}
Example: Let P = {a, b, c} and Q = {k, l, m, n}.
The Cartesian product of P and Q is
Power Set

Power set of a set S is the set of all subsets of S including the empty set.
The cardinality of a power set of a set S of cardinality n is 2n. Power set
is denoted as P(S).
 Example −

 For a set S={a,b,c,d} let us calculate the subsets −

 Subsets with 0 elements − {∅} (the empty set)

 Subsets with 1 element − {a},{b},{c},{d}.

 Subsets with 2 elements − {a,b},{a,c},{a,d},{b,c},{b,d},{c,d}

 Subsets with 3 elements − {a,b,c},{a,b,d},{a,c,d},{b,c,d}{a,b,c},{a,b,d},

{a,c,d},{b,c,d}
 Subsets with 4 elements − {a,b,c,d}{a,b,c,d}

 Hence, P(S)={{∅},{a},{b},{c},{d},{a,b},{a,c},{a,d},{b,c},{b,d},{c,d},{a,b,c},

{a,b,d},{a,c,d},{b,c,d},{a,b,c,d}}
 |P(S)|=24=16
 Note − The power set of an empty set is also an empty set.
 |P({∅})|=20=1
Partitioning of a Set
 Partition of a set, say S, is a collection of n disjoint
subsets, say P1,P2,…Pn that satisfies the following
three conditions −
 Pi does not contain the empty set.
[Pi≠{∅} for all 0<i≤n]
 The union of the subsets must equal the entire
original set.
[P1∪P2∪⋯∪Pn=S]
 The intersection of any two distinct sets is empty.
[Pa∩Pb={∅}, for a≠b where n≥a,b≥0]
 Example
 Let S={a,b,c,d,e,f,g,h}
 One probable partitioning is {a},{b,c,d},{e,f,g,h}{a},{b,c,d},
{e,f,g,h}
 Another probable partitioning is {a,b},{c,d},{e,f,g,h}

Ques: Let A ={a,b,c,d,e,f,g,h}. Consider the following

subsets of A.
A1={a,b,c,d} A2={a,c,e,g,h}
A3={a,c,e,g} A4={b,d} A5={f,h}
Determine which of the following is partition of A ?
1. {A1,A2} 2. {A1,A5} 3. {A3,A4,A5}
Bell Numbers

 Bell numbers give the count of the number of ways to partition a

set. They are denoted by Bn where n is the cardinality of the set.
 Example −
 Let S={1,2,3}, n=|S|=3
 The alternate partitions are −
 1. ∅,{1,2,3}
 2. {1},{2,3}
 3. {1,2},{3}
 4. {1,3},{2}
 5. {1},{2},{3}
 Hence B3=5
Multisets

 A multiset is an unordered collection of elements,

in which the multiplicity of an element may be one
or more than one or zero. The multiplicity of an
element is the number of times the element
repeated in the multiset. In other words, we can say
that an element can appear any number of times in
a set.
 Example:
 A = {l, l, m, m, n, n, n, n}  
 B = {a, a, a, a, a, c}  
Operations on Multisets

1. Union of Multisets: The Union of two multisets A and B is a

multiset such that the multiplicity of an element is equal to the
maximum of the multiplicity of an element in A and B and is
denoted by A ∪ B.
 Example:

Let A = {l, l, m, m, n, n, n, n}  
     B = {l, m, m, m, n},   
A ∪ B = {l, l, m, m, m, n, n, n, n}  
2. Intersections of Multisets: The intersection of two multisets A
and B, is a multiset such that the multiplicity of an element is
equal to the minimum of the multiplicity of an element in A and B
and is denoted by A ∩ B.
 Let A = {l, l, m, n, p, q, q, r}  
    B = {l, m, m, p, q, r, r, r, r}  
A ∩ B = {l, m, p, q, r}.  
3. Difference of Multisets: The difference of two multisets A and B,
is a multiset such that the multiplicity of an element is equal to the
multiplicity of the element in A minus the multiplicity of the element
in B if the difference is +ve, and is equal to 0 if the difference is 0 or
negative
Example:
Let A = {l, m, m, m, n, n, n, p, p, p}  
    B = {l, m, m, m, n, r, r, r}  
A - B = {n, n, p, p, p}  
4. Sum of Multisets: The sum of two multisets A and B, is a multiset
such that the multiplicity of an element is equal to the sum of the
multiplicity of an element in A and B
Example:
Let A = {l, m, n, p, r}  
    B = {l, l, m, n, n, n, p, r, r}  
A + B = {l, l, l, m, m, n, n, n, n, p, p, r, r, r}  
5. Cardinality of Sets: The cardinality of a multiset is the
number of distinct elements in a multiset without
considering the multiplicity of an element
Example:
A = {l, l, m, m, n, n, n, p, p, p, p, q, q, q}  
The cardinality of the multiset A is 5.

Ordered Set
It is defined as the ordered collection of distinct objects.
Example:
Roll no {3, 6, 7, 8, 9}  
Week Days {S, M, T, W, TH, F, S}  
 Algebra of Sets

Idempotent Laws (a) A ∪ A = A (b) A ∩ A = A

Associative Laws (a) (A ∪ B) ∪ C = A ∪ (B ∪ (b) (A ∩ B) ∩ C = A ∩

C) (B ∩ C)

Commutative (a) A ∪ B = B ∪ A (b) A ∩ B = B ∩ A

Laws
Distributive Laws (a) A ∪ (B ∩ C) = (A ∪ B) ∩ (b) A ∩ (B ∪ C) =(A ∩
(A ∪ C) B) ∪ (A ∩ C)

De Morgan's (a) (A ∪B)c=Ac∩ Bc (b) (A ∩B)c=Ac∪ Bc

Laws
Identity Laws (a) A ∪ ∅ = A (c) A ∩ U =A
(b) A ∪ U = U (d) A ∩ ∅ = ∅

Complement (a) A ∪ Ac= U (c) Uc= ∅

Laws (b) A ∩ Ac= ∅ (d) ∅c = U

Involution Law (a) (Ac)c = A

 Ques : A computer company must hire 20 programmers to handle
system programming jobs &30 programmers for application
programming .Of those hired,5 are expected to perform jobs of both
types. How many programmers must be hired?
 ANS.
let,
A be a set of programmers for system programing job i.e n (A)=20
B be as set of programmers for application programming i.e n(B)=30
A∩B is set of programmers doing jobs of both types i.e n(A∩B )=5
now, we know the formula,
AUB= A+B-(A∩B)
applying
AUB= 20+30-5
      =45
hence, the computer company should hire 45 people for the job.
 Ques : In a Class of 25 students ,12 have taken mathematics ,8
have taken mathematics but not biology .Find the number of
students who have taken mathematics & Biology and those who
have taken Biology but not mathematics .
Ans.
 Ques : Prove that A –(B∩C)= (A-B) ∪(A-C)
Ques: Out of 250 students who failed in an examination, it was
revealed that 128 failed in mathematics,87 failed in physics and 134
failed in chemistry.31 failed in maths and physics,54 failed in
chemistry and mathematics,30 failed in chemistry and physics. find
how many candidates failed in:
[a] in all the three subjects.
[b] in mathematics but not in physics.
[c]in chemistry but not in mathematics.
[d] in physics but not in chemistry or in mathematics.
[e]in chemistry or in mathematics but not in physics.
References
 https://www.tutorialspoint.com/discrete_mat
hematics/discrete_mathematics_sets.htm
 http://home.iitk.ac.in/~arlal/book/mth202.p
df
 https://nptel.ac.in/courses/111/107/111107
058/