Discrete Mathematical Structures

• Discrete Mathematics is a branch of mathematics that is

concerned with “discrete” mathematical structures instead of

“continuous”.

• Discrete mathematical structures include objects with distinct

values like graphs, integers, logic-based statements, set

theory, recurrence relation, group theory, and graph theory.

 Recommended Books
1. Bernard Kolman,Busby,” Discrete Mathematical Structures”,PHI.

2. Kenneth H. Rosen. ”Discrete Mathematics and its Applications”, Tata

McGraw-Hill.

3. Seymour Lipschutz, Marc Lipson “Schaum's Outline of Discrete

Mathematics”, Revised Third Edition Tata McGraw-Hill.

4. D. S. Malik and M. K. Sen, “Discrete Mathematical Structures”, Thompson.

5. C. L. Liu, D. P. Mohapatra, “Elements of Discrete Mathematics” Tata

McGrawHill.

6. J. P. Trembley, R. Manohar “Discrete Mathematical Structures with

Applications to Computer Science”, TataMcgraw-Hill.

7. Y N Singh, “Discrete Mathematical Structures”, Wiley-India.

 SET THEORY

• 1.1 Sets, Venn diagrams, Operations on Sets

• 1.2 Laws of set theory, Power set and

Products

• 1.3 Partitions of sets, The Principle of

Inclusion and Exclusion
 SET THEORY
• SETS • SET PROPERTIES
• NOTATION • VENN DIAGRAMS
• SPECIAL SETS • SET OPERATIONS
• DEFINITION • LAWS OF SET THEORY
– SUBSET • PARTITION OF SETS
– EQUAL SETS • POWER SET
– PROPER SUBSET
– UNIVERSAL SET
– NULL/EMPTY SET
– SINGLETON SET
– SUPER SET
– FINITE /INFINITE SET
– DISJOINT SET
– CARDINALITY OF FINITE SET
 SETS
• A set is an unordered collection of objects.
– the students in this class
– the chairs in this room

• The objects in a set are called the elements, or members of

the set.
– A set is said to contain its elements.

• The notation a ∈ A denotes that a is an element of the set A.

• If a is not a member of A, write a ∉ A
 Describing a Set: Roster Method
• S = {a,b,c,d}

• Order not important

S = {a,b,c,d} = {b,c,a,d}
• Each distinct object is either a member or not; listing more than once does
not change the set.

S = {a,b,c,d} = {a,b,c,b,c,d}
• Elipses (…) may be used to describe a set without listing all of the
members when the pattern is clear.

S = {a,b,c,d, ……,z }
 Roster Method
 Set of all vowels in the English alphabet:
V = {a,e,i,o,u}
 Set of all odd positive integers less than 10:
O = {1,3,5,7,9}
 Set of all positive integers less than 100:
S = {1,2,3,……..,99}
 Set of all integers less than 0:
S = {…., -3,-2,-1}
 Some Important Sets
N = natural numbers = {0,1,2,3….}
Z = integers = {…,-3,-2,-1,0,1,2,3,…}
Z⁺ = positive integers = {1,2,3,…..}
R = set of real numbers
R+ = set of positive real numbers
C = set of complex numbers.
Q = set of rational numbers
 SET-BUILDER Notation
• Specify the property or properties that all
members must satisfy:
S = {x | x is a positive integer less than 100}
O = {x | x is an odd positive integer less than 10}
• A predicate may be used: S = {x | P(x)}

• Example: S = {x | Prime(x)}
 Universal Set and Empty Set
• The universal set U is the set containing everything currently
under consideration.
– Sometimes implicit/explicit/Contents depend on the context.

• Empty set is the set with no elements. Symbolized ∅, but { }

also used , but {∅}???

“A null set is a subset of every set “

 Some things to remember
• Sets can be elements of sets.
{{1,2,3},a, {b,c}}
{N,Z,Q,R}
• The empty set is different from a set
containing the empty set.
∅ ≠{∅}
 Set Equality

Definition: Two sets are equal if and only if they have

the same elements.
– Therefore if A and B are sets, then A and B are equal if and
only if A ⊆ B and B ⊆ A then A=B
– We write A = B if A and B are equal sets.

{1,3,5} = {3, 5, 1}
{1,5,5,5,3,3,1} = {1,3,5}
 Subsets
Definition: The set A is a subset of B, if and only if
every element of A is also an element of B.
– The notation A ⊆ B is used to indicate that A is a
subset of the set B.
Eg: If A={1,2,3}, B={1,2,3,4,5}, C=(3,2,1}

– ⊆ - not a subset
“Every set is a subset of itself”
 Proper Subsets
Definition: If A ⊆ B, but A ≠B, then we say A is a
proper subset of B, denoted by A ⊂ B.
A= {x ,y } , B= {x, y ,z}
then is A ⊂ B ?
A= {1,3}
B={1,2,3}
C={1,3,2}
A⊂C ? , B⊂C?
 Set Cardinality
Definition: The cardinality of a finite set A, denoted
by |A|, is the number of (distinct) elements of A.
Examples:
1. |ø| = 0
2. Let S be the letters of the English alphabet. Then
|S| = 26
3. |{1,2,3}| = 3
4. |{ø}| = 1
5. The set of integers is infinite.
 SUPERSET
• If A is the subset of B then B is the SUPERSET
of A

DISJOINT SET
• Two sets are said to be disjoint if they have no
elements in common
 SET PROPERTIES
• Every Set A is a subset of the Universal set U
Ø⊆ A⊆ U
• Every set A is a subset of itself
A⊆ A
• Transitivity
A ⊆ B, B ⊆ C, then A ⊆ C
• If A ⊆ B and B ⊆ A then A=B; converse also
holds true
Venn Diagrams & Set Operations
 Union
• Definition: Let A and B be sets. The union of the sets A and B,
denoted by A ∪ B, is the set:

• Example: What is {1,2,3} ∪ {3, 4, 5}?

Solution: {1,2,3,4,5}
Venn Diagram for A ∪ B

U
A B
 Intersection
The intersection of sets A and B,
• Definition:
denoted by A ∩ B, is

– Note if the intersection is empty, then A and B are said to be disjoint.

• Example: What is? {1,2,3} ∩ {3,4,5} ?
Solution: {3}
• Example:What is?
{1,2,3} ∩ {4,5,6} ? Venn Diagram for A ∩B
Solution: ∅ or { } U
A B
 Complement
Definition: If A is a set, then the complement of the A (with

respect to U), denoted by Ā is the set U-A

Ā = {x ∈ U | x ∉ A}

(The complement of A is sometimes denoted by Ac .)

Example: If U is the positive integers less than 100, what is the complement of {x | x > 70}

Solution: {x | x ≤ 70}
Venn Diagram for Complement
U
Ā
A
 Difference
• Definition: Let A and B be sets. The difference of A and B,

denoted by A – B, is the set containing the elements of A

that are not in B.

A – B = {x | x ∈ A  x ∉ B}
A={a , b , c } B = {b , c , d ,e } A – B = ?

U Venn Diagram for A − B

A
B
 Symmetric Difference
Definition: The symmetric difference of A and B,
denoted by is the set

Example: U
U = {0,1,2,3,4,5,6,7,8,9,10} A B
A = {1,2,3,4,5} B ={4,5,6,7,8}
What is :
– Solution: {1,2,3,6,7,8}
Venn Diagram
 Cartesian Product
Definition: The Cartesian Product of two sets A and B,
denoted by A × B is the set of ordered pairs (a,b) where
a ∈ A and b ∈ B (first element from A and second element
from B)

Example:

A = {a,b} B = {1,2,3}

A × B = {(a,1),(a,2),(a,3), (b,1),(b,2),(b,3)}
 Review Questions
Example: U = {0,1,2,3,4,5,6,7,8,9,10} A = {1,2,3,4,5}, B ={4,5,6,7,8}
1. A ∪ B
Solution: {1,2,3,4,5,6,7,8}
2. A ∩ B
Solution: {4,5}
3. Ā
Solution: {0,6,7,8,9,10}
4.
Solution: {0,1,2,3,9,10}
5. A – B
Solution: {1,2,3}
6. B – A
Solution: {6,7,8}
 PROBLEMS/ EXERCISE TO SOLVE
Consider U= {1,2,3,4,5,6,7,8,9}
A= {1,2,4,6,8}
B={2,4,5,9}
C={x|x is a positive integer and x2<=16)
D= {7,8}
Compute following:
1. AUB
2. AUC
3. AUD
4. BUC
5. A∩D
6. B ∩C
7. C ∩D
8. A-B
9. B-A
10. C-D
11. C`
12. A⊕B
13. C⊕D
14. A ∩( C` U D )
15. (A U B ) ∩ D
 LAWS OF SET THEORY
• Commutative laws

• Associative laws

• Distributive laws
 LAWS OF SET THEORY
• Identity laws

• Properties of Empty set

• Idempotent laws

• Complement law
 LAWS OF SET THEORY
• De Morgan’s laws

• Absorption laws

• Properties of complement law

 LAWS OF SET THEORY
Double Complement A = A
Properties of Universal Set A U U= U
A ∩ U=A
Properties of Empty Set A U {} = A
A ∩{} = {}

* PROOF IS LEFT AS AN EXERCISE TO STUDENT

 Membership Table
Example: Construct a membership table to show that the distributive law
holds.
Solution:
A B C
1 1 1 1 1 1 1 1
1 1 0 0 1 1 1 1
1 0 1 0 1 1 1 1
1 0 0 0 1 1 1 1
0 1 1 1 1 1 1 1
0 1 0 0 0 1 0 0
0 0 1 0 0 0 1 0
0 0 0 0 0 0 0 0
Ex. : Show that (using laws of logic)
(a) A ∪ (AC ∩ B) = A ∪ B.
(b) A ∩ (AC∪ B) = A ∩ B.
 THEOREMS
*PRINCIPLE OF INCLUSION EXCLUSION*
|A U B|= |A| +| B| – |A ∩ B|
MUTUAL INCLUSION EXCLUSION PRINCIPLE
|A U B U C | = | A | + | B | + | C | - | A ∩B |
- | B ∩ C | - | A ∩C | + | A ∩B ∩C |
 PROBLEMS/ EXERCISE TO SOLVE

A company must hire 25 programmers to handle

programming jobs & 40 programmers for application
programming job of which 10 will be expected to do
both kinds of roles. How many programmers must be
hired?
A sample of 80 people have revealed that 24 like cinema and 62 like television
programmes. Find the number of people who like both cinema and television
programmes.
Ans: Let A = Set of people who like cinema
B = Set of people who like television programs
Then, we have
| A | = 24, | B |=62.
Using principle of Inclusion and Exclusion

| A ∪ B|= | A | + | B | – | A ∩ B |

We obtain

80 =24 + 62 – | A ∩ B |

Therefore,
|A∩B| = 6

Thus 6 people like both cinema and television programmes.

 PROBLEMS/ EXERCISE TO SOLVE
In a survey of 260 college students , the following data were
obtained:
64 had taken a maths course
94 had taken a CS course
58 had taken a Business course
28 had taken both M and B course
26 had taken both M and CS course
22 had taken both CS and B course
14 had taken all three types of courses.
(i) How many students surveyed who had taken none of the
three types of courses?
(ii)Of the students surveyed how many had taken only CS
course?
VENN DIAGRAM?
 In a survey of 260 college students, the following data were obtained.
64 had taken a Mathematics course.
94 had taken a computer science course.
58 had taken a business course.
28 had taken both mathematics and business course.
26 had taken both a mathematics and computer science course.
22 had taken both a computer science and Business course.
14 had taken all three types of courses.
(i)How many students were surveyed who had taken none of the three types of courses ?
(ii)Of the students surveyed, how many had taken only a computer science course ?

Ans: Let A be the set of students taken Mathematics course.

B be the set of students taken Computer Science course.
C be the set of students taken Business course.
We have | A |=64, | B | = 94, | C | = 58,

|A∩C| =28, taken mathematics and business course

|A∩B| =26, taken mathematics and computer science course
|B∩C| =22, taken computer science and business course
| A ∩ B ∩C | =14, taken mathematics, computer science and business course

VENN DIAGRAM ?.
(i) Using Principle of Inclusion and Exclusion
| A ∪ B ∪ C |=| A | + | B | + | C | – | A ∩ B | – | B ∩ C | – | A ∩ C |
+|A∩B∩C|
=64 + 94 + 58 – 28 – 26 – 22 + 14
=154
Students who have not taken either of subjects,
=| U | – | A ∪ B ∪ C |
=260 – 154 = 106
Thus 106 students had taken none of the three types of course.

(ii)Students who have taken only computer science course

=| B | – | B ∩ A | – | B ∩ C | + |A ∩ B ∩ C|
= 94 – 26 – 22 + 14 = 60
60 students had taken only computer science course.
Ex. 5 : In a survey of 60 people, it was found that 25 read Newsweek magazine, 26 read
Time and 26 read Fortune. Also 9 read both Newsweek and Fortune, 11 read both
Newsweek and Time, 8 read both Time and Fortune, 8 read no magazine at all.
(a)Find the number of people who read all three magazines.
(b)Fill in the correct number of people in each of eight regions of Venn diagram.
Here N, T and F denote the set of people who read Newsweek, Time and Fortune
respectively.
(c)Determine the number of people who read exactly one magazine.
Ans: | N |=25, | T | = 26, | F | 26,
And | N ∩ T |=11, |N ∩ F|= 9, |T ∩ F| = 8.
8 read no magazine at all.
| N ∪ T ∪ F |=60 – 8 = 52

By the principle of inclusion and exclusion we have,

| N ∪ T ∪ F |=|N| + |T| + |F| – |N ∩ T| – |T ∩ F| -|N ∩ F| + |N ∩ T ∩ F|

52=25 + 26 + 26 – 11 – 9 – 8 + | N ∩ T ∩ F|
| N ∩ T ∩ F |=3
Hence, 3 people read all three magazines.

VENN DIAGRAM ?
(b)To draw Venn Diagram,
3 read all three magazines
|N ∩ T| – |N ∩ T ∩ F|= 11 – 3 = 8 read Newsweek
and Time but not all three magazines.

|N ∩ F| – |N ∩ T ∩ F|=9 – 3 = 6 read Newsweek

and Fortune but not all three magazines.

|T ∩ F| – |N ∩ T ∩ F| =8 – 3 = 5 read Time and

Fortune but not all three magazines.

|N| – |N ∩ T| – |N ∩ F| + |N ∩ T ∩ F| =
25 – 11 – 9 + 3 = 8 read only Newsweek
|T| – |T ∩ F| – |N ∩ T| + |N ∩ T ∩ F| =
26 – 8 – 11 + 3 = 10 read only Time
|F| – |T ∩ F| – |N ∩ F | + |N ∩ T ∩ F| =
26 – 8 – 9 + 3 = 12 read only Fortune

(c)People who read only one magazine is 8 + 10 + 12 = 30

 PROBLEMS/ EXERCISE TO SOLVE
Suppose that 100 of 120 students at a college take at least
one of the languages French , German and Russian . Also
suppose
65 study French
20 study French and German
45 study German
25 study French and Russian
42 study Russian
15 study German and Russian
(i) How many students study all three languages ?
(ii)Fill in the correct regions in Venn Diagram
(iii)Hence find out the number of students ‘k’ who study
* Exactly 1 language *Exactly 2 languages
Ex. 6
 PROBLEMS/ EXERCISE TO SOLVE

1) How many integers between 1 and 60 are not divisible by

2,not by 3,nor by 5 ?

2) How many integers between 1 and 300 are divisible by 3,5, or

7 and are not divisible by 3 nor 5 nor 7 ?

3) Determine number of integers between 1 & 1000 that are

divisible and not divisible by 2 ,3 & 5 ?
Ex. 6 :Find how many integers between 1 and
60 are not divisible by 2 nor by 3 and nor by 5
?
Ex. 7 : Among the integers 1 and 300, how
many of them are divisible by 3, 5 or 7 and are
not divisible by 3, nor by 5, nor by 7? How
many of them are divisible by ‘3’ but not by ‘5’
nor by ‘7’ ?
 Power Sets
Definition: The set of all subsets of a set A,
denoted P(A), is called the power set of A.
Example: If A = {a,b} then
P(A) = {ø, {a},{b},{a,b}}

• If a set has n elements, then the cardinality of

the power set is 2ⁿ.
 PROBLEMS/ EXERCISE TO SOLVE

1. Let A={1 , 2 ,3 }.Determine the power set of A

1. Let A={a , b , c , d }. Determine the power set of A

 Partition of Sets
• If A is a set, a partition of A is any set of non
empty subset A1,A2,A3….. Of A such that
A1 U A2 U A3……… = A

&
A i∩ A j = Ø for i = j (subsets are mutually disjoint)
Example A = { a , b , c}

Verify whether { { a } , { b , c } } is a partition of A or not

 PROBLEMS/ EXERCISE TO SOLVE
1. S={1,2,3,4,5,6,7,8,9}.Determine whether each is a
partition or not
(i) {{1,3,5},{2,6},{4,8,9,}}
(ii) {{1,3,5},{2,4,6,8},{5,7,9}}
(iii) {{1,3,5},{2,4,6,8},{7,9}}
2. Let A={a,b,c,d,e,f,g,h }.Consider the following
subsets of A
A1={a,b,c,d} A3={a,c,e,g}
A2={a,c,e,g,h} A4={b,d} A5={f,h}
Determine whether following is a partition of A or not. Justify
(i) {A1,A2} (ii) {A1, A5} (iii) {A3,A4,A5}
Ex. : Use Venn diagram to illustrate De Morgan's law for sets, viz.