th th

ISO 9001:2015 NBA NAAC Accredited AICTE-CII Survey rating Among Top 250 Colleges 68 & 78 in All India Rank by Outlook
Certified Accredited Institute in Platinum category for in NIRF Ranking survey published in June 2019 &
Industry linkages May 2018 respectively
Institute Programs with 'A' Grade 2019-20 & 2020-21

Mathematics-III
A.Y. 2024-25 (SE SEMESTER III (CS & E/COMP/IT))

A.Y. 2021-22 (SE SEMESTER III- Cyber Security )

Choice Based Credit Grading System with Holistic and Multidisciplinary Education (CBCGS - HME 2023)
Under TCET - Autonomy Scheme (w.e.f A.Y. 2023-24)

Autonomous College Affiliated to University of Mumbai

Approved by All India Council for Technical Education(AICTE) and Government of Maharashtra
Preface

About Resource book

It gives us pleasure to introduce the first edition of this Resource Book Mathematics-
III (BSC-CS301) as per the revised AICTE Model curriculum syllabus under TCET Autonomy
Scheme A.Y. 2021-22. This resource book has been designed according to the Choice
Based Credit Grading Scheme with Holistic and Multidisciplinary Education (CBCGS
– HME 2023 ). This course is aimed to develop the basic mathematical skills of
engineering students that are imperative for effective understanding of engineering
subjects. The topics introduced will serve as basic tools for specialized studies in many
fields of engineering and technology. Students will be benefitted from the comprehensive
information provided and supporting sample solved exercises which are tune to their
needs to learn the subject.
Content and Structure
The resource book has been divided into six modules. Each module is consisting of
content wise weightage, definitions, notations, formulae, solved sample problems,
exercises, objective questions, and homework assignment.

Module 1 consists of Set Theory and Proofing Techniques, where Basic operations
on sets, Cartesian products, disjoint union (sum), power sets and laws of set theory are
discussed. Counting Principle, Basic counting techniques – inclusion and exclusion,
pigeon-hole principle.

Module 2 consists of Relation & Function where definition of relation, types of

relation, and composition of relations, domain and range of a relation, pictorial
representation of relation, properties of relation, Closure and Warshall’s algorithm
,partial ordering relation was studied in detailed with correlating examples. Definition and
types of function, composition of functions, recursively defined functions and recurrence
relation was studied.

Module 3 consists of Partially ordered set, where Partial Orderings & Partially
Ordered Sets, Hasse Diagrams, lattice, complete, distributive, modular and
complemented lattices was discussed with supported problems. Boolean and pseudo-
Boolean lattices were also studied.

Module 4 consists of Graph Theory, where Graph and Graph Models, Graph Terminology,
Special types of Graphs, Representing Graphs and Graph Isomorphism Paths and circuits,
Euler and Hamiltonian Graphs and concept of Trees were studied. Bipartite graph, Trees,
planner graph and graph coloring were also discussed with real life application-based
problems.
Module 5 consists of Logic, where propositions and logical operations, truth tables,
equivalence, implications, laws of logic, normal forms, predicates & quantifiers,
mathematical induction were studied in detailed and examples based on properties
were focused upon. Applications of Logic was discussed to solve real life problems.
Mathematical Induction.

Module 6 consists of Algebraic Structures, where definition of groups, abelian group,

cyclic groups were studied in detailed and examples based on properties were focused
upon. Application of group theory was discussed to solve problems related to coding &
decoding the errors. Concept of field was discussed.
General Guidelines for Learners:

1. Resource book is for structured and guided teaching learning process and
therefore learners are recommended to come with the same in every lecture.
2. Teaching will be done on the basis of resource book and home assignments will
be covered from the same for the benefit of the learners.
3. Resource book is framed to improve the academic result and therefore the
learners are recommended to take up all the module contents, home assignments and
exercise seriously.
4. A separate notebook should be maintained for every subject.
5. Lectures should be attended regularly. In case of absence, topic done in the class
should be referred from the module before attending the next lecture.
6. Motivation, weightage and pre‐requisite in every chapter have been included in
order to maintain continuity and improve the understanding of the content to
clarify topic requirement from exam point of view.
7. For any other additional point related to the topic instructions will be given by
the subject teacher from time to time.

Mathematics-III
SUBJECT RELATED

1. All modules are equally important in weightage of marks.

2. Questions are expected from all modules and learners are instructed not to leave any
module in option.
3. Weightage for Term Work - 25 marks, Theory ‐60 marks and Internal Assessment-
20 marks. Importance should be given to term work for improving overall percentage
in examination.
4. Practice problems should be solved sincerely in order to enhance confidence level
and to excel in university examination.
5. Definitions, key notations and solved examples should be referred thoroughly
from the modules after lecture session.
EXAM SPECIFIC

1. Neat and labelled diagram should be drawn as per the requirement of the question
mentioned in the question paper.
2. Read the question paper thoroughly first then choose the questions. Attempt the
one that you know the best first but do not change the internal sequence of the
sub questions.
3. Minimum passing marks in End Semester Examination (ESE) is 24/60 and
Internal Assessment (IA) comprising of In-Semester Examination (ISE – 20
marks) and Innovative Examination (IE – 20 marks) is 16/40 and in Term Work
10/25.
4. For further subject clarification/ doubt in the subject, learners can contact the subject
teacher.

Guidelines for Writing Quality Answer

1. Write solution of the problem as per marks distribution.

2. All the steps need to be covered while writing the solution of the problems.
2. Highlight the main steps in solving the problems.
3. Write necessary content related to the point.
4. Draw neat and labelled diagrams wherever necessary.
 S.E. Semester –III
Choice Based Credit Grading Scheme with Holistic and Multidisciplinary
Education (CBCGS-HME 2023)
TCET Autonomy Scheme (w.e.f. A.Y. 2024-25)
B.E. Computer Science & Engineering (Cyber security) S.E (SEM: III)
Course Name: Mathematics -III Course Code: BSC –CYS 301
Teaching Scheme (Program Specific) Examination Scheme (Formative/ Summative)
Modes of Teaching / Learning / Weightage Modes of Continuous Assessment / Evaluation

Hours Per Week Theory Practical/ Term Work Total

(100) Oral (25) (25)
Theo Tutori Practic Conta Credi ISE IE ESE TW
ry al al ct ts
Hours 125
3 1 - 4 4 20 20 60 - 25

IA: In-Semester Assessment - Paper Duration – 1.5 Hours

ESE: End Semester Examination - Paper Duration - 3 Hours
Total weightage of marks for continuous evaluation of Term work/Report: Formative (40%),
Timely completion of Tutorial (40%) and Attendance (20%).

Prerequisite: Basic Mathematics, Mathematics-I &II.

Course Objectives:
The course intends to deliver the fundamental knowledge of set theory, function, relation,
pigeonhole principle, recurrence relation, generating function, partially order set, Lattice.
To prepare the students to understand various concepts in graph theory, Logic and
Algebraic Structure.

Course Outcomes:

SN Course Outcomes Cognitive levels

of attainment as
per Bloom’s
Taxonomy
1 Understand the basic concepts of set theory and able to apply basic L1, L2, L3
set operations in problem solving.
2 Understand relation and function and their properties and also L2, L3
able to understand their use in programming applications.
3 Able to apply PO set and Boolean lattice concepts in various L1, L2, L3
applications.
4 Able to apply graph theory in various fields. L1, L2, L3
5 Develop an understanding of how to read and construct valid L1, L2, L3
Mathematical statements, arguments and understand mathematical
statements.
6 Understand use of groups and codes in Encoding-Decoding and apply L1, L3
discrete structures into other computing problems such as formal
specification, verification, artificial intelligence, cryptography, Data
Analysis and Data Mining.
 Detailed Syllabus:

Module Topics Hr Cognitive

No. s. levels as per
blooms
Taxonomy
1 Set Theory and Proofing Techniques
Basic operations on sets, Cartesian products, disjoint 7
union (sum), complements, power sets and Products
Partitions of sets. Counting principle, cardinality and L1, L2, L3
countability (Countable and Uncountable sets). The
Principle of Inclusion and Exclusion, Pigeonhole Principle.

2 Relation and Functions

Relation: Definition, types of relation, composition of 7
relations, pictorial
representation of relation (Digraphs), properties of relation,
partial ordering relation. Operations on relations, Closures, L2, L3
Warshall’s algorithm.
Function: Definition and types of function, composition
and inverse of functions, Generating Functions.
3 Partially ordered sets
Complete partial ordering (Hasse Diagram), chain, lattice, 7
L1, L2, L3
complete, distributive, modular and complemented lattices.
Boolean and pseudo-Boolean lattices.
4 Graph theory
Definitions: graphs, digraphs, Multigraphs, Paths and cycles 8
(Hamiltonian and Eulerian) Subgraphs, Isomorphism, Special L1, L2, L3
kinds of graphs: trees, bipartite graphs, planer
graphs, Graph coloring, Trees.
5 Logic
Propositions and logical operations, Truth tables Equivalence, 7
Implications Laws of logic, Normal Forms, Predicates and L1, L2, L3
Quantifiers, Mathematical Induction
6 Algebraic Structures
Algebraic structures with one binary operation: semigroup, 9
monoid and group, Abelian group, Cyclic groups, L1, L3
Homomorphism, Isomorphism, Field. Coding theory: Coding of
binary information and error detection, decoding and error
correction
Total hours 45
List of Tutorials:

Sr. Topic Hrs. Cognitive levels of

No attainment as per
Bloom’s Taxonomy
1 Tutorial on Set theory 1 L1, L2
2 Tutorial on Principle of Inclusion 1 L1, L2, L3
and Exclusion
3 Tutorial on Pigeonhole Principle 1 L1, L2, L3
4 Tutorial on Relation 1 L1, L2
5 Tutorial on Warshall’s Algorithm 1 L1, L2, L3
6 Tutorial on Functions 1 L1, L2
7 Tutorial on isomorphism 1 L1, L2, L3
8 Tutorial on poset, Hasse diagram 1 L1, L2
9 Tutorial on Lattice, Sublattice 1 L1, L2, L3
10 Tutorial on types of lattices 1 L1, L2, L3

11 Tutorial on planar graphs 1 L1, L2

12 Tutorial on Eulerian and 1 L1, L2, L3
Hamiltonian Graphs
13 Tutorial on Logic 1 L1, L2
14 Tutorial on Groups 1 L1, L2, L3

15 Tutorial on Coding & Decoding 1 L1, L2, L3

Total Hours 15

Books and References:

SN Title Authors Publisher Edition Year

Introductory
1 methods of S.S. Sastry PHI 4th Edition 2005
numerical analysis
Advanced John Wiley &
Erwin 2006
2 Engineering Sons 9th Edition
kreyszig
Mathematics
 Engineering Tata McGraw-
3 Mathematics for Veerarajan T Hill, New 3rd Edition 2008
first year Delhi
Higher
Tata McGraw
Engineering
4 Ramana B.V Hill, New 11th Edition 2010
Mathematics Delhi
Higher
Khanna 36th Edition 2010
5 Engineering B.S. Grewal
Publishers
Mathematics
A text book of Laxmi
6 N.P. Bali and
Engineering Publications 9th Edition 2008
Manish Goyal
Mathematics
Elements of Tata McGraw-
7 Discrete C. L. Liu 2nd Edition 2000
Hill
Mathematics
Discrete
Mathematics:
World
8 Proof Techniques R. C. Penner - 1999
Scientific
and Mathematical
Structures
Discrete
Tata McGraw-
9 Mathematics and K. H. Rosen 6th Edition 2007
Hill
its Applications

Online References:

S. Website Name URL Modules

No. Covered
1. [Link] [Link] M1
.[Link] es/111106086/[Link]
2. [Link] [Link] M2
.[Link] 6183/
3. [Link] [Link] M3
.[Link] rb_sXg
4. [Link] [Link] M4
.[Link] 6183/
5. [Link] [Link] M5
.[Link]
6. [Link] [Link] M6
.[Link]
 Table of Contents

Sr. No. Module Name Pages

1 Set Theory 1-16

2 Relation and Functions 17-40

3 Partially Ordered Set 41-58

4 Graph Theory 59-94

5 Logic 94-109

6 Algebraic Structures 110-120

 Mathematics – III (CS & E)

Module 1: Set Theory

1. Motivation:

Set theory is a branch of mathematical logic that studies sets, which informally are
collections of objects. The language of set theory can be used in the definitions of nearly
all mathematical objects. Sets are important everywhere in mathematics because every
field of mathematics uses or refers them in some way. They are important for building more
complex mathematical structure.

2. Syllabus:
Module Content Duration Self-
Units study
Weightage
duration

1 Definition of Sets, Venn Diagrams, 7 Hrs 10 Hrs 21 Marks

complements, cartesian products, power sets,
counting principle, cardinality and
countability (Countable and Uncountable
sets) Laws of set theory, Power set and
Products Partitions of sets. Principle of
Inclusion and Exclusion Pigeonhole
Principle.

3. Prerequisite: Basics of logic and concept of Number system

4. Learning Objective:
1. Student shall be able to understand the concept of sets.
2. Student shall be able to understand the laws related to set and their real-life
application.
3. Student shall be able to know different types of Set operation.
4. Student shall be able to learn the counting principal of the set theory.
5. Student shall be able to know law of inclusion and exclusion.

Set Theory

Lecture: 01

1. Learning Objective: Students shall be able to understand the concept of sets.

2. Introduction: The concept of sets is the basic concept required to explain the basic
mathematical structure. This concept is the basis of mathematical analysis.
3. Key Notations:
(1)  : belongs to (10) : union
(2)  : intersection (11) : super set
(3)  : subset (12)⊄ : not a subset
1
SE Semester III-CBCGS HME 2021-22

(4) ⊂&⊃ : proper subset (13) : does not belong

(5) { } : set (14) : empty set
(6) U : universal set (15)P (A) : power set
(7) ∀ : for every (16): : such that
(8) Z : set of integers (17)R : set of real numbers
(9) Q : rational numbers (18)Ac : Complement
4. Key Definitions:
I. Sets: A set is any well-defined collection of objects called the elements or members of the
set.
II. Null set: The set that has no elements in it is denoted either by { } or the symbol 
and is called the empty set.
III. Equal sets: Two sets A and B are said to be equal if they have the same elements and is written
as A = B.
IV. Universal Set: A set which contains all the elements of other given sets is called a universal
set and is denoted by U.
V. Finite set: A set A is said to be finite if it has n distinct elements, where n  N. Here n is
called the cardinality of A and it is denoted by |A|. The set that is not finite is called
infinite.
VI. Power Set: If A is a set, then the set of all subsets of A is called power set of A and
it is denoted by P (A). If A has n elements, P(A) has 2 n elements. The power set of
{1, 2, 3} is {{1, 2, 3}, {1, 2}, {1, 3}, {2, 3}, {1}, {2}, {3}, ∅}. The cardinality of the original
set is 3, and the cardinality of the power set is 23 = 8.
VII. Venn Diagrams: Pictorial representations of sets represented by closed figures are called set
diagrams or Venn diagrams.
VIII. Subsets: If any element of A is also an element of B, that is, if whenever x A then x B,
the A is called a subset of B or that A is contained in B and is written as A  B. If A is not a
subset of B, it is written as A  B.
IX. Countable sets: A set is called countable (or countably infinite) if it has the same
cardinality as N. Equivalently, a set A is countable if it can be enumerated in a sequence,
i.e., if all of its elements can be listed as a sequence a1, a2, A set is called uncountable if
it is infinite and not countable.
X. Cartesian Product of two sets: If A and B are two non-empty sets, then their Cartesian
product A × B is the set of all ordered pair of elements from A and B.
A×B={(x, y): x ∈A ,y ∈B }.
XI. Duality: If E is an equation in the set operations, then equation obtained by replacing 
by ,  by , U by  and  by U is called the dual of E and is denoted by E*.

XII. Proper subset: If A and B are two sets, then A is called the proper subset of B if A ⊆ B but
B ⊇ A i.e., A ≠ B. The symbol ‘⊂’ is used to denote proper subset. Symbolically, we write
A ⊂ B.
Note: i. No set is a proper subset of itself.
ii. Empty set is a proper subset of every set.
XIII. Operations on sets:

2
 Mathematics – III (CS & E)

a. Union: If A and B are sets, then the set consisting of all elements that belong to A or
B is said to be union and it is denote by AB. Thus

AB = {x | x  A or x  B}

b. Intersection: If A and B are sets, then the set consisting of all elements that belong to both
A and B is said to be intersection and it is denote by A  B. Thus AB = {x | x  A and x 
B}.

AUB U AB U

c. Disjoint sets: Two sets that have no common elements are called disjoint sets.
d. Complement of B with respect to A: If A and B are sets, then the set of all elements that
belong to A but not in B is said to be complement of B with respect to A and it is denote by
A – B. thus

A - B = {x | x  A and x  B}.

e. Symmetric difference: If A and B are sets, then the set of all elements that belong to
A or to B but not to both A and B is said to be symmetric difference and it is denote by
A  B. Thus AB = {x | (x A and x  B) or (x A and x B) } or AB = (A-B)∪ (B-
A). It is also represented by AB.

5. Sample Problem:
Q.1. Let U = {a, b, c, d, e, f, g, h, k}, A = {a, b, c, g), B = {d, e, f, g}, C = {a, c, f} and
D = {f,h,k} compute the following: (a) 𝐴 ∪ 𝐵 (b) 𝐴 ∩ 𝐶 (c) (𝐴 ∪ 𝐵) − 𝐶
(d) 𝐴 ∩ 𝐷 (e) 𝐴 ∪ 𝐵 (f) 𝐴 ⊕ 𝐵 (g) 𝐴 ∪ 𝐵 ∪ 𝐶 (h) 𝐴 ∩ 𝐵 ∩ 𝐶
(i) (𝐴 ∪ 𝐵) ∩ 𝐶 (j) 𝐴 ∩ 𝐵

Solution: (a) 𝐴 ∪ 𝐵 = {a, b, c, d, e, f, g}

(b) 𝐴 ∩ 𝐶 = {a, c}

(c) (𝐴 ∪ 𝐵) − 𝐶 ={b, d, e, g}

3
SE Semester III-CBCGS HME 2023-24

(d) A = {d, e, f, h, k}, D = {a, b, c, d, e, g}, A  D = {d, e}

(e) 𝐴 ∪ 𝐵={h, k}

(f) 𝐴 ⊕ 𝐵 =(A−B)∪(B−A) here (A−B)= {a, b, c} and (B−A)={d, e, f}, then

𝐴 ⊕ 𝐵 = {a, b, c, d, e, f}

(g) 𝐴 ∪ 𝐵 ∪ 𝐶 = {a, b, c, d, e, f, g}

(h) A  B  C = {}

(i) (𝐴 ∪ 𝐵) ∩ 𝐶 = {a, c, f}
(j) A∩B = {g}, 𝐴 ∩ 𝐵={a, b, c, d, e, f, h, k}
Exercise 1

1. Let U={1,2,3,4,5,6,7,8,9}, A={1,2,3,4}, B={4,5,6,7}, C={1,3,6}, D={6,8,9}. Compute the

following:
(a) A  B (b) B  C (c) A  C (d) A (B C) (e) (A B) C (f) A  B

2. Let the universal set be the set R of all real numbers and let
A  {xR|1 x  5} and B  {xR| 3  x  8}. Find each of the following

(i) A B (ii) A  B (iii) A-B (iv) B-A

3. Prove that if a set has ‘n’ element, then its power set has 2𝑛 element.
4. Prove that if for set A its power set has m elements and there is set B such that
|𝐵| = |𝐴| + 1 then the number of elements in the power set of B is 2m.

Let’s check the takeaway from lecture

Choose the correct option from the following:
1. If A = {1, 3, 5, 7, 9,….}, B = {2, 4, 6, 8, 10…..}, A  B is

(a) {1,2,3,4,5,6,7,8,9,10,….} (b) {} (c) {1,3,5,7,….} (d) none of these

2. A  A is
(a) U (b)  (c) A (d) A

Homework Problems for the day

1. If a finite set A has n elements, prove that the power set of A has 2n elements.
2. Determine the sets A and B, given that
(i) A  B = {1,2,4}, B  A= {7,8} and A  B = {1,2,4,5,7,8,9}.

3. If A = {1,2,3} determine the power set of A.

4. Let U={1,2,3,4,5,6,7,8,9}, A={1,2,3,4}, B={4,5,6,7}, C={1,3,6}, D={6,8,9}. Compute the
following:

4
 Mathematics – III (CS & E)

(a) A  D (b) A  C (c) (d) A  B  C (e) A  B  C (f) A  𝐵

̅

Learning from the topic: Students will be able to understand the concept of sets.

Set theory continued...

Lecture -02
1. Learning Objective: Student shall be able to understand the laws of sets.
2. Introduction: Set theory follows some of the law related with its operations. These laws
are different from addition and subtraction of real numbers.

3. Important Formulae/ Theorems / Properties:

(i) Theorems:
1. Laws of idempotent: a) A∪A=A b)A∩A=A
2. Laws of commutativity: a) A∪B=B∪A b)A∩B=B∩A
3. Laws of associativity: a) (A∪B) ∪ C=A∪(B∪C) b) (A∩B)∩C=A∩(B∩C)
4. Laws of distributivity: a) A∩(B∪C) =(A∩B) ∪ (A∩C)
b) A∪(B∩C) = (A∪B) ∩ (A∪C)

5. Properties of Complement: a) AA b) AAU

c) A  A   (d) e) U   f) A B A B

g) A B A B

6. Properties of a Universal set: a) A  U  U b) A  U  A

7. Properties of empty set: a) A    A b) A   

5
 SE Semester III-CBCGS HME 2023-24

(ii) Formulae: (with proof / counter example)

1. (A∩B)C=(AC)(BC)
2. A−(B∪C) =(A−B) ∩(A−C)
3. A−(B∩C) =(A−B) ∪(A−C)
4. AB=(A−B) ∪(B−A)

4. Key Notations:
1. R= the set of all real numbers.
2. Z: the set of all integers positive or negative including zero.

5. Sample Problem:

Q.1 Prove that A B  A  B

Solution: LHS A  B  ( A  B) (B A)  (A  B) (B A)  (A  B) (B A)

(B A) (A B)  (A B) (B A)  A B  RHS

Q.2 Using set laws, prove that (A B) (A B)  (A  B)  A B

Solution:

( A  B) ( A  B) (A B)  ( A  B)  ( A  B) (A B)  ( A  B)   A (B B)


 ( A  B)  A U   ( A  B)  A  A ( A  B)  ( A  A) ( A  B)
 U  ( A  B)  A  B  RHS

Exercise 2

1. using Venn diagram show that P Q R  P  Q P  R .

2. using Venn diagram show that P − (Q ∩ R) = (P − Q) ∪ (P − R).
3. using Venn diagram show that P Q  R  P Q  P R.
4. the sets A, B, C given that A B = A C and A  B = A C . Is it necessary that B = C?
Justify.
5. prove that A-(A-B)B
6. prove that A-B=A  ̅𝐵

6
 Mathematics – III (CS & E)

Let’s check the takeaway from lecture

Choose the correct option from the following:
1. Dual of A  (A B)(A ) is

(a) A  (A B)(A ) (b) A  (A B)(A )

(c) A  (A B)(A U) (d) A  (A B)(A )

2. If U={1,2,3,4,5,6,7,8,9,10}, A={1,4,7,10}, B={1,2,3,4,5}, C={2,4,6,8}, then A∩(BUC)

(a) {1,2,3,4,5,7,10} (b) {1,4,7,10} (c) {1,2,3,4,5} (d) {1,4}

Homework Problems for the day

1. Using Venn diagram, prove: A(B C)  (A B) C
2. Using Venn diagram, prove: (A B) (AC)  A(B C)
3. Prove that the following distributive law, 𝐴 ∪ (𝐵 ∩ 𝐶) = (𝐴 ∪ 𝐵) ∩ (𝐴 ∪ 𝐶)

Learning from the topic: Students will be able to understand the laws of sets.

Counting Principle

Lecture -03

1. Learning Objective: Student shall be able to understand the principal of inclusion

and exclusion and counting principal.
2. Introduction: In this topic, principal of inclusion and exclusion are introduced which
is also known as addition principal of the set theory. Principal of Inclusion and exclusion
is a counting technique that compute the number of elements that satisfy at least one
of the several properties while guaranteeing that elements satisfying more then one
property and not counted twice.
3. Key Definitions: The inclusion–exclusion principle (also known as the sieve
principle) is an equation relating the sizes of two sets and their union. It states that
if A and B are two (finite) sets, then
|A∪B| = |A| + |B| - |A∩B|
The meaning of the statement is that the number of elements in the union of the two
sets is the sum of the elements in each set, respectively, minus the number of
elements that are in both. Similarly, for three sets A, B and C

|A∪B∪C| = |A| + |B|+|C| - |A∩B|- |B∩C|- |C∩A|+|A∩B∩C|

7
SE Semester III-CBCGS HME 2023-24

This can be seen by counting how many times each region in the figure to the right is

included in the right-hand side. More generally, for finite sets A1, ..., An one has the

identity
|⋃𝑛 𝐴𝑖| = ∑𝑛 (−1)𝑘+1(∑1≤𝑖 <⋯<𝑖 ≤𝑛|𝐴𝑖 ∩ … . .∩ 𝐴𝑖 |)A
𝑖=1 𝑘=1 1 𝑘 1 𝑘

4. Sample Problem:

Q.1. In a town there are 2000 literate persons. of them 60% read newspaper A, 55%

read newspaper B and 20% read neither A nor B. How many persons read (i) both

newspapers A and B? (ii) only one newspaper?

Solution: Let there be 100 literate persons in the town. Given that 20 of them do not

read any newspaper. This means 100-20 = 80 read A or B or both.

Since 60 read A, 80 - 60 = 20 read only B.

Since 55 read B, 50 - 55 = 25 read A only.

80 – (20+25) =35 read both.

Number of persons reading both newspapers =2000× 35 = 700
100
Q.2 Find the number of positive integers n where 1≤n≤100 and n is not divisible by 2, 3
or 5.

Solution: Let us denote the sets by A, B, C respectively. Then we have

n(A)=50, n(B)=33, n(C)=20, n(A B) =16, n(AC) =10, n(B C) =6,
n(A B C) =3

Number of integers divisible by 2 or 3 or 5 is

n(A B C)  n(A)  n(B)  n(C) n(A B) n(BC) n(CA)  n(ABC)
=50+33+20-16-6-10+3=74
Number which are not divisible by 2 or 3 or 5 =n(S)-n(A B  C) =100 – 74 = 26

Exercise 3
1. It is known that at the university 60% of the professors play tennis, 50% of them play
bridge,70% jog, 20% play tennis and bridge, 30% play tennis and jog, 40% play bridge and
jog. If someone claimed that 20% of the professor’s jog and play bridge and tennis, would
you believe this claim? Why?
2. Thirty cars are assembled in a factory. The options available were a radio, AC and
white-wall tyres. It is known that 15 of the cars have radio, 8 of them AC and 6 of them white-
wall tyres. 3 of them have all 3 options. Find how many cars don’t have any options at
all.
3. 75 Children went to an amusement park where they can ride on the merry-go-round,
roller coaster and ferris wheel. It is known that 20 of them have taken all 3 rides, and 55
8
 Mathematics – III (CS & E)
of them have taken at least two of the 3 rides. Each ride costs 0.50 Rs and the total
receipt of the amusement park was 70 Rs. Determine the number of children who did
not try any of the rides.

Let’s check the takeaway from lecture

Choose the correct option from the following:

1. Is this A×(B∪C) =(A×B) ∪ (A×C) correct?

(a) Yes (b) No (c) don’t know
2. Is this PQ  P  R correct?

9
SE Semester III-CBCGS HME 2021-22
(a) Yes (b) No (c) don’t know

Homework Problems for the day

1. A menu in the restaurant read like the following:
Group A: Tomato soup, Manchow soup, Spring soup, Roasted papad
Group B: Almond Ice-creame, Chowmin, Gobhi Paratha
Group C: Sweet corn, French fries, Fried rice, Dal-rice, salad
Group D: Coffee, Tea, Milk

I. Suppose you select one course from each group without omission or substitution.
How many complete different four course dinner you can make out of this menu?
II. Suppose you select one course from each group A, B and D and two courses from
group C without omission or substitution. How many different dinner you can
make out of this menu?
2. A survey of a sample of 25 new cars being sold by an auto-dealer was conducted to see
which of the three options: air-conditioning, radio and power windows were already
installed. The survey found: 15 had air-conditioning, 12 had radio, 11 had power
windows, 5 had air-conditioning and power windows, 9 had air-conditioning and
radio, 4 had radio and power windows and 3 had all the three options. Find the number
of cars that had:
(a) only power windows (b) only one of the options (c) at least one option (d) none of
the options (e) air-conditioning and radio but not power windows.
3. A survey of 500 television viewers of a sports channel produced the following information:
285 watch crickets, 195 watch hockey, 115 watch football, 45 watch cricket and
football, 70 watch cricket and hockey, 50 watch hockey and football and 50 do not watch
any of the three kinds of games.
Learning from the topic: Students will be able to understand the real-life application
of Principal of inclusion and exclusion.
Pigeonhole Principal

Lecture -04
1. Learning Objective: Student shall be able to learn Pigeonhole Principal and counting
problems related to it.
2. Introduction: Pigeonhole principal is another counting principal. This principal talks
about the that there must be an object or objects with certain characteristic. For
example, if we consider the case of having been born on the same day of the week for
two people in a group of eight people then this theorem guarantees that there are at
least two people but does not identify the individual members.
3. Important Formulae/ Theorems / Properties:
(i) Pigeonhole Principle: If n pigeons are assigned to m Pigeonholes and m < n
then at least one Pigeonhole contains two or more pigeons.
(ii) The extended Pigeonhole Principle: If there are m Pigeonholes and more than
2m, 3m, …. Pigeons, then at least one Pigeonhole will have more than 2,
3,…..pigeons respectivily.
4. Sample Problem:
10
 Mathematics – III (CS & E)
Q.1. If eight persons are chosen from any group, show that at least two of them will
have the same birthday.
Solution:
There are seven days in a week. These 7 days are 7 pigeonholes and 8 persons
from the group are 8 pigeons. Since there are more pigeons than the pigeonholes,
at least two persons will have the same birthday.
Q.2. If any 5 numbers are chosen from 1 to 8, show that the sum of two of them will
be 9.
Solution:
Let us construct 4 sets each containing two numbers out of the above 8 numbers such
that the sum of them is 9 as follows: (1,8), (2,7), (3,6), (4,5). Each of the 5 numbers
chosen from 1 to 8 must belong to one of these 4 sets. Since there are four sets and
we have chosen 5 numbers, the pigeonhole principle states that two of the chosen
numbers must belong to the same set.
Q.3. Show that in a group of 50 students at least 5 are born in the same month.
Solution:
Consider the months as pigeonholes and students as pigeons. Consider even
distribution, if there are 48 students, (48/12=4) 4 are born in each month. Since
there are 50 students at least 5 are born in the same month.
Exercise 4
1. If five points are taken in a square of side 2 units, show that atleast two of them are
̅
no more than ̅ √̅2̅ units apart.
2. Consider a regular hexagon whose sides are of length 1 unit. If any seven points are
chosen in the region bounded by the hexagon, show hat at least two of them will be
no more than 1 unit apart.
3. Consider an equilateral triangle whose sides are of length 3 units. If ten points are chosen
lying on or inside the triangle, then shoe that atleast two of them are no kore than 1 unit
apart.
4. Show that if any ten positive integers are chosen, two of them will have the same
remainder when divided by 9.
5. Show that any set of six positive integer whose sum is 13 must contain a subset
whose sum is three.
Let’s check the takeaway from lecture
Choose the correct option from the following:
1. If 7 colors are used to paint 50 bicycles at least how many bicycles will be of the
same color?
(a) 2 (b) 7 (c) 8 (d) 6
2. If nine persons are chosen from any group, then how many of them will have
the same birthday ?
(a) least two (b) least three (c) least four (d) don’t know

Homework Problems for the day

1. Show that if 7 numbers are chosen from 1 to 12 then two of them will add upto 13.
2. Show that among any group of 5 integers (not necessarily consecutive), there are two
with the same remainder when divided by 4.
3. If a fair die is thrown 7 times show that it will show one of the numbers 1,2,3,4,5 and
13
SE Semester III-CBCGS HME 2021-22
6 atleast twice.
4. If a number has 11digits then show that atleast two digits are repeated.
5. What is the least number of people required to guarantee that atleast two of them are
born (i) on the same day, (ii) in the same month?

Learning from the topic: Student will be able to learn Pigeonhole Principal and
counting problems related to it.

Problems for Self-assessment: Level 1

1. Let A,B,C Be the three non-empty sets the under what condition is the following
statement is true.
(a) (A-B)∪ (A-C)=A
(b) (A-B) ∪ (A-C)=

2 . Let A,B,C Be the three non-empty sets the under what condition is the following
statement is true.
(a) (A-B)∩ (A-C)= 
(b) (A-B)  (A-C)= 
3. Six friends discover that they have total of Rs 21.61with them on a trip for movie
.Show that one or more of them have at least Rs 3.61.
3. Prove that if any 14 integers are chosen from 1 to 25 then one of them is a multiple of
another number in the subset.
5. Prove that 5+10+15+…+5n=5𝑛(𝑛+1) by mathematical Induction.
2

Level 2
1. Given that A-B=B what can be concluded about A and B .
2. Show that (A-B)-C=A-(BUC).
3. Show that there must be at least 90 ways to choose six integers from 1 to 15 so that all
the choices have the same sum.
4. Determine the cardinality of the set {n7: where n is a positive integer }
5. Prove by mathematical induction that n4-4n2 is divisible by 3 for all n≥ 2.

Level 3
1. Let A and b are two arbitrary set show that P(A∩ B)= P(A) ∩ P(B).
2. Show that for any integer n ,11𝑛+2 + 122𝑛+1 is always divisible by the 133.
3. How many friends must you have to guarantee at least five of them will have
birthday in same month?
4. Determine the number of integer between 1 and 250 that are divisible by any of
integers 2,3,5,7 .

12
 Mathematics – III (CS & E)
5. Find the least n for which the statement true and then prove that (1+n2)<2n.

Digital references:
1) [Link]
2) [Link]

Learning Outcomes:
1. Know: Student should be able to

a) set theory
b) Mathematical induction
c) Pegion hole principale and its application.
2. Comprehend: Student should be able to comprehend concept of set theory and counting
principals and mathematical induction.
3. Apply, analyze and synthesize: Student should be able to
Apply set theory and counting principal aling with application of mathematical induction

Self-Evaluation

Name of student: Class & Div : Roll No:

Add to Knowledge: Set theory is the mathematical theory of well-determined collections, called
sets, of objects that are called members, or elements, of the set. Pure set theory deals
exclusively with sets, so the only sets under consideration are those whose members are also
sets. The theory of the hereditarily-finite sets, namely those finite sets whose elements are
also finite sets, the elements of which are also finite, and so on, is formally equivalent to
arithmetic. So, the essence of set theory is the study of infinite sets, and therefore it can be
defined as the mathematical theory of the actual—as opposed to potential—infinite..

13
SE Semester III-CBCGS HME 2021-22

1. Are you able to evaluate the different probleams of set operation?

(a) Yes (b) No

2. Do you understand how to use pegion hole principal

(a) Yes (b) No

3. Will you able to identify problam of mathematical Induction?

(a) Yes (b) No

4. Are you able to apply the counting pricipal?

(a) Yes (b) No

5. Do you understood this module?

(a) Fully understood (b) Partially understood (c) Not at all

14
 Mathematics – III (CS & E)

Module 2
Relation & Function

1. Motivation: The present module deals with the relation and functions. In particular,
the student should be able use the Concept of the relation and functions in higher
mathematics & their project work.
Two variables may be linked by some type of relationship. That brings us to the concept of
relations. In contrast, a function defines how one variable depends on one or more other
variables. There is nothing such as application of functions in our daily life. Like we use
differentiation to find velocity, integration to find areas and volumes, Linear
programming to get maximum profit, functions cannot be used like this, but it makes our
mathematics easy, it becomes hard to explain mathematics without functions.
2. Syllabus:

Module Content Duration Self-

study
No. Weightage
duration

2 Definition, types of relation, composition 7 Hrs 10 Hrs 20 Marks

of relations, pictorial representation of
relation (Digraphs), properties of
relation, partial ordering relation.
Operations on relations, Closures,
Warshall’s algorithm
Function: Definition and types of
function, composition of functions,
Generating Functions.

3. Prerequisite: Concept of Number system, set theory

4. Learning Objective:
1. Student shall be able to know different types of relations.
2. Student shall be able to identify domain and range of a relation.
3. Student shall be able to find pictorial representation of relation, properties of
relation, partial ordering relation.
4. Student shall be able to know different types of function.
15
SE Semester III-CBCGS HME 2021-22
5. Student shall be able to find composition of functions.
6. Student shall be able to distinguish between recursively defined functions.

Relation: Definition, Types of Relation

Lecture: 07
1. Learning Objective: Students shall be able to understand the mathematical modelling
of the Relation.

2. Introduction: A relation between two sets is a collection of ordered pairs containing one
object from each set. If the object x is from the first set and the object y is from the
second set, then the objects are said to be related if the ordered pair (x,y) is in the
relation. A function is a type of relation

3. Key Notations & definitions:

1. R= the set of all real numbers.
2. Z: the set of all integers positive or negative including zero.

Relation: If A and B are two non-empty sets, then a relation R from A to B is a subset of A x
B. If R ⊆ A x B and (a, b) ∈ R, then we say that a is related to b by the relation R, written as
a R b.

Domain and Range of a Relation

Let R be a relation from a set A to set B. Then, set of all first components A or coordinates of the
ordered pairs belonging to R is called is the domain of R, denoted by Dom(R). While the set of
all second components B or coordinates of the ordered pairs belonging to R is called the
range of R, denoted by Ran(R). Thus, domain of R = {a: (a, b) ∈ R} and range of
R = {b: (a, b) ∈ R}
Definition: A binary relation R on a set A is a subset of A × A or a relation from A to A.

Inverse Relation:
If A and B are two non-empty sets and R be a relation from A to B, such that R = {(a, b) : a
∈A, b ∈ B}, then the inverse of R, denoted by R-1 , a relation from B to A and is defined by
R-1 = {(b, a) : (a, b) ∈ R}

4. Important Formulae/ Theorems / Properties on Relations:

Types and Properties of Relations

(i) Void Relation: As Φ ⊂ A x A, for any set A, so Φ is a relation on A, called the empty or
Void relation.

(ii) Universal Relation: Since, A x A ⊆ A x A, so A x A is a relation on A, called the

universal relation.

(iii) Identity Relation: The relation IA = {(a, a): a ∈ A} is called the identity relation on A.
16
 Mathematics – III (CS & E)

5. Sample Problem:

1. Let A = {1, 2, 3, 4}. Find the relation R = {(a, b) | a divides b} .

Solution: R= {(1,1), (1, 2), (1,3), (1, 4), (2, 2), (2, 4), (3, 3),(4, 4)}.

2. How many relations are there on a set A?

Solution: Because a relation on A is the same thing as a subset of A ⨉ A, we count the
subsets of A × A. Since A × A has n2 elements when A has n elements, and a set with
m elements has 2m subsets, there are subsets of A × A. Therefore, there are relations
on a set A.

3. Consider these relations on the set of integers:

R1 = {(a,b) | a ≤ b}, R4 = {(a,b) | a = b},
R2 = {(a,b) | a > b}, R5 = {(a,b) | a = b + 1},
R3 = {(a,b) | a = b or a = −b}, R6 = {(a,b) | a + b ≤ 3}.
Which of these relations contain each of the pairs?
(1,1), (1, 2), (2, 1), (1, −1), and (2, 2)?
Solution: Checking the conditions that define each relation, we see that the pair (1,1) is in
R1, R3, R4, and R6: (1,2) is in R1 and R6: (2,1) is in R2, R5, and R6: (1, −1) is in R2, R3, and
R6: (2,2) is in R1, R3, and R4.

4. Let A= {eggs, milk, corn} and B= {cows, goats, hens} we can define a relation r from A
to b by (a, b)R if a is produced by the b.
Solution: The relation will be formed as R={(eggs, hens),(Milk, Cows),(Milk, Goat)}.

Exercise 07

1. Given A={1 ,2,3} and B={ a , b} then Find . (a) A×B (b) B×A (c) B×B.
2. Given that A= {1,2} ,b={ x, y, z} and c={3,4} Find A×B×C.
3. Find the Number of relation from A= {a, b, c} to B={1,2}.
4. Find x and y given that (2x , x+y)=(6,2)
5. Let R be the relation on the positive integer N defined by the equation x+3y=12 that is
R={(x , y): x+3y=12}.
6. Prove that (A×B)∩( A× C) =A× (B∩ 𝐶)

Let’s check the takeaway from lecture

1. The relation R defined in A = {1, 2, 3} by aRb, if | a2 – b2 | ≤ 5. Which of the following

is false?
(a) R = {(1, 1), (2, 2), (3, 3), (2, 1), (1, 2), (2, 3), (3, 2)}
(b) R–1 = R
(c) Domain of R = {1, 2, 3}
(d) Range of R = {5}
2. The relation R defined on the set A = {1, 2, 3, 4, 5} by R = {(x, y) : | x2 – y2| < 16} is
given by
(a) {(1, 1), (2, 1), (3, 1), (4, 1), (2, 3)}
(b) {(2, 2), (3, 2), (4, 2), (2, 4)}
(c) {(3, 3), (4, 3), (5, 4), (3, 4)}
17
SE Semester III-CBCGS HME 2021-22
(d) None of the above
Homework Problems for the day
1. Confirm or disprove the Identity that (A∪ B) ×(C∪D) =(A×C)∪ (𝐵 × 𝐷).
2. Show that (A ∩ B) ×(C ∩D) =(A×C) ∩ (𝐵 × 𝐷).
3. Let A= {1,2}. construct the set P(A) × A.
4. Let A be the set of workers and B be the set of jobs. Let R1 be a binary relation from A
to B such that (a,b) is in R1 if worker a is assigned the job b(we assume that worker might
be assigned to more than one job and more than one worker might be assigned to the
same job.). Let R2 be a binary relation on A such that (a1, a2) is in R2 if a1 and a2 can get
along with each other if they were assigned with same job. State a condition in term of R1,
R2 and binary relation derived from R1 and R2 such that an assignment to the job s
according to R1 will not put workers that cannot get along with one other on same job.
Composition of Relations, Pictorial Representation of Relation (Digraphs)

Lecture: 08
1. Learning objective: Students shall be able to understand the composition of two
relation and the pictorial representation of the Relation.
2. Introduction: Two Relation can be clubbed with each other by the process of
composition. The visual understanding of relation can be seen by its pictorial
representation.
3. Definition:
(1) Composition of Relation
Let R and S be two relations from sets A to B and B to C respectively, then we can
define Relation S o R from A to C such that (a, c) ∈ So R ⇔ ∃ b ∈ B such that
(a, b) ∈ R and (b, c) ∈ S. This relation S o R is called the composition of R and S.
(i) R o S ≠ S o R (ii) (S o R)-1 = R-1 o S-1
known as reversal rule.
(2) Representation of Relations of Finite set: Suppose A and B are finite sets. The
following are two ways of picturing a relation R from A to B.

(i) Form a rectangular array whose rows are labeled by the elements of A and whose
columns are labeled by the elements of B. Put a 1 or 0 in each position of the
array according as aAis or is not related to bB. This array is called the matrix of
the relation.
(ii) Write down the elements of A and elements of b in two disjoint disks and then draw
an arrow from aA to bB whenever a is related to b. This picture will be
called the arrow diagram of the relation.
(iii) There is another way of picturing a relation R when R is relation from a finite
set to itself. First, we write down all the elements of the set and then we draw
an arrow from each element x to the element y whenever x is related to y. This
diagram is called diagraph or directed graph of the relation.

(3) Composition of Relation and Matrices: Let A, B, C be three non-empty sets

and R is relation from A to B and S be a relation from B to C. Let MR and Ms
denote respectively the matrices of the relation R and S. Then Multiplying MR
and Ms we obtain the matrix M which represent the matrix presentation of Ros
i.e., MROS.
(4) Representing Relations Using Digraphs
18
 Mathematics – III (CS & E)

(i) Draw a small circle for each element of A and write the element in that
circle. These circles are called vertices.
(ii) If the element 𝑎𝑖 is related to the element 𝑎𝑗 i.e., 𝑎𝑖𝑅𝑎𝑗 draw a straight line
or an arc with an arrow in the direction from 𝑎𝑖 to 𝑎𝑗. Such a straight line or
an arc with an arrow is called an edge.
(iii) If an element 𝑎𝑖 is related to itself, we draw an arc with an arrowhead starting and
ending at 𝑎𝑗. Such an arc is called a loop.
(iv) The resulting pictorial representation is called directed graph or diagraph
of R.
(v) Thus, if a relation R on A is represented by a digraph, then the edges and
loops in the diagraph correspond to the pairs in R and the vertices
correspond to the element of A.
(vi) Conversely if a diagraph is given, we can write the set of the corresponding
relation.

4. Sample Problem:
(1) Suppose that A = {1,2,3} and B = {1,2}. Let R be the relation from A to B
containing (a,b) if a ∈ A, b ∈ B, and a > b. What is the matrix representing R
(Assuming the ordering of elements is the same as the increasing numerical
order)?
Solution: Because R = {(2,1), (3,1),(3,2)}, the matrix is

0 0
MR=[1 0]
1 0
(2) Let A = {a1,a2, a3} and B = {b1,b2, b3,b4, b5}. Which ordered pairs are in the
relation R represented by the matrix.

0 1 0 0 0
MR=[1 0 1 1 0]
1 0 1 0 1
Solution: Because R consists of those ordered pairs (ai,bj) with mij = 1, it follows
that: R = {(a1, b2), (a2, b1),(a2, b3), (a2, b4),(a3, b1), {(a3, b3), (a3, b5)}.
(4) Let A={a,b,c,d} and let r be the relation on A that has a Matrix.
1 0 0 0
0 1 0 0
MR=[ ]
1 1 1 0
0 1 0 1
Solution:
b

c
a

19
SE Semester III-CBCGS HME 2021-22

d
The diagraph of the relation R is shown in the figure. The following table gives the
indegree and outdegree of all the vertices. Note that sum of all the indegrees must
equal the sum of all out degrees.

a b c D
In-degree 2 3 1 1
Out- degree 1 1 3 2

(3). Let A={1,4,5} and Let R be given by the diagraph shown in the following figure

5
1 0 1 1
Solution: MR= 4 [1 1 0] R= {(1,4),(1,5),(4,1),(4,4),(5,4),(5,5)}
5 0 1 1

Exercise 08
1. Let A= {a, b, c} and let r and s be the relation on A whose Matrices are

1 0 1 1 0 0
MR= [1 1 1] & Ms= [0 1 1] then show that MSoR=MR ×MS .
0 1 0 1 0 1
2. Let A= {a , b} ,R={(a, a) ,(b, a) , (b, b) } and .Then find SoR and RoS.
3. Let A={1,2,3,4} and let R={(1,1) ,(1,2), (2,3) ,(2,4) (3,4) ,(4,1) ,(4,2) } S={ (3,1) ,(4,4) ,(2,3)
,(2,4) ,(1,1) ,(1,4)} Than compute RoR, SoR, RoS ,SoS .
4. Find the Relation represented by the diagraph.
2

1 3

5 4

5. If A={1,2,3,4} ,B={1,4,6,8,9} if aRb if and only if b=a2 and aSb if and only if a<b than
find R and S , is Ros possible to evaluate .

Let’s check the takeaway from lecture

1. Let X = {4, 5, 6}, Y = {a, b, c} and Z = {l, m, n}. Consider the relation R1 from X to Y and

20
 Mathematics – III (CS & E)

R2 from Y to Z. R1 = {(4, a), (4, b), (5, c), (6, a), (6, c)} and R2 = {(a, l), (a, n), (b, l), (b,m),
(c, l), (c, m), (c, n)} than composition of R1 o R2 is
(a) {(4, l), (4, n), (4, m), (5, l), (5, m), (n, n), (6, l), (6, m), (m, n)}
(b) {(4, l), (n, 4), (4, m), (l, 5 ), (5, m), (5, n), (6, l), (6, m), (6, n)}
(c) {(4, l), (4, n), (4, m), (5, l), (5, m), (5, n), (6, l), (6, m), (6, n)}
(d) {(4, l), (4, n), (4, m), (5, l), (5, m), (5, n), (l, l), (6, m), (n, n)}
2. The R o R in the above example is
(a) {(2, 2), (3, 2), (2, 3), (3, 4), (2, 2), (4, 5), (5, 2), (5, 3), (5, 5)}
(b) {(2, 2), (3, 2), (3, 3), (3, 4), (4, 2), (4, 5), (5, 2), (5, 3), (5, 5)}
(c) {(2, 2), (3, 2), (3, 3), (5, 4), (5, 2), (4, 5), (5, 2), (5, 3), (5, 5)}
(d) {(2, 2), (3, 2), (3, 3), (3, 4), (4, 2), (4, 4), (5, 2), (5, 4), (5, 5)}

Homework Problems for the day

01 1 0 1
1. If A= {1,2,3,4} and MR=[ 1 0 than find the diagraph of It.

]
0 0 1 1
1 0 0 0
1 1 0 0 0
⎡0 0 1 1 0⎤
2. Let A={a, b, c, d, e} and MR= 0 0 0 1 1 than find the diagraph of It.
⎢0 1 1 0 0⎥
[1 0 0 0 0]
3. Let R be the Relation whose diagraph is given as

1 3

7 5

6
If R is defined on {1,2,3} and S is defined on {4,5,6,7} then find RoS.

4. What are the ordered pairs in the relation represented by this directed graph?

21
SE Semester III-CBCGS HME 2021-22

Properties of Relation, Partial Ordering Relation

Lecture: 09
1. Learning objective: Students shall be able to understand the properties of the relation and
the partial order Relation.
2. Introduction: In many applications to the computer science and applied mathematics,
we deal with relations on the set A rather than relations from A to B. Moreover, these
relation s often satisfy certain properties.

3. Definition:
(i ) Reflexive Relation: A relation R is said to be reflexive relation if every element of A
is related to itself. Thus, (a, a) ∈ R, ∀ a ∈ A = R is reflexive.

(ii) Symmetric Relation: A relation R is said to be symmetric relation, iff (a, b) ∈ R (b, a)
∈ R, ∀ a, b ∈ A i.e., a R b ⇒ b R a, ∀ a, b ∈ A ⇒ R is symmetric.

(iii) Anti-Symmetric Relation: A Relation R is said to be anti-symmetric relation, iff

(a, b) ∈ R and (b, a) ∈ R ⇒ a = b, ∀ a, b ∈ A.
(iv) Transitive Relation: A relation R is said to be transitive relation, iff (a, b) ∈ R and (b,
c)∈ R ⇒ (a, c) ∈ R, ∀ a, b, c ∈ A

(v) Equivalence Relation: A Relation R is said to be an equivalence relation if it is

simultaneously reflexive, symmetric, and transitive on A.

(vi) Partial Order Relation: A Relation R is said to be a partial order relation, if it is

simultaneously reflexive, symmetric, and anti-symmetric on A.

(vii) Total Order Relation: A Relation R on a set A is said to be a total order relation on
A, if R is a partial order relation on A.

(viii) Equivalence Classes of an Equivalence Relation

Let R be equivalence relation in A (≠ Φ). Let a ∈ A. Then, the equivalence class of a
denoted by [a] or {a} is defined as the set of all those points of A which are related to a
under the relation R.

(ix) Congruence Modulo m

Let m be an arbitrary but fixed integer. Two integers a and b are said to be congruence
modulo m, if a – b is divisible by m and we write a ≡ b (mod m).i.e., a ≡ b (mod m) ⇔ a
– b is divisible by m.

Important Results on Relation

1. If R and S are two equivalence relations on a set A, then R ∩ S is also on ‘equivalence
relation on A.
2. The union of two equivalence relations on a set is not necessarily an equivalence
relation on the set.
3. If R is an equivalence relation on a set A, then R-1 is also an equivalence relation on
A.

22
 Mathematics – III (CS & E)

4. If a set A has n elements, then number of reflexive relations from A to A is 2n2-2

5. Let A and B be two non-empty finite sets consisting of m and n elements,
respectively. Then, A x B consists of mn ordered pairs. So, total number of relations
from A to B is 2nm.

4. Sample Problems:

Q (1) Let A={ 0,1,2,3} and a relation R on A be given

by R={ (0,0), (0,1), (0,3), (1,0), (1,1), (2,2), (3,0),

(3,3) } .

Is R reflexive? symmetric? transitive?

Solution: (a) R is reflexive, i.e. there is a loop at each vertex.

(b) R is symmetric, i.e. the arrows joining a pair of different vertices always appear in a
pair with opposite arrow directions.
(c) R is not transitive. This is because otherwise the arrow from 1 to 0 and arrow from 0 to
3 would imply the existence of an arrow from 1 to 3 (which doesn't exist). In other words (1,0)
R, (0,3) R and (1,3) R imply R is not transitive.

Q (2) Let m, n and d be integers with d 0. Then if d divides (m-n), denoted by d | (m-n),
i.e. m-n=dk for some integer k, then we say m is congruent to n modulo d, written simply
as m ≡n (mod d).

Solution: Let R be the relation of congruence modulo 3 on the set of all integers, i.e. m R
n m n (mod) 3 3 | (m-n) . Show R is an equivalence relation.

We just need to verify that R is reflexive, symmetric, and transitive.

(a) Reflexive: for any n we have nRn because 3 divides n-n=0.

(b) Symmetric: for any m,n if mRn, i.e. m n (mod 3) then there exists a k such

that m-n =3k. This means n-m=3(-k), i.e. n m (mod 3), implying finally nRm. For

example, 7R4 is equivalent to 4R7 can be seen from

7R4 7 4 (mod 3) 7-4 =3 1 4-7 =3 (-1) 4 7 (mod 3) 4R7

(c) Transitive: for any m,n,p , if mRn and nRp, then there exists r,s such that m-n =3r
and n-p=3s. Hence m-p=(m-n)+(n-p)=3(r+s), i.e., mRp.
We thus conclude that R is an equivalence relation

Exercise 09

23
SE Semester III-CBCGS HME 2021-22

1. Determine the Relation on R on the set A is reflexive, irreflexive, symmetric, asymmetric,

antisymmetric, or transitive.
(i) A=Z; a R b if and only if a≤b+1.
(ii) A=Z+; aRb if and only if |𝑎 − 𝑏| ≤ 2.
(iii) A is the set of all people in the world aRb if and only if a is the sister of b.
2. Let A= {1,2,3,4} and R={ (1,1),(1,2),(2,1),(2,2),(3,1) ,(3,3),(1,3),(4,1),(4,4)} determine
whether R is an Equivalence relation on R.
3. Let A=the set all people in the social security database aRb if and only if a and b have
same last name.
4. If {{1,3,5,7,9},{2,4,6,8,10}} is the partition of the set A={1,2,3,…10}, determine the
corresponding equivalence relation R.
5. Let A=R×R. define the following relation R on A: (a,b) R(c,d) if and only if a2+b2=c2+d2
(a) Show that R is an Equivalence Relation
(b) Compute A/R
Let’s check the takeaway from lecture

1. which of the following is not an equivalence relation on the set of integers?

(a) xRy iff x – y is an even integer (b) xRy iff x + y is even integer (c) xRy iff x = y
(d ) xRy iff x ≤ y.

2. Let A = {a, b, c} and relation R= {(a, a), (b, b), (c, c), (b, c)} n a set A, then R is
(a) transitive relation (b) Symmetric relation (c) equivalence relation (d) None of these
3. A relation R on a set of real numbers defined as R ={(a,b): a ≤ b2 } is
(a)Reflexive (b) Symmetric (c) Transitive (d) None of the above
5. Let A = {1,2,3}, which of the following is not an equivalence relation on A?
(a) {(1,1,), (2,2,), (3,3)} (b) {(1,1,), (2,2,), (3,3), (1,2), (2,1)} (c) {(1,1,), (2,2,), (3,3), (2,3), (3,2)}
(d) None of the above.
Homework Problems for the day
1. Determine the Relation on R on the set A is reflexive, irreflexive, symmetric,
asymmetric, antisymmetric, or transitive.
(i) A=Z+, aRb if and only if a=bk for some k∈ 𝑍+ .
(ii) A is the set of all order pair of real numbers (a,b) R (c,d) if and only if a=c.
2. If A=Z+×Z+; (a, b) R (c, d) if and only if b=d. Check it is an equivalence relation or not?
3. Let S = {1,2,3,4,5} and A=S X S define the following relation R on A: (a, b) R (a’, b’) if and
only if ab’=a’b.
(i) Show that R is an Equivalence Relation.
(ii) Compute A/R
4. Let A= {a, b, c, d, e} and R is Relation on A defined by

24
 Mathematics – III (CS & E)

1 1 1 0 1
⎡1 1 1 0 1⎤
MR= 1 1 1 0 1
⎢0 0 0 1 0⎥
R. [1 1 1 0 1]
Compute A/
Operation On the Relation

Lecture: 10
1. Learning objective: Students shall be able to understand the operation on the Relation.
2. Introduction: Up till now we have seen the relation and its classifications. Now we
proceed towards the operations on relation which together with relation form the
Mathematical Structure.
3. Definition:
Complementary Relation: Let R and S be Relations from Set A to Set B. If we remember that R
ans S are simply subset of AXB Complement of R, 𝑅̅ is referred as Complementary Relation. It
can be explained by a 𝑅̅ b if and only if a𝑅 b.
4. Sample Example:
Q (1): Let A= {1,2,3,4} and B= {a, b, c}. Let R= {(1, a), (1, b), (2, b), (2, c), (3, b), (4, a)}
And S= {(1, b), (2, c), (3, b), (4, b)} than compute ( a) 𝑅̅ (b) R∩S (c) R∪S and (d) R-1
Solution:

(a) We first find that

AXB= {(1, a), (1, b), (1, c), (2, a), (2, b), (2, c), (3, a), (3, b), (3, c), (4, a), (4, b), (4, c)}
Then the complement of R in AXB is 𝑅̅ = {(1, c), (2, a), (3, a), (3, c), (4, b), (4, c)}
(b) We have R∩S = {(1, b), (3, b),(2, c)}
(c) We have R∪S = {(1, a),(1,b),(2,b),(2,c),(3,b),(4,a),(4,b)}
(d) Since (x,y)∈R-1 if and only if (y,x) ∈R we have R-1={(a,1),(b,1),(b,2),(c,2),(b,3),(a,4)}

Exercise 10

1. Let R and S be the relation on A then prove that

̅
(a) If R is symmetric so are R-1 and 𝑅
(b) If R and S are symmetric, so are R∩S and R∪S.

2. Let R be a Relation from A to B and let S be a relation from B to C. Then for A1 which is subset of A
we have SoR(A1)=S(R(A1)).
3. Let R and S be symmetric relation s on the set A. Prove or disprove that R-S is also a
symmetric relation on A.
4. Let A, B and C be sets, R a relation from a to B and S a Relation from b to c Then prove that
(SoR)-1=R-1oS-1 .
5.

Let’s check the takeaway from lecture

1. Let A= {1,2,3} and B= {1,2,3} and R= {(1,1),(1,2),(2,3),(3,1)} then 𝑅̅is

(a) {(1,3) ,(2,1),(2,2),(3,2),(3,3)} (b) {(2,3),(2,1),(2,2),(3,2),(3,3)}
(c) {(1,3),(1,1),(2,2),(3,2),(3,3)} (d) {(1,3),(2,1),(2,2),(3,2))}

25
SE Semester III-CBCGS HME 2021-22

2. Let A=B=C= Set of real number . Let R and S be the following relation from A to B and
From B to C respectively R={(a,b): a≤2b} and S={(b,c): b≤3c} than is (2,3)∈ 𝑅𝑜𝑆 .

(a) True (b) False (c) Cannot be said

Homework Problems for the day

1. Let R and S are relation from A to B. than prove the following
(a) If R⊆ S then R-1⊆ S-1 .
̅
(b) If R⊆ S then 𝑠̅̅ ⊆ 𝑅
2. Let A= Set of people. Let aRb if and only if a is older than b; let aSb if and only if a and b are
sister Describe R∪ S.
3. Let A={2,3,6,12} and let R and S be the following relation on A : xRy if and Only if 2∖
(𝑥 − 𝑦); xSy if and only if 3∖ (𝑥 − 𝑦)then compute
(a) 𝑅̅ (b) R∩S (c) R∪S (d) S-1

Closures, Warshall’s Algorithm

Lecture: 11
1. Learning objective: Students shall be able to understand the concept of closure of a relation
and methods to find the closure.
2. Introduction: The closure of a relation R with respect to property p is
the relation obtained by adding the minimum number of ordered pairs to r to obtain property
p. in terms of the digraph representation of R.
3. Definition:
(i) Reflexive Closure: If R is a relation on a set A then the smallest relation which is reflexive
and Contain R is called the Reflexive closure of R.

(ii) Symmetric Closure: If R is a relation on a set A then the smallest relation on A which is
symmetric and contain R is called the symmetric closure of R.

(iii) Transitive closure: If R is a relation on a set A then the smallest transitive relation on A
which contain R is called Transitive closure of R it is represented by 𝑅∞.

(iv) Warshall’s Algorithm: A general method to find the transitive closure is available. It
is known as Warshall’s algorithm .Let R be a relation on a set A={a 1,a2,…,an}.

Interior vertices

If x1,x2,…xm is a path in R, then any vertices other than x1 and xm are called interior
vertices of the path.

Boolean matrix Wk (n matrices with size n-by-n): For 1 ≤ k ≤n, Wk has a 1 in position
i , j if and only if there is a path from ai to aj in R whose interior vertices, if any, come
from the set {a1,a2, …, ak}

Wn=M R∞

26
 Mathematics – III (CS & E)

Since any vertex must come from the set {a1,a2,…,an}, it follows that the matrix Wn has a
1 in position i , j if some path in R connects a i with aj

• How to compute Wk k=1,2,…n

Let W0=MR and Support Wk-1=[sij] is known, let Wk=[tij] then if tij =1, then there must
be a path from ai to aj whose interior vertices come from the set {a1,a2, …,ak}.

Case 1: If ak is not an interior vertex of this path, then all interior vertices must actually
come from the set {a1,a2,…ak-1}, so sij=1.

Case 2: If ak is an interior vertex of this path, then sik=1 and skj=1

ak P1, P2 are sub paths with all interiors

P2
P
a 1 vertices from {a1,a2, …, ak-1}

i aj
Case 3: if m>n, there must have some vertex appearing two times in the path (why?),

saying xi = xj, where i<j . x0, x1, …, xi, …, xj, xj+1 … xm there must exists another path

from x0 to xm with length less than m (why?), x0, x1, …, xi, xj+1 … xm Therefore, if x0 R ∞

xm , we can find the shortest path from x 0 to xm with length less than or equal to n

(why?) , namely x0 R k xm 1≤ k≤ n

Steps of Warshall’s Algorithm: Warshall’s Algorithm is a more efficient algorithm for

computing transitive closure, the procedure of the algorithm is as follows:

Step1: First transfer Wk all 1’s in Wk-1

Step 2: List the locations p1,p2,… in column k of Wk-1, where the entry is 1 and the
locations q1,q2,… in row k of Wk-1, where the entry is 1

Step 3: Put 1’s in all the positions pi, qj of Wk

3. Sample Examples:

Q(1) Let A={ 1,2,3,4} and R={(1,2),(2,3),(3,4),(2,1)} Find the transitive closure of R.

Solution: The diagraph of this relation is as follows

27
SE Semester III-CBCGS HME 2021-22

1 3

The diagraph of R is shown in the figure Since 𝑅∞ is the transitive closure we can proceed

geometrically by computing all pathes. We see that from vertex 1 we have the path for the vertex

2,3,4 and 1 . Note that path from 1 to 1 proceeds from 1 to 2 to 1. Thus we see that the orderd pair

(1,1) ,(1,2),(1,3) and (1,4) are in 𝑅∞ Starting from the vertex 2 we have path to the vertex 2,1,3 and

4 so the ordered pair (2,1),(2,2),(2,3) and (2,4) are in 𝑅∞.The only other path is from vertex 3

to 4 so we have

𝑅∞={(1,1),(1,2),(1,3),(1,4),(2,1),(2,2),(2,3),(2,4),(3,4)}

Q(2) Let A={1,2,3} consider the relation on the set A is R={ (1,1),(1,2),(1,3),(3,3) } Then
reflexive closure of R

Solution: R’={(1,1),(1,2)(1,3),(2,2),(3,3)}

Q(3) Let A={1,2,3,4} consider the relation on the set A is R={(2,1),(2,3),(3,2),(3,3),(2,2),(4,2)}

Find the reflexive closure of R and symmetric closure of R

Solution: a) R’={(1,1),(2,1),(2,3),(3,2),(3,3)(2,2),(4,2),(4,4)} is the reflexive closure

b) R’’={(2,1),(1,2),(2,3),(3,2),(3,3),(2,2),(4,2),(2,4)} is the symmetric closure

Q(4) Consider the relation R defined

0 1 0 0
1 0 0 1
MR   
0 0 0 1
 
0 0 0 0

Find the transitive closure of it by Warshall’s Algorithm.

Solution:

0100 0100 pi: 1, 2

1010  pi: 2  
1110 
W0  M R    
 0001
0001 qj: 2 W1 qj: 1, 2, 3
   
0000 
  0000 

28
 Mathematics – III (COMP)
 

1110  1111 
1111 
 
pi: 1, 2 pi: 1, 2

1110  W3   
W2   
0001 qj: 4 0001 qj: ф
   
 0000  0000 

M R  W4  W3

Exercise 11

1. Let A={1,2,3,4} and R={(2,1),(2,3),(3,2),(3,3),(2,2),(4,2)}.Define Rr to be reflexive closure of

R and Rs to be the symmetric closure of R. Prove or disprove that the symmetric closure of
Rr is the same relation as the reflexive closure of Rs.

2. Let A={1,2,3,4} and R={(2,1),(2,3),(3,2),(3,3),(2,2),(4,2)}.Define R t to be the transitive closure

of R and Rs to be the symmetric closure of R .Prove or disprove that the symmetric closure
of Rt is the same relation as the transitive closure of Rs.

3. Let A={1,2,3,4} for the relation R whose matrix is given below, find the matrix of
transitive closure by using Warshall’s Algorithm

1 0 0 1 1 1 0 0
MR= 0 1
0 0
(i) [ 1 0
] (ii) MR = [ 0
]
0 0 1 0 0 0 0 0
0 0 0 1 0 0 1 0

4. Let A={1,2,3,4} and Let R and S be the relations on A described by

0 0 0 1 1 1 0 0
M =[ 0 0] 0 0]
R
0 0 and Ms =[ 1 0
0 1 0 0 0 0 1 0
0 0 1 0 0 1 0 1

Use Warshall’s algorithm to compute the transitive closure of R∪S.

Let’s check the takeaway from lecture

1. What approach is being followed in Floyd Warshall Algorithm?

a) Greedy technique b) Dynamic Programming c) Linear Programming d) Backtracking

2. In the given graph, how many intermediate vertices are required to travel from node a to

node e at a minimum cost?

31
SE Semester III-CBCGS HME 2021-22

a) 2 b) 0 c) 1 d) 3

Homework Problems for the day

1. Let A={1,2,3,4} for the relation R whose matrix is given below, find the matrix of
transitive closure by using Warshall’s Algorithm.

1 0 0 1 0 0 0 1
0 1 1 0] (ii) MR=[ 1 0 0 1]
(i) MR=[
0 1 1 0 0 1 0 1
1 0 0 1 0 0 1 0

2. Let A={a, b, c, d, e} and let R and S be the relations on A described by

1 0 1 0 1 0 1 0 1 0
⎡0 0 0 1 0⎤ ⎡1 1 0 0 1⎤
MR= 1 0 0 0 0 and Ms= 1 1 1 0 0
⎢0 0 1 1 0⎥ ⎢0 1 0 0 0⎥
[1 0 1 0 0] [0 1 0 1 0]

Use of Warshall’s algorithm to compute the transitive closure of R∪S.

Function: Definition and Types of Function

Lecture: 12
1. Learning objective: Students shall be able to understand the concept of function and
type of function.
2. Introduction: The closure of a relation R with respect to property p is
the relation obtained by adding the minimum number of ordered pairs to r to obtain property
p. in terms of the digraph representation of R.
3. Definition:
(i) Let A and B be nonempty sets. A function f from A to B, denoted f: A → B is an
assignment of each element of A to exactly one element of B. We write f(a) = b if b is the
unique element of B assigned by the function f to the element a of A.

or

A function f:A → B can also be defined as a subset of A×B (a relation). This subset is restricted
to be a relation where no two elements of the relation have the same first element.

(ii) Given a function f: A → B . We say f maps A to B or f is a mapping from A to B.

A is called the domain of f. B is called the codomain of f. If f(a) = b, then b is called the

image of a under f. and a is called the preimage of b. The range of f is the set of all

32
 Mathematics – III (COMP)

images of points in A under f. We denote it by f(A). Two functions are equal when they

have the same domain, the same codomain and map each element of the domain to the

same element of the codomain.

The function is categorized as follows:

Injection: A function f is said to be one-to-one , or injective, if and only if f(a) = f(b) implies that
a = b for all a and b in the domain of f. A function is said to be an injection if it is one- to-
one.

Surjection: A function f from A to B is called onto or surjective, if and only if for every
element b ∈ B there is an element a ∈ A with f(a) = b. A function f is called a surjection if it
is onto.

Bijection: A function f is a one-to-one correspondence, or a bijection, if it is both one-to-one and

onto (surjective and injective).

4. Sample Example:

Q(1) Define function, If ƒ converts a temperature in degrees Celsius C to degrees Fahrenheit

F.

Solution: The function converting degrees Fahrenheit to degrees Celsius would be a

suitable ƒ−1.

Q (2) Let f be the function from {a, b, c, d} to {1,2,3} defined by f(a) = 3, f(b) = 2, f(c) = 1, and
f(d) = 3. Is f an onto function?

Solution: Yes, f is onto since all three elements of the codomain are images of elements in
the domain. If the codomain were changed to {1,2,3,4}, f would not be onto.

Q (3) Is the function f(x) = x2 from the set of integers to the set of integers onto?

Solution: No. For example, f is not onto because there is no integer x with x2 = −1.

Q (4) Let A=B=R, the set of real numbers. Let f: A B be given by the formula f(x)=2 x3-1
3 1 1
and Let g: B A be given by g(y)=√ 𝑦 + . Show that f is bijection from A to B and g is
2 2
bijection between B and A.

3
1 3 3 1 1
Solution: Let x∈A and y=f(x)=2x -1. Then (y+1) =x therefore x=√ 𝑦 + =g(y) =gof(x)
2 2 2
33
SE Semester III-CBCGS HME 2021-22

Thus gof=1 A. similarly fog=1B Hence both f and g are bijections.

Exercise 12

1. Given f:Z->Z. Find whether function is one-to-one and whether it is onto. If the function
is not onto, determine range f(Z). f(x)=x 2+x.

2. Let A = {1,2,3} and B={1,2,3,4,5}. F={(1,1),(2,3),(3,4)} is a one-to-one function from A to B.

g={(1,1),(2,3),(3,3)} is a function but not one-to-one. Why?

3. Define Bijective function. Show that the function f: R - {2/5} -> R – {4/5} defined by f(x) =
(4x+3)/(5x-3) is a bijection.
4. A={1,2,3,4}, B={1,2,3,4,5,6}. How many functions are there from B to A. How many are
one-to- one and how many onto?

Let’s check the takeaway from lecture

1. Which of the following function f: Z X Z → Z is not onto?

a) f(a, b) = a + b b) f(a, b) = a c) f(a, b) = |b| d) f(a, b) = a – b
2. The value of ⌊1/2.⌊5/2⌋ ⌋ is

a) 1 b) 2 c) 3 d) 0.5

Homework Problems for the day

1. Determine whether the relation R from A to B is a function.
A= A set of People in United states, B={x: x is nine digit number}
aRb if b is a’s passport number.
2. In each part, Sets A and B and a function from A to B are given. Determine whether the
function is one to one or onto (or both or neither).
(a) A= {1/2,1/3,1/4}; B={x, y ,z , w}; f={(1/2,x),(1/4,y),(1/3,w)}
(b) A={1.1,7,0.06}; B={p, q}; f={(1.1,p),(7,q),(0.06,p)}
Composition and inverse of Functions

Lecture: 13
1. Learning Objective: Student will understand composition of the function and analyze the
existence of its inverse and generating function.
2. Introduction: The application of the function starts with the operation of the function
where two functions can be combined is called composition of two function. The
inverse of the function is f -1 which maps the function from codomain to domain.
3. Definition:

34
 Mathematics – III (COMP)

Composite Function: Let f: A → B and g: B → C be two functions, then gof is said to be

composite function of f and g. The function composition of two or more functions
takes the output of one or more functions as the input of others. The functions ƒ:
X → Y and g: Y → Z can be composed by first applying ƒ to an argument x to obtain y
= ƒ(x) and then applying g to y to obtain z = g(y). The composite function formed in
this way from general ƒ and g may be written as

𝑔𝑜𝑓: 𝑋 → 𝑍 i.e. x→ 𝑔(𝑓(𝑥)).

Inverse of a function: Let f be a bijection from A to B. Then the inverse of f, denoted

𝑓−1, is the function from B to A defined as 𝑓 −1(y) = x iff f(x) = y. No inverse exists
unless f is a bijection
4. Sample Example:
Q (1). Let g be the function from the set {a, b, c} to itself such that g(a) = b, g(b) = c, and
g(c) = a. Let f be the function from the set {a, b, c} to the set {1, 2, 3} such that f (a) = 3,
f(b)= 2, and f (c) = 1. What is the composition of f and g, and what is the composition of
g and f ?
Solution: The composition f ◦ g is defined by (f ◦ g)(a) = f (g(a)) = f (b) = 2,
(f ◦ g) (b) = f (g(b)) = f (c) = 1, and (f ◦ g)(c) = f (g(c)) = f (a) = 3.

Note that g ◦ f is not defined, because the range of f is not a subset of the domain of g.

Q (2). Let f and g be the functions from the set of integers to the set of integers defined
By f (x) = 2x + 3 and g(x) = 3x + 2. What is the composition of f and g? What is the
Composition of g and f ?
Solution:
Both the compositions f ◦ g and g ◦ f are defined. Moreover,

(f ◦ g)(x) = f (g(x)) = f (3x + 2) = 2(3x + 2) + 3 = 6x + 7

and

(g ◦ f )(x) = g(f (x)) = g(2x + 3) = 3(2x + 3) + 2 = 6x + 11.

Q (3) Let f : Z → Z be such that f (x) = x + 1. Is f invertible, and if it is, what is its
inverse?
Solution: The function f has an inverse because it is a one-to-one correspondence, as
.To reverse the correspondence, suppose that y is the
image of x, so that y = x + 1. Then x = y − 1. This means that y − 1 is the unique element
of Z that is sent to y by f . Consequently, f -1(y) = y − 1.
Exercise 13

1. Let f: A→B and g: B→A verify that g=f-1 where A=B=set of Real numbers and
f(a)=𝑎+1 and g(b)=2b-1.
2

35
 Mathematics – III (COMP)
2. Let f be a function from A to b. Find f-1
(i) where A= {x: x is real and x≥ -1}; B= {x : x is real and x≥0} ; and f(a)=√𝑎 + 1
(ii) where A=B=R: f(a)=a3+1
3. Let f(x,y)=(2x-y,x-2y) ,(x,y)R X R ,Show that f is one to one and find Inverse of F.
4. Let A=B=C=R and let f: A→B, g: B→C. Defined by f(a)=a+1 and g(b)=b2+2 find
(a) (gof) (-2) (b) (fog)(-2) (c) (gof)(x) (d) (fog)(x)
Let’s check the takeaway from lecture
1. If f is a function defined from R to R, is given by f(x) = 3x – 5 then f –1(x) is given by

(a) 1/(3x-5) (b) (x+5)/3 (c) does not exist since it is not a bijection (d) none of the
Mentioned
2. For an inverse to exist it is necessary that a function should be
(a) injection (b) bijection (c) surjection (d) none of the mentioned

Homework Problems for the day

1. Let A=B=C=R and let f: A→b, g: B→ c be defined by f(a)=a-1 and g(b)=b2 then find
(i) (fog) (2) (ii) (gof)(2) (iii) (gof) (x) (iv) (fog)(x)
2. Let f(n) be the number of divisors of n, nZ+. Determine whether f is one to one or
onto (or both or neither).
3. Let A=B=C=R and consider the function f: A→B and g: B→ C defined by f(a)=2a+1,
g(b)=b/3. Verify the theorem that (gof) -1=f-1og-1.
4. Let f: A→ B and g:B→ C be functions . Show that if gof is one -one then f is one one.
5. If A set has ‘n’ element, then how many bijections are there from A to A.
Generating Function

Lecture: 14
1. Learning objective: Students shall be able to understand the concept of Generating function.
2. Introduction: We introduce an alternative way to represent Numeric function. For a
numeric function (a 0, a1 ,a2…ar…) we define an infinite series a0+a1 Z+a2 z 2+a3
z3+…+arzr+.. which is called Generating function of a numeric function of a.
3. Definition and Formulae:
(i) The generating function for the sequence a0, a1,…, ak, … of real numbers is
the infinite series 𝑘=0 G(x)=a0+a1x+ . . .+ak
xk +. . . =∑∞ 𝑎kxk
⚫ Generating functions for finite sequences of real numbers can be defined by extending
a finite sequence a0,a1, … , an into an infinite sequence by setting an+1 = 0, an+2 =
0, and so on.
⚫ The generating function G(x) of this infinite sequence {an} is a polynomial of degree n
because no terms of the form ajxj with j > n occur, that is,

37
SE Semester III-CBCGS HME 2023-24

G(x) = a0 + a1x + ⋯ + an xn.

(ii) Let u be a real number and k a nonnegative integer. Then the extended binomial
𝑢
coefficient ( ) is defined by
𝑘
𝑢−𝑘+1
𝑢 𝑢(𝑢 − 1)(𝑢 − 2). . . 𝑖𝑓 𝑘 > 0
( ){ 𝑘!
𝑘 1 𝑖𝑓 𝑘 = 0
4. Sample Example:
Q(1) What is the generating function for the sequence 1,1,1,1,1,1?
Solution: The generating function of 1,1,1,1,1,1 is
1 + x + x2 + x3 + x4 + x5.
since, we have (x6 − 1)/(x −1) = 1 + x + x2 + x3 + x4 + x5
when x ≠ 1.
Consequently G(x) = (x6 − 1)/ (x −1) is the generating function of the sequence.
Q (2) Find the number of solutions of e1 + e2 + e3 = 17, where e1, e2, and e3 are
nonnegative integers with 2 ≤ e1≤ 5, 3 ≤ e2 ≤ 6, and 4 ≤ e3 ≤ 7.
Solution: The number of solutions is the coefficient of x17 in the expansion of
(x2 + x3 + x4 + x5) (x3 + x4 + x5 + x6) (x4 + x5 + x6 + x7).
This follows because a term equal to is obtained in the product by picking a term in the
first sum xe1, a term in the second sum xe2, and a term in the third sum xe3, where
e1 + e2 + e3 = 17.
There are three solutions since the coefficient of x17 in the product is 3.
Exercise: 14
1. Find the generating function of the sequence 1, a, a2, a3, . . . ,

2. In how many ways can eight identical cookies be distributed among three distinct
children if each child receives at least two cookies and no more than four cookies?
4. Find the values of the extended binomial coefficients −2 and 1/2
( ) ( )
3 3
Let’s check the takeaway from lecture

1. What is the sequence depicted by the generating series 4 + 15x2 + 10x3 + 25x5 + 16x6+⋯?

a) 10, 4, 0, 16, 25, … b) 0, 4, 15, 10, 16, 25,… c) 4, 0, 15, 10, 25, 16,… d) 4, 10, 15, 25,…

2. What is the generating function for the sequence 1, 6, 16, 216,….?

38
 Mathematics – III (COMP)

a) (1+6𝑥) c)
𝑥3 b) (1−6𝑥)
1 1 d) 1-6x2
(1−4𝑥)

Homework Problems for the day

39
SE Semester III-CBCGS HME 2023-24

1. Let m be a positive integer. Let ak = mC k for k = 0, 1, 2, . . . , m. What is the generating

function for the sequence a0, a1, . . . , am?

2. Use generating functions to determine the number of ways to insert tokens worth $1,
$2, and $5 into a vending machine to pay for an item that costs r dollars in both the
cases when the order in which the tokens are inserted does not matter and when the
order does matter. (For example, there are two ways to pay for an item that costs $3
when the order in which the tokens are inserted does not matter inserting three $1
tokens or one $1 token and a $2 token. When the order matters, there are three ways:
inserting three $1 tokens, inserting a $1 token and then a $2 token, or inserting a $2 token and
then a $1 token.)

Problems for Self-assessment:

Level 1

1. Let R be the following relation on the set A={1,2,3,4,5}:

R={(1,2),(2,1),(3,4),(4,3),(3,5),(5,3),(4,5),(5,4),(5,5)} draw the diagraph of R.

2. Determine the relation represented by the following matrix is Reflexive, symmetric,

irreflexive, asymmetric, antisymmetric or transitive?

0 1 0 1
1
MR=[ 0 1 1]
0 1 0 0
1 1 0 0

3. On the set of boys is the relationship of friendship is an equivalence relation.

4. Let A= {a, b, c, d} and B= {1,2,3}. Determine whether the relation R from A to B is a
function. If it is a function give its range.
(a) R={(a,3), (b,2) ,(c,1)} (b) R={(a,1), (b,1) ,(c,1) ,(d,1)}
5. If R is the relation whose matrix is
1 0 0 1 1
⎡1 0 1 0 1⎤
MR= 1 1 1 0 0
⎢0 1 1 0 0⎥
[0 0 1 0 1]
(a) Find the reflexive closure of R.
(b) Find the symmetric closure of R.

Level 2
1. Explain whether the Relation R on the set is reflexive, Symmetric or transitive where
R is defined on A= {1,2,3,4,5}=B as aRb if and only if a is multiple of b.
2. Let S be the product set {1,2,3}X {a, b}. How many relations are there on S?

40
 Mathematics – III (COMP)

3. Let f be a function from A= {1,2,3,4} to B={a, b, c, d} Determine whether f-1 is a

function. Where f={(1, a), (2,a) ,(3,c),(4,d)}
4. If a set has ‘n’ element, how many functions are there from a to A?
5. Let f : A→ B and g: B→ C be functions. Show that gof is onto then g is onto.

Level 3
1. Prove or disprove that if a relation r on a set A is transitive and irreflexive, then it is
symmetric.
2. Let a={1,2,3,4} and consider the partition P={{1,2,3},{4}} of A. Find the equivalence
relation R on A determined by P.
3. For the relation whose matrix is follows
1 0 0 0 0 1
⎡0 1 1 0 1 0⎤

MR = 0 0 0 1 0 1
1 0 0 1 0 1
⎢0 0 1 0 1 0⎥
[0 1 0 0 1 1]
Determine whether R is reflexive, irreflexive, symmetric, asymmetric or transitive.
4. Find the Generating function for nCk , ak .
5. Find the generating function of ak.

Digital references:

1) [Link]
2) [Link]
Learning Outcomes:
1. Know: Student should be able to know
a) Relations
b) Function
c) Generating function.
2. Comprehend: Student should be able to comprehend concept of Relation, Function and
Generating function.
3. Apply, analyze and synthesize: Student should be able to Apply Relation, Function and
Generating Function to solve the problems.
Add to Knowledge: A function in very abstract terms can be thought of as something that
will take an input and produce an output. It depends on the function what kind of input it
will take and what output it will give. But, to imagine, It can be thought of as a machine or a
box which gives an output for a particular value of the input. So, where should one look for it
in day to day lives? It can be seen anywhere, for example, Weatherman takes a reading from
the thermometer. The thermometer usually gives a reading in Celsius or Fahrenheit. The
weatherman then converts it using some formula. That formula can be thought of as
39
something which resides in the “Function Machine” box given in the figure above. It takes
input temperature in degree Celsius and converts it into Fahrenheit. Now, can one reading of
degree celsius give us two different temperature outputs in Fahrenheit? No. That’s why a rule
is put on the function machine that it cannot give two outputs on taking one input.
SE Semester III-CBCGS HME 2021-22

Self-Assessment

Name of student: Class &Div: Roll No:

1. Are you able to distinguish the different types of relations and functions?
(a) Yes (b) No

2. Are you able to find the composition of relations and functions?

(a) Yes (b) No

3. Do you understand the difference between compositions of relations and functions?

(a) Yes (b) No

4. Will you able to solve the pictorial representation of relation, properties of relation,
partial ordering relation?
(a) Yes (b) No

5. Are you able to find the difference relations and functions and recursively defined
functions?
(a) Yes (b) No

6. Do you understand this module?

(a) Fully understood (b) Partially understood (c) Not at all

40
 Mathematics – III (COMP)

Module 3
Partially Ordered Set(POSET)
1. Motivation: Poset is a branch of mathematical logic that studies sets, which informally are
collections of objects. The language of POset can be used in the definitions of nearly all
mathematical objects. Sets are important everywhere in mathematics because every field of
mathematics uses or refers them in some way. They are important for building more complex
mathematical structure.

2. Syllabus:

Module Content Duration Self- weightage

Units study
duration

3 Posets, Hasse Diagram, chain , Upper 7 10 18-20

bounds, Lower bounds, GLB & LUB of
sets, Definition & properties of Lattice,
sublattice Distributive& modular
Lattices, complemented & bounded
Lattices , Complete lattices.
3. Prerequisite: Basics of relation and function.

4. Learning Objective:
1. Student shall be able to understand the concept of Partially ordered set.
2. Student shall be able to know different types of relations and to identify Poset & draw
Hasse Diagram.
3. Student shall be able to learn pictorial presentation of relation from Hasse diagram
4. Student shall be able to understand chain and draw chain.
5. Students shall be able to understand the lattice
6. Students shall be able to understand the concept of Boolean algebra
Posets, Hasse Diagram, chain

Lecture 15
1. Learning Objective: students shall be able to understand the concept of Poset, Hasse
diagram and chain.

2. Introduction: The concept of ordering does not exist in the theory of sets but if we want
to induct the concept of ordering in a set. This is possible by introducing the concept of
partial ordering on a set.

3. Definition /Formulae:
43
SE Semester III-CBCGS HME 2021-22
(i) Partial Ordering Relation: A relation R on a set is called a partial ordering or partial
order if it is reflexive, antisymmetric and transitive.
(ii) (a) Antisymmetric Relation: A relation R on a set is called antisymmetric if whenever

aRb and bRa then a=b.

Remark: A relation is antisymmetric if a≠b then aRb or bRa.

(iii) Partial Order Set (PO Set) : A set together with a partial ordering R is called a partially
ordered se, or poset and it is denoted by (S,R) or (S,≤). Members of S are called element of
the poset.

Remark: The symbol ≤ is used to denote the relation in any PO set.

(iv) Hasse Diagrams: Definition: A Hasse diagram is a visual representation of a partial

ordering that leaves out edges that must be present because of the reflexive and transitive
properties

A partial ordering is shown in (a) of the figure above. The loops due to the reflexive
property are deleted in (b). The edges that must be present due to the transitive property
are deleted in (c). The Hasse diagram for the partial ordering (a), is depicted in (c).

(v) Procedure for Constructing a Hasse Diagram

To represent a finite PO set (S, ≼) using a Hasse diagram, start with the directed graph of
the relation:

 Remove the loops (a, a) present at every vertex due to the reflexive property.

 Remove all edges (x, y) for which there is an element z ∈ S such that x ≺ z and z ≺ y.
These are the edges that must be present due to the transitive property.

 Arrange each edge so that its initial vertex is below the terminal vertex. Remove all the
arrows because all edges point upwards toward their terminal vertex.

44
 Mathematics – III (COMP)
Remark: The graphical representation of a partial ordering relation in which all arrowheads are
understood to be pointing upward is called the Hasse diagram of the relation.

Remark: The word ordering implies that the objects in the set are ordered according to
some properties or criteria.

4. Sample Example:

Q 1: Show that the “greater than or equal” relation (≥) is a partial ordering on the set of
integers. Is (Z, ≥) PO set?
Solution: To check relation ≥ is partial ordering and (Z, ≥) PO set.
a) Reflexivity: a≥a for every integer.
b) Anti Symmetric: If a≥b and b≥a then a=b.
c) Transitivity: If If a≥b and b≥c then a≥c.
Thus ≥ is a partial ordering relation and hence (Z, ≥) is PO set.

Q 2: Let A = {1, 3, 9, 18} and R is the relation ‘≤’. Prove that (A, ≤) is PO set and draw Hesse
diagram.

Solution: Here R = { (1,1),(1,3),(1,9),(1,18), 3,3), (3,9),(3,18),(9,9), (9,18), (18,18)}.

Exercise 15

1. Show that the inclusion relation (⊆) is a partial ordering on the power set of a set S. Is
(P(A), ⊆) PO set?
2. Determine whether the relation R is a partial order on set A.
(i) A=Z and aRb iff a=2b.
(ii) A=Z and aRb if and only if b2│a

3. Let A = {1,2,3,4} and R = {(1,1), (2,2), (3,3),(4,4), (1,3), (1,4), (2,3), (2,4), (3,4)}. draw its

Hasse diagram.

4. Let A = {1,2,3,4,12}. Draw Hasse diagram of (A, │).

5. Let A = {1,2,3,4,6,8}. Draw Hasse diagram of (A, │).

6. Let A = {1,2,3,4,6,8,12}. Draw Hasse diagram of (A, │).

Let’s check the takeaway from lecture

45
SE Semester III-CBCGS HME 2021-22

1. Let a set S = {2, 4, 8, 16, 32} and ≤ be the partial order defined by aRb, if a divides b.
Number of edges in the Hasse diagram of is

a) 6 b) 5 c) 9 d) 4

2. The Relation < on Z+ is not a partial order as it is not

a) Not reflexive b) Not antisymmetric c) Not transitive d) Nonsymmetric

Homework problem for the Day

1. Determine whether the relation R is a partial order on the set A

(i) A=Z and aRb if and only if a=bk for some k∈Z+. Note that k depends on a and b

(ii) A=R and aRb if and only if a≤b.

2. Draw the Hasse diagram of D36, where D36 is set of divisors of 36.

3. Determine the Hasse diagram of the relation on A= {1,2,3,4,5} whose matrix is shown as

1 1 1 1 1
⎡0 1 1 1 1⎤
MR= 0 0 1 1 1
⎢0 0 0 1 1⎥
[0 0 0 0 1]

4. Let B= {2,3,6,9,12,18,24} and let A=B X B. Define the following relation on A: (a, b) <(a’,b’)
if and only if a│a’ and b ≤ b’ ,where ≤ is the usual partial order. Show that < is a partial
order.

Upper Bound and Lower Bound

Lecture 16
1. Learning Objective: students shall be able to understand the concept of Upper bound
and lower bound in a poset.

2. Introduction: Certain elements of a poset are of special importance for many properties and
applications of poset. when order or defined on the elements of a set. It raises the question
of greatest element and least element of a set. The concept of greatest and least element leads
to upper bound and lower bound of a poset.
3. Definition /Formulae:

(i) Comparability: The element a and b of a PO set (S, ≤) are comparable if either a≤b or
b≤a. When a and b are elements of S so that neither a ≰ b or b ≰ a. then a and b are called
incomparable.

46
 Mathematics – III (COMP)

(ii) Totally ordered set/ Chain: If (S, ≤) is a PO set and every two elements of S are
comparable, S is called a totally ordered or linearly ordered set, and ≤ is called a total order
or a linear order. A totally ordered set is called a chain.

(iii) Well, ordered: (S, ≤) is a well-ordered set if it is PO set such that ≤ is a totally ordering
and every nonempty subset of S has a least element.

(iv) Maximal Element: Let (A, ≤) be a PO set and a ϵ A . Then the element a is said to be
maximal element of A if there is no b such that a ≤ b. In other words, if in a PO set an element
is not related to any other element.

(v) Minimal Element: Let (A, ≤) be a PO set and a ϵ A. Then the element a is said to be
minimal element of A if there is no b such that b ≤ a. In other words, if in a PO set no element
is related to an element.

(vi) Maximum Element (Greatest Element): Let (A, ≤ ) be a PO set and a ϵ A . Then the
element a is said to be maximum element of A if x ≤ a , for all x ϵ A. In other words, if it is a
maximal element and every element is related to it.

(vii) Minimum Element (Least Element): Let (A, ≤ ) be a PO set and a ϵ A . Then the
element a is said to be minimum element of A if a ≤ x, for all x ϵ A. In other words, if it is a
minimal element and it is related to every element in a PO set.

(viii) Upper Bound (w.r.t subset): Let (A, ≤) be a PO set and B ⊂ A. An element x ϵ A is an upper
bound of B if y≤x for all y in B.

(ix) Lower Bound (w.r.t subset): Let (A, ≤) be a PO set and B ⊂ A. An element x ϵ A is an upper
bound of B if x ≤y for all y in B.

(x) Least Upper Bound (w.r.t subset): Let (A, ≤) be a PO set and B ⊂ A. An element a ϵ A is
a least upper bound of B if it is an upper bound of B such that a≤a whenever a is the upper bound
of B.

(xi) Greatest Lower Bound (w.r.t subset): Let (A, ≤) be a PO set and B ⊂ A. An element a ϵ
A is a greatest lower bound of B if it is a lower bound of B such that a≤a whenever a is the lower
bound of B.

4. Sample Example:

Q 1: Consider the Poset A={a, b ,c ,d ,e ,f ,g ,h} ,whose Hasse diagram is shown in the figure
below .Find all upper and lower bound s of the following subset of A : (a) B1={a ,b } ; (b)
B2={c ,d ,e}

g
f
47
SE Semester III-CBCGS HME 2021-22

d e
c

a b

Solution: (a) B1 has no lower bound, its upper bounds are c , d ,e ,f ,g and h.

(b) The upper bound of B2 are f , g ,f and h ; its lower bounds are c ,a and b.

Q 2: In the above example with the subset B1 and B2 as defined in the example. Find all least
upper bounds and all greatest lower bounds of (A) B 1 ; (b) B2 .

Solution: (a) Since B1 has no lower bounds, so it has no greatest lower bound. However
LUB(B1)= c.

(b) Since the lower bounds of B 2 are c ,a ,and b we find that GLB (B 2 )=c .The upper bound
of B2 are f ,g and h . since f and g are not comparable, we conclude that B 2 has no least upper
bound.

Exercise 16

1. A= {x: x is a real number and 0≤x<1 } with usual partial order ≤. Then find its all minimal
and maximal Elements.
2. Find all the minimal and maximal elements of A= {2 ,3 ,4 ,6 ,8 ,24 ,48} with partial order
of divisibility.

3. Prove that a poset Has at most one greatest element and at most one least element.

4. Prove that if (A, ≤) has greatest element then it is unique.

5. Determine the Greatest and least element of the following set if it exist
f e
(i) (ii) (iii) 5

d e d 4
c

b c 2 3

a a b 1

Let’s check the takeaway from lecture

1. Let s={a ,b ,c} be a set and P(s) be the power set of S and Poset is defined as (P(s),⊆) then
the least element of it ?

(a) {a} (b) {b} (c) {c} (d) 𝜙

48
 Mathematics – III (COMP)

2. Let A be the poset of nonnegative real numbers with usual partial order ≤. Then maximal
element of it

(a) 100 (b) 5000 (c) 99 (d) does not exist

Homework problem for the Day

1. Find the maximal and minimal element of the poset

2. Find the maximal and minimal element of the poset

3. Prove that if (A, ≤ ) has the least element then it is unique.

4. find the greatest and least element from the partial ordered set on A={2 ,3 ,4 ,6 ,12 ,18 ,24
,36} with partial order of divisibility.

Lattice
Lecture 17
1. Learning Objective: students shall be able to understand the concept of Lattice.
2. Introduction: A poset when becomes more concrete it generates the structure of lattice. It
is quite similar like the structure of the lattice

3. Definition /Formulae/ Notation:

(i) Join: lub or join or V. In other words, least among all upper bounds

(ii) Meet: glb or mert or ∧. In other words, greatest among all lower bounds.

(iii) Join Semi Lattice: (lub or V) For every pair of elements lub or join exists then PO set is
called joint Semilattice.

(iv) Meet Semi Lattice : (glb or ∧) For every pair of elements lub or join exists then PO set is
called joint Semilattice.

49
SE Semester III-CBCGS HME 2021-22

(v) Lattice: If a PO set is both joint and meet semilattice then it is called lattice. T hus lattice
is 1. PO set (set L, ≤) 2. 0 element is 0 ≤ x, for every in L 3. I element x ≤ I, for every in L.

(vi) Finite and infinite Lattice: Lattice can be finite as well as infinite (L, V, ∧). The number
of elements are finite then it is finite lattice otherwise infinite lattice.

(vii) Dn: It is a set of all positive integers less then n and divides n.

4. Sample Example:

Q 1: From the Hasse diagram of the PO set prove that the poset is lattice or not
i
h
g

e f
d

b c

a
Solution: Let us find the joint and meet of every pair of elements

∨ a b c d e f g h i

a a b c d e f g h i

b b b e d e h g h i

c c e c g e f g h i

d d d g d g i g i I

e e e e g e h g h I

f f h f i h f i h I

g g g g g g g i i I

h h h h i h h i h I

i i i i i i i i i i

∧ a b c d e f g h i

50
 Mathematics – III (COMP)

a a a a a a a a a a

b a b a b b a b b b

c a a c a c c c c c

d a b a d b a d b d

e a b c b e c e e e

f a a c a c f c f f

g a b c d e c g e g

h a b c b e f e h h

i a b c d e f g h i

Since for every pair of points there exist joint and meet hence the above poset is the lattice.

Exercise 17

1. Determine whether the following Hasse diagrame is lattice or not

e g
(i) f (ii)

e f
d
d
c
b c
b
a
a
2. Prove that D30 is a lattice.

3. If L is a lattice then prove that

(a) a∨ (b∨ 𝐶)= (a∨ b)∨ c

(b) a∧ (b ∧ c)= (a ∧ b) ∧ c

Let’s check the takeaway from lecture

1. In the poset (Z+, |) (where Z+ is the set of all positive integers and | is the divides

relation) are the integers 9 and 351 comparable

51
SE Semester III-CBCGS HME 2021-22

a) comparable b) not comparable c) comparable but not determined d) determined but

not comparable

2. If every two elements of a poset are comparable then the poset is called

a) sub ordered poset b) totally ordered poset c) sub lattice d) semigroup

Homework problem for the Day

1. Determine that the following Hasse diagrame represent a lattice?

(i) g (ii) g

e f h f

d d e

b c c

a a b

2. Let L be a lattice. Then for every a , b and c in L Then prove that

(i) If a≤ b the aV c ≤ b V c

(ii) a∧ c ≤ b∧ c

(iii) a≤ c and b≤ c if and only if a V b≤ c.

Sub Lattice, Distributive lattice

Lecture 18
1. Learning Objective: students shall be able to understand the concept of Sublattice,
distributive lattice.

2. Introduction: Sub lattice is the concept which shows that one part of the lattice also can
be following all the properties of lattice. It leads to the concept of different kind of lattice.

3. Definition:
(i) Dual in Lattice: The dual of any statement in a lattice (L, V, ∧) is defined to be the
statement obtained by interchanging V & ∧.

(ii) Sublattice: Let (L , ≤) be a lattice. A non-empty Subset S of L is called a sublattice if for each
a ∈ S and b ∈ S, ( a V b)∈S and ( a ∧b) )∈S. In other words, if S is a nonempty subset of a
lattice L such that every pair of (a , b) of two elements of S has a join and meet then S is
called a sublattice.

52
 Mathematics – III (COMP)

(iii) Bounded Lattice: A lattice is bounded if it has a greatest element (I) and least element
(0).

(iv) Compliment of a element in a Lattice: Let, (L, V, ∧) be a bounded lattice with 0 & I as
least and greatest elements, For any a, b ∈L. If a, V b= I and a ∧b=0 then a and b are called
compliment of each other. Every element of lattice need not have compliment. If compliment
exist, then need not be unique.

(v) Compliment Lattice: A lattice (L, V, ∧) is complimented if every element has at least one
compliment.

(vi) Distributive Lattice: A lattice (L, V, ∧) is Distributive lattice if for all a , b c ∈L we get,

1. a V ( b ∧ c)= ( a V b) ∧ (b V c)
2. a ∧ ( b V c)=:( a ∧b) V (b∧ c)
4. Sample Example:

Q 1. For the given structure answer the following: Is it lattice? , Subset {a, b, c, e} is a

sublattice? , Subset {a, b, c, d} is a sublattice?

Solution: 1. This is not a lattice as joint of d & e does not exist.

2. Subset {a, b, c, e} gives substructure

This subset (sub structure) being lattice, is a sublattice.

3. Subset {a, b, c, d} gives substructure

53
SE Semester III-CBCGS HME 2021-22

This subset (sub structure) being lattice, is a sublattice.

4. Subset {b, c, d, e} gives substructure

This subset is not a lattice as join of d , e does not exist. Hence it is not sublattice.

Exercise 18

1. For the given structure answer the following: 1. Is it lattice? , 2. Subset {x, a, y, b} is a

lattice? , [Link] {x, a, c, y} is a lattice? ,4. Subset {x, c, d, y} is a lattice? ,5. Subset

{x, b, d, y} is a lattice?

2. Let L be bounded distributive lattice. If a complement exists, it is unique.

3. Show that following lattice are not distributive

1 1

a c

c a b

0 0

4. Let L= {a1 , a2 , a3 ...........an} be a finite set .Then L is bounded.

54
 Mathematics – III (COMP)

Let’s check the takeaway from lecture

1. If a lattice has a greatest element and a least element which satisfy 0 ≤ a ≤1 for every a
in the lattice then lattice L is
a) semilattice b) join semilattice c) meet semilattice d) bounded lattice
2. If every two elements of a poset are comparable then the poset is called
a) sub ordered poset b) totally ordered poset c) sub lattice d) semigroup
Homework problem for the Day

1. Show that a sublattice of a distributive lattice is distributive.

2. Find all the sublattice of D24 that contain at least five elements

3. Show that a subset of a linearly ordered poset is a sublattice.

4. Fond the complement of each element in the Hasse diagram

b c

Boolean Algebra
Lecture 19
1. Learning Objective: students shall be able to understand the concept of Boolean algebra.

2. Introduction: There are certain type of lattice which are important for computer science and
its applications. These lattices are known as Boolean lattice, and it leads to an algebraic structure
which is called Boolean algebra.
3. Definition:

(i) Boolean Lattice: A compliment and distributive lattice (L, ∨ , ∧) is called Boolean Lattice.

(ii) Boolean Algebra: An algebraic structure (L, ∨, ∧,-,0,I) defined by the Boolean lattice is
called Boolean Algebra.

(iii) Every element in a Boolean lattice has a unique compliment. Unary binary operation is
referred as a complementation operation and denoted by ‘-’.

4. Sample Example:

55
SE Semester III-CBCGS HME 2021-22

Q 1: Let L be a distributive lattice show that if there exist an element a if 𝑎 ∧ 𝑥 = 𝑎 ∧ 𝑦 and

𝑎 ∨ 𝑥 = 𝑎 ∨ 𝑦 then x=y.

Solution: x=x ∨ (𝒙 ∧ 𝒂)

=(𝒙 ∨ 𝒙 ) ∧ (𝒙 ∨ 𝒂)

=x∧ (𝒙 ∨ 𝒂)

= x∧ (𝒂 ∨ 𝒙)

=𝒙 ∧ (𝒂 ∨ 𝒚)=(𝒙 ∧ 𝒂) ∨ (𝒙 ∧ 𝒚) = (𝒂 ∧ 𝒙) ∨ (𝒙 ∧ 𝒚) = (𝒂 ∧ 𝒚) ∨ (𝒙 ∧ 𝒚)

=(𝒂 ∧ 𝒙 ) ∨ 𝒚 = (𝒂 ∧ 𝒚) ∨ 𝒚 = 𝒚

Exercise 19

1. Determine whether the following poset is Boolean algebra

(i) f (ii) g (iii) h

d e e f f e g

b c d b d c

b c

a a a

2. Are there are any Boolean algebra having three elements why or why not.

3. Show that in a Boolean algebra for any a and b ,a ≤ b if and only if b’≤ a’.

4. Show that in a Boolean algebra for any a and b ,

(𝑎 ∧ 𝑏) ∨ (𝑎 ∧ 𝑏′) = 𝑎

Let’s check the takeaway from lecture

1. In Boolean algebra, the OR operation is performed by which properties?

a) Associative properties b) Commutative properties c) Distributive properties

d) All of the Mentioned

2. The involution of A is equal to

a) A b) A’ c) 1 d) 0
56
 Mathematics – III (COMP)

Homework problem for the Day

1. Show that in a Boolean algebra ,for any a and b ,a=b if and only if (𝑎 ∧ 𝑏′) ∨ (𝑎′ ∧ 𝑏) = 0

2. Show that in a Boolean algebra for any a , b and c ,if a ≤ b then (𝑎 ∧ 𝑐) ≤ (𝑏 ∧ 𝑐).

3. Show that in a Boolean Algebra for any a and b 𝑏 ∧ (𝑎 ∨ (𝑎′ ∧ (𝑏 ∨ 𝑏′))) = 𝑏 .

4. Show that in a Boolean algebra for any a , b and c if a≤ b then 𝑎 ∨ (𝑏 ∧ 𝑐) = 𝑏 ∧ (𝑎 ∨ 𝑐).

Problems for Self-assessment:

Level 1

1. Determine the Hasse diagrame of the relation on A={1 ,2 ,3 ,4 ,5} whose matrix is
shown as .

1 0 1 1 1
⎡0 1 1 1 1⎤
MR= 0 0 1 1 1
⎢0 0 0 1 0⎥
[0 0 0 0 1]

2. Determine whether the relation R is a Linear order on the set A where A=R and aRb
if and only if a≤ b.
3. Find the minimal Elements of The Poset
4 5

1 2

.
4. Prove that any linear order is distributive lattice.
5. Is the following lattice is Boolean algebra or not?

b c

57
SE Semester III-CBCGS HME 2021-22

Level 2
1. Let A={ 2,4,6,8,12,18,24,36,72} with partial order of divisibility. Draw its Hasse
diagram.
2. Give an example of partial on A={a ,b ,c ,d ,e} that has two maximal element and has
no least element.
3. Let A= {a ,b ,c ,d ,e ,f ,g ,h} and R is the Relation defined as follows

1 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 1 0 0 0 0⎥
MR= ⎢
⎢1 1 1 1 1 1 1 1⎥
⎢0 1 0 1 0 1 0 1⎥
⎢0 0 1 1 0 0 1 1⎥
[0 0 0 1 0 0 0 1]

Show that (A, R) is a poset.

4. Show that Sublattice of a distributive lattice is distributive.

5. Prove that in a lattice L then
(i) 𝑎 ∨ (𝑎 ∧ 𝑏) = 𝑎 (𝑖𝑖) 𝑎 ∧ (𝑎 ∨ 𝑏) = 𝑎

Level 3
1. Find all upper bound of B and all the lower bound of B ,the least upper bound of B
and greatest lower bound of B={3 ,4 ,6}
5 8

4 6 9

3 7

1 2

2. Let A= {2,3,4 . . . , 100 } with partial order of divisibility .How many maximal elements
does ( A ,≤ ) have ?, Give a subset of A that is a linear order under divisibility and is as
large as possible.
3. Prove that if a and b are the elements in a bounded, distributive lattice and if a has a
complement a’ then
(i) 𝑎 ∨ (𝑎′ ∧ 𝑏) = 𝑎 ∨ 𝑏 (𝑖𝑖) 𝑎 ∧ (𝑎′ ∨ 𝑏) = 𝑎 ∧ 𝑏
4. Let n=p1 .p2 . . . pk, where the pi are distinct primes. Then Dn is a Boolean algebra.

58
 Mathematics – III (COMP)

5. Show that the lattice whose Hasse diagram is shown as follows is not a Boolean
algebra. I
a f

e d
b c

Digital references:
1) [Link]
2) [Link]

Learning Outcomes:
1. Know: Student should be able to know

a) Partial ordered set

b) Lattices

c) Boolean algebra.

2. Comprehend: Student should be able to comprehend concept of Partial order relation,

Lattices and Boolean algebra

3. Apply, analyze, and synthesize: Student should be able to Apply Partial order relation

, lattices and Boolean algebra.

Add to Knowledge: When a ranking of some objects (chemicals, geographical sites,

river sections, etc.) by a multicriteria analysis is of concern, then it is often
difficult to find a common scale among the criteria, and therefore even the simple
sorting process is performed by applying additional constraints, just to get a
ranking index. However such additional constraints, often arising from normative
considerations, are controversially discussed. The theory of partially ordered sets
and its graphical representation (Hasse diagrams) does not need such additional
information just to sort the objects. Here, the approach of using partially ordered
sets is described by applying it to a battery of tests, developed by Dutka et al. of
this specific test.

59
SE Semester III-CBCGS HME 2021-22

Self-Evaluation

Name of student: Class & Div : Roll No:

1. Are you able to evaluate the different probleams of PO set operation?

(a) Yes (b) No

2.
(a) Yes (b) No

3.
(a) Yes (b) No

4.
(a) Yes (b) No

5.
(a) Fully understood (b) Partially understood (c) Not at all

60
 Mathematics – III (COMP)

Module 4
Graph Theory
1. Introduction: In the last four decades Graph Theory has established itself as a worthwhile
mathematical discipline. The development of many branches in mathematics has been
necessitated while considering certain real-life situations arising in practical life problems
arising in other branches of study. Graph theory also has been independently discovered
many times through some puzzles that are arose from physical world, consideration of
chemical isomers, electrical networks etc. Any real-world situation can be conveniently
represented on a paper by means of a diagram consisting of a set of points or nodes
together with lines or curves joining some or all pairs of these points which is called a
graph. In this module we give the mathematical definition of graph and study some of
graphs and operations on graphs.
2. Syllabus:

Self-study
Module Content Duration Weightage
duration

4 Definitions: graphs, digraphs,

Multigraphs, Paths and cycles
(Hamiltonian and Eulerian) Subgraphs, 09 hours 12 Hours 22 Marks
Isomorphism, Special kinds of graphs:
trees, bipartite graphs, planer graphs,
Graph coloring.

3. Learning Objective:
1. Student shall be able to define Graphs and its terminology.
2. Student shall be able to Know graph models.
3. Student shall be able to learn special types of graphs.
4. Student shall be able to learn to represent Graphs and Graph isomorphism.
5. Student shall be able to learn about Paths and circuits.
6. Student shall be able to identify Euler and Hamiltonian Graphs.
7. Student shall be able to Know tree and Prefix Code.

Graphs, Directed graphs

Lecture: 21
Graphs: A Graph G = (V,E) consist of nonempty set V of Vertices or nodes or points and a
set of E of Edges or curve or line. Each edge has either one or to vertices associated with it is
called its endpoints. An edge is said to be CONNECT its end points.
61
SE Semester III-CBCGS HME 2023-24
Example: This graph is with four vertices and five edges.

Remarks:
 The graphs we study here are unrelated to graph of function studied.
 We have a lot of freedom when we draw a picture of graph. All that matter is the
connection made by the edges not the particular geometry depicted, For example the
lengths of edges whether edges cross how vertices are depicted and so on do not
matter.
 A graph with the infinite vertex set is called an infinite graph. A graph with finite
vertex set is called finite graph.
Some Terminology
 In a simple graph each edge connects two different vertices, and no two edges
connect the same pair of vertices.
 Multigraphs may have multiple edges connecting the same two vertices. When m
different edges connect the vertices u and v we say that {u,v} is an edge with
multiplicity m.
 An edge that connects a vertex to itself is called loop.
 An pseudograph may include loops as well as multiple edges connecting the same
pair of vertices.

Example: This pseudograph has both multiple edges and a loop.

Remark: There is no standard terminology for graph theory. So, it is crucial that you
understand the terminology being used whenever you read material about graphs.
DIRECTED GRAPHS

Definition: A directed graph (or digraph) G = (V, E) consists of a nonempty set V of vertices
(or nodes) and a set E of directed edges (or arcs). Each edge is associated with an ordered pair
62
 Mathematics – III (COMP)

of vertices. The directed edge associated with the ordered pair ( u, v) is said to start at u and
end at v.
Remark: Graphs where the end points of an edge are not ordered are said to be undirected
graphs.
SOME TERMINOLOGY (CONTINUED)
 A simple directed graph has no loops and no multiple edges.
Example:

This is a directed graph with three vertices and four edges.

 A directed multigraph may have multiple directed edges. When there are m directed
edges from the vertex u to the vertex v, we say that ( u, v) is an edge of multiplicity
m.
Example:
In this directed multigraph the multiplicity of ( a, b) is 1 and the multiplicity of ( b, c)
is 2.

Example: Show that the in a simple graph having n vertices, there can be atmost n(n-
1)/2 edges.
Solution: For a given n vertices we can join any two of them to get a simple graph.
n(n 1)
But n vertices can be taken two at time in nC  ways. Hence, we will have at
2
2
most n(n-1)/2 edges.

Exercise 21

1. Can we have a simple graph with 6 vertices and 16 edges.

2. Show that maximum degree of any vertex in a simple graph of n vertices is (n-1).
3. Let G = (V,E) be a graph where V= {v1 ,v2, v3, v4, v5} and
63
SE Semester III-CBCGS HME 2023-24

E = {( v1 ,v2), ( v2 ,v2), ( v2 ,v3), ( v2 ,v5), ( v2 ,v4), ( v4 ,v5)} then draw the graph.
Learning from the topic: Students will be able to understand the concept of Simple
graph.
Lecture: 22
Graph terminology & special types of graphs:
Definition 1. Two vertices u, v in an undirected graph G are called adjacent (or neighbors)
in G if there is an edge e between u and v. Such an edge e is called incident with the vertices u
and v and e is said to connect u and v.
Definition 2. The set of all neighbors of a vertex v of G = (V, E), denoted by N(v), is called
the neighborhood of v. If A is a subset of V, we denote by N(A) the set of all vertices in G that
are adjacent to at least one vertex in A. So,
Definition 3. The degree ( or valency ) of a vertex in a undirected graph is the number of edges
incident with it, except that a loop at a vertex contributes two to the degree of that vertex.
The degree of the vertex v is denoted by deg (v) or d(v).

Remark: (1) Vertex with degree zero is called isolated vertex.

(2) Vertex with degree one is called pendant vertex and corresponding edge is
called pendant edge.

Degrees and Neighborhoods of Vertices:

Example: What are the degrees and neighborhoods of the vertices in the graphs G and H?

Solution:

G: deg(a) = 2, deg(b) = deg(c) = deg(f ) = 4, deg(d ) = 1,

deg(e) = 3, deg(g) = 0.
N(a) = {b, f }, N(b) = {a, c, e, f }, N(c) = {b, d, e, f }, N(d) = {c},

N(e) = {b, c , f }, N(f) = {a, b, c, e}, N(g) =  .

H: deg(a) = 4, deg(b) = deg(e) = 6, deg(c) = 1, deg(d) = 5.

64
 Mathematics – III (COMP)

N(a) = {b, d, e}, N(b) = {a, b, c, d, e}, N(c) = {b},

N(d) = {a, b, e}, N(e) = {a, b ,d}.

DEGREES OF VERTICES:
Theorem 1 (Handshaking Lemma): If G = (V, E) is an undirected graph with m edges then
2m  deg(v)
vV

Proof: Each edge contributes twice to the degree count of all vertices. Hence, both the left-
hand and right-hand sides of this equation equal to the twice the number of edges.

Theorem 2: An undirected graph has an even number of vertices of odd degree.

Proof: Let V1 be the vertices of even degree and V2 be the vertices of odd degree in an
undirected graph G = (V, E) with m edges. Then

Exercise 22
1. Find the number of vertices in a simple graph having n edges and having each
vertex of degree 2.
2. Find the number of vertices in a simple graph with exactly 6 edges in which each
vertex is of degree 2
3. Determine the number of edges in a group with 6 nodes, 2 of degree 4 and 4 of
degree 2. Draw such graph.
4. How many edges are there in a graph with 10 vertices of degree six?
5. If a graph has 5 vertices, can each vertex have degree 3?

65
SE Semester III-CBCGS HME 2023-24

Lecture: 23
Directed graphs:

66
 Mathematics – III (COMP)

Recall the definition of a directed graph.

Definition: An directed graph G = (V, E) consists of V, a nonempty set of vertices (or nodes),
and E, a set of directed edges or arcs. Each edge is an ordered pair of vertices. The directed
edge ( u, v ) is said to start at u and end at v.

Definition: Let ( u, v) be an edge in G. Then u is the initial vertex of this edge and is adjacent
to v and v is the terminal (or end) vertex of this edge and is adjacent from u. The initial and
terminal vertices of a loop are the same.

Definition: The in-degree of a vertex v, denoted deg−(v), is the number of edges which
terminate at v. The out-degree of v, denoted deg+(v), is the number of edges with v as their
initial vertex. Note that a loop at a vertex contributes 1 to both the in-degree and the out-
degree of the vertex.
Example: In the graph G we have

deg−(a) = 2, deg−(b) = 2, deg−(c) = 3, deg−(d) = 2, deg−(e) = 3, deg−(f) = 0.

deg+(a) = 4, deg+(b) = 1, deg+(c) = 2, deg+(d) = 2, deg+ (e) = 3, deg+(f) = 0.

Theorem 3: Let G = (V, E) be a graph with directed edges. Then,

Proof: The first sum counts the number of outgoing edges over all vertices and the second
sum counts the number of incoming edges over all vertices. It follows that both sums equal
the number of edges in the graph.

Special types of simple graphs: complete graphs

Definition: A Complete graph on n vertices, denoted by Kn, is the simple graph that contains
exactly one edge between each pair of distinct vertices.

67
SE Semester III-CBCGS HME 2023-24

Remark:

 Complete graph is denoted with number of vertices.

 For a complete graph, Kn degree of each vertex is same and it is n-1.
 Every pair of vertices is adjacent in Kn.
 For Kn total d(v)  n(n 1)
Special types of simple graphs: Regular graphs

Definition: A graph in which every vertex has the same degree is called regular graph. If
the common degree of vertex is r then it is called an r-regular graph of regular graph of degree r.

Observe that all above graphs are regular but not complete except (i). Graph (v) is not
even a simple graph.

Remark:
(1) Complete graph Kn is (n-1) – regular graph.

(2) Every complete graph, is regular but converse is not true.

Special types of simple graphs: cycles and wheels

68
 Mathematics – III (COMP)

A cycle Cn for n ≥ 3 consists of n vertices v1, v2 ,⋯ , vn, and edges {v1, v2}, {v2, v3} ,⋯ , {vn-1, vn},

{vn, v1}.
A wheel Wn is obtained by adding an additional vertex to a cycle Cn for n ≥ 3 and connecting
this new vertex to each of the n vertices in Cn by new edges.

Special types of simple graphs: n-cubes

An n-dimensional hypercube, or n-cube, Qn, is a graph with 2n vertices representing all bit
strings of length n, where there is an edge between two vertices that differ in exactly one bit
position.

Exercise 23

1. Can a complete graph with 8 vertices have 40 edges excluding self loop.
2. If r and n are odd natural number then there cannot be an regular graph of n
vertices.
3. Can we have a raph in which there are 5 vertices and the degree of each vertex is 3.
4. If G= (V,E) is an r-regular graph with n vertices and m edges then m=nr/2.

69
SE Semester III-CBCGS HME 2023-24

Lecture: 24
Connectivity:
Path & circuit:

Definition: An alternating sequence of vertices and edges in a graph in which neither

vertex nor edge is repeated is called a path.

Remark :
(1) When the graph is simple, we denote this path by its vertex sequence x0, x1, … ,
xn (since listing the vertices uniquely determines the path).
(2) The number of edges in a path is called length of a path.

Definition: The path is a Circuit if it begins and ends at the same vertex

(u = v) and has length greater than zero.

Remark : (1) The path or circuit is said to pass through the vertices x1, x2,

… , xn-1 and traverse the edges e1, … , en.

(2) A path or circuit is simple if it does not contain the same edge more than once.

This terminology is readily extended to directed graphs.

Example: In the simple graph here,

– a, d, c, f, e is a simple path of length 4.

– d, e, c, a is not a path because e is not connected to c.

– b, c, f, e, b is a circuit of length 4.

– a, b, e, d, a, b is a path of length 5, but it is not a simple path.

Degrees of separation:

Example: Paths in Acquaintanceship Graphs. In an acquaintanceship graph there is a path

between two people if there is a chain of people linking these people, where two people
adjacent in the chain know one another. In this graph there is a chain of six people linking
Kamini and Ching.

70
 Mathematics – III (COMP)

Some have speculated that almost every pair of people in the world are linked by a small
chain of no more than six, or maybe even, five people. The play Six Degrees of Separation by
John Guare is based on this notion.
Connectedness in Undirected Graphs

Definition: An undirected graph is called connected if there is a path between every pair of
vertices. (or from any vertex to any vertex).

An undirected graph that is not connected is called disconnected.

Remark: We say that we disconnect a graph when we remove vertices or edges, or both, to
produce a disconnected subgraph.

Example: G1 is connected because there is a path between any pair of its vertices, as can be
easily seen. However, G2 is not connected because there is no path between vertices a and
f,

for example.

Connected Components:

71
SE Semester III-CBCGS HME 2023-24

Definition: A connected component of a graph G is a connected subgraph of G that is not a

proper subgraph of another connected subgraph of G. A graph G that is not connected has two
or more connected components that are disjoint and have G as their union.
Remark: In a disconnected graph various connected pieces are called component of the
graph.

Example: The graph H is the union of three disjoint subgraphs H1, H2, and H3, none of
which are proper subgraphs of a larger connected subgraph of G. These three subgraphs
are the connected components of H.

Counting Paths between Vertices

• We can use the adjacency matrix of a graph to find the number of paths between two
vertices in the graph.
Theorem: Let G be a graph with adjacency matrix A with respect to the ordering v1, … , vn
of vertices (with directed or undirected edges, multiple edges and loops allowed). The
number of different paths of length r from vi to vj, where r >0 is a positive integer, equals
the ( i, j) th entry of Ar.
Proof by mathematical induction:

Basis Step: By definition of the adjacency matrix, the number of paths from vi to vj of length
1 is the (i,j)th entry of A.

Inductive Step: For the inductive hypothesis, we assume that that the (i,j)th entry of Ar is the
number of different paths of length r from vi to vj.

– Because Ar+1 = Ar A, the (i,j)th entry of Ar+1 equals bi1a1j + bi2a2j + ⋯ + binanj,
where bik is the (i,k)th entry of Ar. By the inductive hypothesis, bik is the
number of paths of length r from vi to vk.
– A path of length r + 1 from vi to vj is made up of a path of length r from vi to
some vk , and an edge from vk to vj. By the product rule for counting, the
number of such paths is the product of the number of paths of length r from vi

72
 Mathematics – III (COMP)

to vk (i.e., bik ) and the number of edges from from vk to vj (i.e, akj). The sum
over all possible intermediate vertices vk is bi1a1j + bi2a2j + ⋯ + binanj .

Example: How many paths of length four are there from a to d in the graph G

Solution: The adjacency matrix of G (ordering the vertices as a, b, c, d) is given above.

Hence the number of paths of length four from a to d is the (1, 4) th entry of A4 . The eight
paths are as:
a, b, a, b, d a, b, a, c, d a, b, d, b, d a, b, d, c, d
a, c, a, b, d a, c, a, c, d a, c, d, b, d a, c, d, c, d
8 0 0 8
0 8 8 0
A4   
0 8 8 0
 
8 0 0 8


Exercise 24
1. Draw the graph of following matrices as their adjacency matrices

73
SE Semester III-CBCGS HME 2023-24

Lecture: 25

EULER & HAMILTONIAN GRAPHS:

Euler Paths and Circuits:

• The town of Kӧnigsberg, Prussia (now Kalingrad, Russia) was divided into four
sections by the branches of the Pregel river. In the 18th century seven bridges
connected these regions.

• People wondered whether it was possible to follow a path that crosses each bridge
exactly once and returns to the starting point.
• The Swiss mathematician Leonard Euler proved that no such path exists. This result
is often considered to be the first theorem ever proved in graph theory.

Definition: An Euler path in G is a simple path containing every edge of G.

Remark : For Euler path each edge exactly once but vertex may repeated.

Definition: An Euler circuit in a graph G is a simple circuit containing every edge of G.

Remark : Euler path that is a circuit is Euler circuit..

Example: Which of the undirected graphs G1, G2, and G3 has a Euler circuit? Of those that
do not, which has an Euler path?

Solution: The graph G1 has an Euler circuit (e.g., a, e, c, d, e, b, a) but no Euler path.
The graph G2 has neither an Euler circuit nor path.
74
 Mathematics – III (COMP)

The graph G3 has an Euler path (e.g., a, c, d, e, b, d, a, b) but there is no Euler circuit.
Necessary and sufficient conditions for Euler circuits and paths:
• Definition: A graph that contains an Euler circuit is called Euler graph.
• An Euler circuit begins with a vertex a and continues with an edge incident with a,
say {a, b}. The edge {a, b} contributes one to deg (a).
• Each time the circuit passes through a vertex it contributes two to the vertex’s
degree.
• Finally, the circuit terminates where it started, contributing one to deg (a). Therefore
deg (a) must be even.
• A connected graph is Euler circuit iff all vertices are of even degree.
By the same reasoning, we see that the initial vertex and the final vertex of an Euler path have
odd degree, while every other vertex has even degree. So, a graph with an Euler path has
exactly two vertices of odd degree (and rest all vertices with even degree).
EULER PATHS:
Example:

G1 contains exactly two vertices of odd degree (b and d). Hence it has an Euler path, e.g., d,
a, b, c, d, b.

G2 has exactly two vertices of odd degree (b and d). Hence it has an Euler path, e.g., b, a, g,
f, e, d, c, g, b, c, f, d.

G3 has six vertices of odd degree. Hence, it does not have an Euler path.

Note that G1, G2, G3, are not Euler circuit.

EULER CIRCUITS:
Example:

75
SE Semester III-CBCGS HME 2023-24

G contains all vertices of even degree. Hence it has an Euler circuit. e.g., f, a, b, c, e, d, c, f.
H has also all vertices of even degree. Hence it has an Euler circuit. e.g., e, d, c, e.
Note that none of the above graph is Euler path.
HAMILATONIAN PATHS AND CIRCUITS:

• Euler paths and circuits contained every edge only once. Now we look at paths and
circuits that contain every vertex exactly once.

• William Hamilton invented the Icosian puzzle in 1857. It consisted of a wooden

dodecahedron (with 12 regular pentagons as faces), illustrated in (a), with a peg at
each vertex, labeled with the names of different cities. String was used to used to
plot a circuit visiting 20 cities exactly once
• The graph form of the puzzle is given in (b)

• The solution (a Hamilton circuit) is given here,

HAMILTON PATHS AND CIRCUITS

76
 Mathematics – III (COMP)

Definition: A simple path in a graph G that passes through every vertex exactly once is
called a Hamilton path (Hamiltonian path).

Definition: A simple circuit in a graph G that passes through every vertex exactly once is
called a Hamilton circuit (Hamiltonian circuit).

Definition: A graph G has Hamilton circuit then graph is called a Hamilton graph

Remark : That is, a simple path x0, x1, …, xn-1, xn in the graph G = (V, E) is called a Hamilton
path if V = {x0, x1, … , xn-1, xn } and xi ≠ xj for 0≤ i < j ≤ n, and the simple circuit x0, x1, …, xn-1,
xn, x0 (with n > 0) is a Hamilton circuit if x0, x1, … , xn-1, xn is a Hamilton path.
Remark:

 In Hamiltonian circuit and path, some edges may not be transverse at all.
 There may exist more than one Hamiltonian circuit and path for a given graph.
NECESSARY CONDITIONS FOR HAMILTONIAN CIRCUITS:

• Unlike for an Euler circuit, no simple necessary and sufficient conditions are known
for the existence of a Hamilton circuit.

• However, there are some useful necessary conditions. We describe two of these
now.
Dirac’s Theorem: If G is a simple graph with n ≥ 3 vertices such that the degree of every
vertex in G is ≥ n/2, then G has a Hamilton circuit.

Ore’s Theorem: If G is a simple graph with n ≥ 3 vertices such that deg (u) + deg (v) ≥
n-1 for every pair of nonadjacent vertices, then G has a Hamilton path.
EXAMPLES ON HAMILTON PATHS AND CIRCUITS:
Example: Which of these simple graphs has a Hamilton circuit or, if not, a Hamilton path?

Solution:
G1 has no Hamilton circuit but has path a, b, e, d, c.
G2 has a Hamilton circuit a, b, e, c, d, a and Hamilton path : a, b, e, c, d.
G3 has a Hamilton circuit c, a, b, e, d, c and a Hamilton path c, a, b, e, d.
Remark:

77
SE Semester III-CBCGS HME 2023-24

 In Hamiltonian circuit and path, some edges may not be transverse at all.
 There may exist more than one Hamiltonian circuit and path for a given graph.
 Hamiltonian circuit is always a Hamiltonian path but converse need not be true.

Applications of Hamilton paths and circuits:

• Applications that ask for a path or a circuit that visits each intersection of a city, each
place pipelines intersect in a utility grid, or each node in a communications network
exactly once, can be solved by finding a Hamilton path in the appropriate graph.

• The famous traveling salesperson problem (TSP) asks for the shortest route a traveling
salesperson should take to visit a set of cities. This problem reduces to finding a
Hamilton circuit such that the total sum of the weights of its edges is as small as
possible.
• A family of binary codes, known as Gray codes, which minimize the effect of
transmission errors, correspond to Hamilton circuits in the n-cube Qn. (See the text for
details.)

Examples on Euler & Hamilton paths and circuits:

Example: Give an example of a graph which is

(i) Eulerian And Hamiltonian

(ii) Eulerian but not Hamiltonian

(iii) Hamiltonian but not Eulerian

(iv) Neither Eulerian Nor Hamiltonian

Solution:

Exercise 25

Example: Discuss whether the following graphs have Euler circuit.

78
 Mathematics – III (COMP)

Example: Discuss whether the following graphs have Hamiltonian circuit.

79
SE Semester III-CBCGS HME 2023-24

Lecture: 26
REPRESENTING GRAPHS: ADJACENCY LIST

Definition: An adjacency list can be used to represent a graph with no multiple edges by
specifying the vertices that are adjacent to each vertex of the graph.

Example: (i)

Example: (ii)
80
 Mathematics – III (COMP)

REPRESENTING GRAPHS: ADJACENCY MATRIX

Definition: Suppose that G = (V, E) is a simple graph where |V| = n. Arbitrarily list the
vertices of G as v1, v2, … , vn. The adjacency matrix AG of G, with respect to the listing of
vertices, is the n × n zero-one matrix with 1 as its (i, j)th entry when vi and vj are adjacent,
and 0 as its (i, j)th entry when they are not adjacent.
– In other words, if the graphs adjacency matrix is AG = [aij], then

Example:

The ordering of vertices is a, b, c, d.

The ordering of vertices is a, b, c, d.

When a graph is sparse, that is, it has few edges relatively to the total number of possible
edges, it is much more efficient to represent the graph using an adjacency list than an
adjacency matrix. But for a dense graph, which includes a high percentage of possible
edges, an adjacency matrix is preferable,

Note: The adjacency matrix of a simple graph is symmetric, i.e., aij = aji

Also, since there are no loops, each diagonal entry aij for i = 1, 2, 3, …, n, is 0.
• Adjacency matrices can also be used to represent graphs with loops and multiple
edges.

• A loop at the vertex vi is represented by a 1 at the (i, i) th position of the matrix.

81
SE Semester III-CBCGS HME 2023-24

• When multiple edges connect the same pair of vertices vi and vj, (or if multiple loops
are present at the same vertex), the (i, j)th entry equals the number of edges
connecting the pair of vertices.
Example: We give the adjacency matrix of the pseudograph shown here using the ordering
of vertices a, b, c, d.

• Adjacency matrices can also be used to represent directed graphs. The matrix for a
directed graph G = (V, E) has a 1 in its (i, j) th position if there is an edge from vi to
vj, where v1, v2, … vn is a list of the vertices.

• In other words, if the graphs adjacency matrix is AG = [aij], then

• The adjacency matrix for a directed graph does not have to be

symmetric, because there may not be an edge from vi to vj, when there
is an edge from vj to vi.

• To represent directed multigraphs, the value of aij is the number of

edges connecting vi to vj.
REPRESENTING GRAPHS: INCIDENCE MATRICES

When a graph is Definition: Let G = (V, E) be an undirected graph with vertices where v1,
v2, … vn and edges e1, e2, … em. The incidence matrix with respect to the ordering of V and
E is the n × m matrix M = [mij], where

Example: Simple Graph and Incidence Matrix

82
 Mathematics – III (COMP)

The rows going from top to bottom represent v1 through v5 and the columns going from left
to right represent e1 through e6.
Example: Pseudograph and Incidence Matrix

The rows going from top to bottom represent v1 through v5 and the columns going from left
to right represent e1 through e8.
ISOMORPHISM OF GRAPHS

Definition: The simple graphs G1 = (V1, E1) and G2 = (V2, E2) are isomorphic if there is a
one-to-one and onto function f from V1 to V2 with the property that a and b are adjacent in
G1 if and only if f(a) and f(b) are adjacent in G 2 , for all a and b in V 1 . Such a function f is
called an isomorphism. Two simple graphs that are not isomorphic are called non-
isomorphic.
Example: Show that the graphs G =(V, E) and H = (W, F) are isomorphic

Solution: The function f with f(u1) = v1,f(u2) = v4, f(u3) = v3, and f(u4) = v2 is a one-to-one
correspondence between V and W.

Note: Adjacent vertices in G are u1 and u2, u1 and u3, u2 and u4, and u3 and u4. Each of the
pairs f(u1) = v1 and f(u2) = v4, f(u1) = v1 and f(u3) = v3 , f(u2) = v4 and f(u4) = v2 , and f(u3) = v3
and f(u4) = v2 consists of two adjacent vertices in H.
Remark:

• It is difficult to determine whether two simple graphs are isomorphic using brute
force because there are n! possible one-to-one correspondences between the vertex
sets of two simple graphs with n vertices.
• The best algorithms for determining whether two graphs are isomorphic have
exponential worst case complexity in terms of the number of vertices of the graphs.
83
SE Semester III-CBCGS HME 2023-24

• Sometimes it is not hard to show that two graphs are not isomorphic. We can do so
by finding a property, preserved by isomorphism, that only one of the two graphs
has. Such a property is called graph invariant.
• There are many different useful graph invariants that can be used to distinguish
non-isomorphic graphs, such as the number of vertices, number of edges, and degree
sequence (list of the degrees of the vertices in nonincreasing order).

Exercise 26

1. Example: Determine whether these two graphs are isomorphic

2. Example: Determine whether these two graphs are isomorphic.

Applications of Graph Isomorphism

• The question whether graphs are isomorphic plays an important role in applications
of graph theory. For example,

– chemists use molecular graphs to model chemical compounds. Vertices

represent atoms and edges represent chemical bonds. When a new compound
is synthesized, a database of molecular graphs is checked to determine
whether the graph representing the new compound is isomorphic to the
graph of a compound that this already known.

– Electronic circuits are modeled as graphs in which the vertices represent

components and the edges represent connections between them. Graph
isomorphism is the basis for
• the verification that a particular layout of a circuit corresponds to the
design’s original schematics.
84
 Mathematics – III (COMP)

• determining whether a chip from one vendor includes the intellectual

property of another vendor.

Lecture: 27

SPECIAL TYPES OF GRAPHS & COMPUTER NETWORK ARCHITECTURE

Various special graphs play an important role in the design of computer networks.

• Some local area networks use a star topology, which is a complete bipartite graph K1,n
,as shown in (a). All devices are connected to a central control device.

• Other local networks are based on a ring topology, where each device is connected to
exactly two others using Cn, as illustrated in (b). Messages may be sent around the ring.

• Others, as illustrated in (c), use a Wn – based topology, combining the features of a

star topology and a ring topology.

• Various special graphs also play a role in parallel processing where processors need
to be interconnected as one processor may need the output generated by another.

– The n-dimensional hypercube, or n-cube, Qn, is a common way to connect

processors in parallel, e.g., Intel Hypercube.

– Another common method is the mesh network, illustrated here for 16

processors.

85
SE Semester III-CBCGS HME 2023-24

BIPARTITE GRAPHS

Definition: A simple graph G is bipartite if V can be partitioned into two disjoint subsets V1
and V2 such that every edge connects a vertex in V1 and a vertex in V2. In other words, there
are no edges which connect two vertices in V1 or in V2.

It is not hard to show that an equivalent definition of a bipartite graph is a graph where it is
possible to color the vertices red or blue so that no two adjacent vertices are the same color.

G is bipartite & H is not bipartite

since if we color a red, then the adjacent vertices f and b must both be blue.

Example: Show that C6 is bipartite.

Solution: We can partition the vertex set into V1 = {v1, v3, v5} and V2 = {v2, v4, v6} so that
every edge of C6 connects a vertex in V1 and V2 .

Example: Show that C3 is not bipartite.

Solution: If we divide the vertex set of C3 into two nonempty sets, one of the two must
contain two vertices. But in C3 every vertex is connected to every other vertex. Therefore,
the two vertices in the same partition are connected. Hence, C3 is not bipartite.
COMPLETE BIPARTITE GRAPHS

Definition: A complete bipartite graph Km, n is a graph that has its vertex set partitioned into
two subsets V1 of size m and V2 of size n such that there is an edge from every vertex in V1
to every vertex in V2.
Example: We display four complete bipartite graphs here.

86
 Mathematics – III (COMP)

NEW GRAPHS FROM OLD

Definition: A subgraph of a graph G = (V, E) is a graph (W,F), where W ⊂ V and F ⊂ E.
A subgraph H of G is a proper subgraph of G if H ≠ G.

Example: Here we show K5 and one of its subgraphs.

Definition: Let G = (V, E) be a simple graph. The subgraph induced by a subset W of the
vertex set V is the graph (W,F), where the edge set F contains an edge in E if and only if both
endpoints are in W.

Example: Here we show K5 and the subgraph induced by W = {a,b,c,e}.

87
SE Semester III-CBCGS HME 2023-24

BIPARTITE GRAPHS & MATCHING

• Bipartite graphs are used to model applications that involve matching the elements
of one set to elements in another, for example:

• Job assignments - vertices represent the jobs and the employees, edges link employees
with those jobs they have been trained to do. A common goal is to match jobs to
employees so that the most jobs are done.

 vertices represent the men and the women and edges link a a man and a woman if
they are an acceptable spouse. We may wish to find the largest number of possible
marriages.

NEW GRAPHS FROM OLD (CONTINUED)

Definition: The union of two simple graphs G1 = (V1, E1) and G2 = (V2, E2) is the simple
graph with vertex set V1 ⋃ V2 and edge set E1 ⋃ E2. The union of G1 and G2 is denoted by G1
⋃ G2.

Example:

88
 Mathematics – III (COMP)

Lecture: 28
PLANER GRAPHS

Definition: If it is possible to draw the diagram of a given graph in such a way that no two
edges intersect (except at a vertex) is called a planner graph.
Definition: The diagram of a graph drawn in such a way that no two edges intersect is
called a plan graph.

Examples:

Exercise 28

1. Are the following graphs are planar?

2. Which of the following graphs are planar ?

89
SE Semester III-CBCGS HME 2023-24

Lecture: 29

GRAPH MODELS:
COMPUTER NETWORKS
 When we build a graph model, we use the appropriate type of graph to capture the
important features of the application.
 We illustrate this process using graph models of different types of computer
networks. In all these graph models, the vertices represent data centers, and the
edges represent communication links.
 To model a computer network where we are only concerned whether two data
centers are connected by a communications link, we use a simple graph. This is the
appropriate type of graph when we only care whether two data centers are directly
linked (and not how many links there may be) and all communications links work in
both directions.

90
 Mathematics – III (COMP)

 To model a computer network where we care about the number of links between
data centers, we use a multigraph.

 To model a computer network with diagnostic links at data centers, we use a

GRAPH TERMINOLOGY: Summary

 To understand the structure of a graph and to build a graph model, we ask these
questions:
91
SE Semester III-CBCGS HME 2023-24

 Are the edges of the graph undirected or directed (or both)?

 If the edges are undirected, are multiple edges present that connect the same pair
of vertices? If the edges are directed, are multiple directed edges present?
 Are loops present?

•
Social networks
Communications networks
Software design
Transportation networks

• Graphs can be used to model social structures based on different kinds of

relationships between people or groups.

• In a social network, vertices represent individuals or organizations, and edges

represent relationships between them.

• Useful graph models of social networks include:

– friendship graphs - undirected graphs where two people are connected if they are
friends (in the real world, on Facebook, or in a particular virtual world, and
so on.)

– collaboration graphs - undirected graphs where two people are connected if they
collaborate in a specific way

Influence graphs - directed graphs where there is an edge from one person to another if the
first person can influence the second person

92
 Mathematics – III (COMP)

Example: A friendship graph where two people are connected if they are Facebook friends.

Example: An influence graph

EXAMPLES OF COLLABORATION GRAPHS

• The Hollywood graph models the collaboration of actors in films.
– We represent actors by vertices, and we connect two vertices if the actors they
represent have appeared in the same movie.
– An academic collaboration graph models the collaboration of researchers who
have jointly written a paper in a particular subject.
– We represent researchers in a particular academic discipline using vertices.
– We connect the vertices representing two researchers in this discipline if they
are coauthors of a paper.

TRANSPORTATION GRAPHS
 Graph models are extensively used in the study of transportation networks.
 Airline networks can be modeled using directed multigraphs where

93
SE Semester III-CBCGS HME 2023-24

– airports are represented by vertices

– each flight is represented by a directed edge from the vertex representing

the departure airport to the vertex representing the destination airport

 Road networks can be modeled using graphs where

– vertices represent intersections and edges represent roads.

– undirected edges represent two-way roads and directed edges represent one-
way roads.

SOFTWARE DESIGN APPLICATIONS

• Graph models are extensively used in software design. We will introduce two such
models here; one representing the dependency between the modules of a software
application and the other representing restrictions in the execution of statements in
computer programs.

• When a top-down approach is used to design software, the system is divided into
modules, each performing a specific task.

• We use a module dependency graph to represent the dependency between these

modules. These dependencies need to be understood before coding can be done.

– In a module dependency graph vertices represent software modules and there

is an edge from one module to another if the second module depends on the
first.
Example: The dependencies between the seven modules in the design of a web browser are
represented by this module dependency graph.

94
 Mathematics – III (COMP)

TREE
Definition : A connected graph which does not have a circuit or cycle is called a tree.

Definition : A vertex of degree one is called a terminal node or a leaf.

Definition : A vertex of degree greater than one is called a internal node or branch
node.

Definition : A tree in which exactly one vertex is distinguishable from all vertices is
called a rooted tree, The particular distinguishable vertex is called the root of the tree.

Remark :

(1) A tree is a simple plane graph without loop and multiple edges.

(2) Tree is always bipartite graph.

(3) In a tree we can always find a path joining two vertices and such path is unique. This
is because tree is a connected graph.

(4) A tree must start from a vertex and end at a vertex.

(5) If we add an edge to a tree we will get cycle. If we remove an edge from a tree we
will get disconnected graph.

Definition : A tree in which one and only one vertex has degree two and the remaining
vertices are of degree one or three is called a binary tree.

95
SE Semester III-CBCGS HME 2023-24

Definition : If in a binary tree every internal node has exactly two branches it is called a
full binary tree.

Remark : The number of vertices in a binary tree is always odd

Example on prefix coding

Definition : A set of sequences formed from two digits 0 and 1 is called a binary prefix
code.

Remark : using 0 and 1 we can represent a binary tree by binary prefix code and vice
versa. For this we agree to assign 0 to the branch going to the left and 1 to the branch
going to the right.

Example: Write the prefix code of the following tree

Solution: (a) { 00, 10, 010, 111, 0110, 0111, 1100, 1101 }

96
 SE Semester III-CBCGS HME 2023-24

Module 5 Logic

Lecture - 30
5.1. Logic

5.1.1. Motivation: Logic is concerned with all types of reasoning such as valid statements,
mathematical proofs, valid conclusion etc. Logic reasoning is used to prove theorems, to
verify the correctness of computer programs and draw conclusions from experiments.

5.1.2. Syllabus:

Module Content Duration Self study

(in hours) duration
(in hrs)
Introduction, Definition and propositions and logical 3 4
5.1 operations , truth tables equivalence .

5.2 Implication law of logic, Normal Forms, Predicates and 4 8

Quantifiers , Mathematical induction.

5.1.3. Weight age: 18- 21 Marks

[Link]: Logical Operations.

5.1.5. Learning Objective:

Students will be able to...
 learn the concepts & Logical operations
 learn the law of logic
 learn the Normal forms
 learn the Predicates and Quantifiers
 learn Mathematical induction

[Link] Notations:

Symbols Connective Word

~ Not
𝖠 And
∨ Or
⟹ Implies or if…… then
⟺ If and only if, iff

94
 Mathematics – III (CS & E)
[Link] Definitions: )

Symbols Connective Word Symbols

~ Not ~
𝖠 And 𝖠
∨ Or ∨
⟹ Implies or if…… then ⟹
⟺ If and only if, iff ⟺

if p and q are two statements then “ ~q, p∧q, p∨q, p⟹q, p⟺q are all propositions.

5.1.8. Important Formulae/ Tables :

1. Basic logical Operations:

Conjunction: When two or more statement are joined by the connective, denoted by the
symbol”
∧”. The compound statement so formed is called conjunction. If p & q are two statements then
their conjunction p & q written as 𝖠 ∧ 𝖠 is defined in the truth table given below
Truth table p∧ 𝖠
p q 𝑝𝑝𝑝
T T T
T F F
F T F
F F F

Disjunction: When two statement are joined by the connective “𝖠 ∨ 𝖠” the compound statement
so formed is called disjunction and written as 𝖠 ∨ 𝖠”, is defined in truth table given below.

Truth table 𝖠 ∨ 𝖠

p q 𝑝𝑝𝑝
T T T
T F T
F T T
F F F

Negation: If p is the given statement then the negation of p is denoted by “~𝖠"is defined to form
a statement that is true when p is false and false when p is true. The negation of p is read as “not
p”
Truth table ~𝖠
𝖠 ~𝖠
T F
F T

Truth table of double negation ~( ~𝖠)

𝖠 ~𝖠 ~(~𝖠)
T F T

95
 SE Semester III-CBCGS HME 2023-24

Conditional Operator: The conditional statement It “p then q written” as 𝖠 ⇒ 𝖠 is obtained by

combining two statement monks by " If …..then”. The statement which follows “then" is called
Antecedent (or premises) and the statement which follows "then" is called consequent (or
conclusion).

𝖠 ⇒ 𝖠 can be read as follows

(I) p implies q

(II) p is sufficient for q

(III) p only if q

(IV) q is necessary for p

(V) q is consequence of p.
Truth Table for 𝖠 ⇒ 𝖠

p q 𝖠⇒𝖠
T T T
T F F
F T T
F F T

5.1.9 : Examples
Sample Problems:

Write each of the following as conditional sentences in the “If----- then” form

(i) Freezing water expands'

Ans: If water freezes then it expands.

(ii) A racer wins the race only if he runs fast.

Ans: If a racer wins the race then he runs fast

(iii) Roses are vegetables if Carrots are flowers,

Ans. If carrots are flowers then roses are vegetables.

Note : The truth value of Implication is false only if the premises are true but conclusions are

false Converse Statement

96
 Mathematics – III (CS & E)
) formed by
The converse of a given conditional statement 𝖠 ⇒ 𝖠 is a new statement
interchanging the premise p and conclusion q of the given conditional statement If 𝖠 ⇒ 𝖠 then
converse of it is 𝖠
⟹𝖠

Truth Table for converse ( 𝖠 ⇒ 𝖠)

p q 𝖠⇒𝖠 𝖠⇒𝖠

T T T T
T F F T
F T T F
F F T T

Sample Problems:

(1) If there is smoke then there is fire.

Converse statement: If there is fire then there is smoke.

Note: If implication is true then converse may not be true it can be seen from third row of the
above table.

Inverse statement:

If both the premises and conclusion of an implication are negated we get the inverse of that
implication.

Example: If 𝖠 ⇒ 𝖠 then inverse of it is “if not p then not q” and is written as ∼ 𝖠 ⇒∼ 𝖠

Truth Table for inverse

p q ∼𝖠 ∼𝖠 𝖠⇒𝖠 ∼ 𝖠 ⇒∼ 𝖠
T T F F T T
T F F T F T
F T T F T F
F F T T T T

From third row it can be seen that inverse is not true hen implication is true.
Contrapositive: if both the premises and conclusion of the implications are first negated and then
interchanged, we get contrapositive statement of the implication.

If 𝖠 ⇒ 𝖠 then contrapositive is ∼ 𝖠 ⇒∼ 𝖠
Truth table of contrapositive

p q ∼𝖠 ∼𝖠 𝖠⇒𝖠 ∼ 𝖠 ⇒∼ 𝖠
T T F F T T
T F F T F F

97
 SE Semester III-CBCGS HME 2023-24

F T T F T T
F F T T T T

Note: if the implication are true then contrapositive is true and implication is false then
contrapositive is false.

Sample Problems:
Example: If you are good in mathematics then you are good in Science.

Converse of the statement: If you are good in Science then you are good in maths.

Inverse of the statement: If you are not good in maths then you are not good in Science.

Contrapositive of the statement: If you are not put in science then you are not good in maths.

Bi-conditional: A equivalence or a bi-conditional is a compound statement obtained by

combining two simple statement by if and only if. It is denoted by” 𝖠 ⟺ 𝖠" is read as p if
andonly if q.

This statement is true if p and q both are true or false and is false when one of the statement
true and other is false.

Truth table of Bi-conditional

p q 𝖠⟺𝖠
T T T
T F F
F T F
F F T

Logical equivalence: Two statements are said to be logically equivalent if their equivalent is
always true.

Compound Statement: A statement which contains another statement or statements as its

component is called a compound statement .

Example: (1) It is raining and it is cold.

(2) You can have a cakes are you can eat it.

Truth table: The truth value of a compound statement is completely determined by the truth
value of its component .If a statement is true then its truth value is represented by T and if truth
value is false then it is represented by F.

Propositional variable are constant. English alphabets p, q, r, s…. are used to represent simple

98
 Mathematics – III (CS & E)
statement and are called propositional variables. )

Example: p= It is raining.

q= It is cold.

T and F are used to represent true and false statement are called propositional constant.

Negation of compound statement

(1) Negation of conjunction:

∼ (𝖠 𝖠 𝖠) ≡∼ 𝖠 ∨∼ 𝖠

(2) Negation of disjunction

∼ (𝖠 ∨ 𝖠) ≡∼ 𝖠 𝖠∼ 𝖠

(3) Negation of negation

∼(∼ 𝖠) ≡ 𝖠
(4) Negation of implication

∼ (𝖠 ⟹ 𝖠) ≡∼ (∼ 𝖠 ∨ 𝖠) ≡ 𝖠 𝖠∼ 𝖠

(5) Negation of Bi-conditional

∼ (𝖠 ⇔ 𝖠) ≡∼ (∼ 𝖠 ∨ 𝖠) 𝖠 (𝖠 ∨∼ 𝖠) ≡∼ (∼ 𝖠 ∨ 𝖠) ∨∼ (𝖠 ∨∼ 𝖠)

∼ (𝖠 ⇔ 𝖠) ≡ (𝖠 𝖠∼ 𝖠) ∨ (∼ 𝖠 𝖠 𝖠)

Laws of Logic

(a) Idempotent law:

(1) 𝖠 ∨ 𝖠 ≡ 𝖠 (2) 𝖠𝖠𝖠≡𝖠

(b) Commutative law:

(1) 𝖠 ∨ 𝖠 ≡ 𝖠 ∨ 𝖠 (2) 𝖠 𝖠 𝖠 ≡ 𝖠 𝖠 𝖠

(c) Associative law:

(𝖠 𝖠 𝖠) 𝖠 𝖠 ≡ 𝖠 𝖠 (𝖠 𝖠 𝖠) (2) (𝖠 ∨ 𝖠) ∨ 𝖠 ≡ 𝖠 ∨ (𝖠 ∨ 𝖠)

(d) Identity law:

(1) 𝖠 ∨ 𝖠 ≡ 𝖠 (2) 𝖠 𝖠 𝖠 ≡ 𝖠

(e) Involution law :

99
 SE Semester III-CBCGS HME 2023-24
∼ (∼ 𝖠) ≡ 𝖠

(f) Distributive law:

(1) 𝖠 ∨ (𝖠 𝖠 𝖠) ≡ (𝖠 ∨ 𝖠) 𝖠 (𝖠 ∨ 𝖠) (2) 𝖠 𝖠 (𝖠 ∨ 𝖠) ≡ (𝖠 𝖠 𝖠) ∨ (𝖠 𝖠 𝖠)

(g) Inverse law:

(1) 𝖠 ∨∼ 𝖠 ≡ 𝖠 (2) 𝖠 𝖠∼ 𝖠 ≡ 𝖠

(h) De Morgan’s law:

(1) ∼ (𝖠 ∨ 𝖠) ≡∼ 𝖠 𝖠∼ 𝖠 (2) ∼ (𝖠 𝖠 𝖠) ≡∼ 𝖠 ∨∼ 𝖠

Statement form: It is a sequence of symbols containing statement variable such that when
statement variable are replaced by a statement then the result is a statement.
It is of three type.
(i) Tautology

(ii) Contradiction

(iii) Contingency

Tautology: A statement form which is always true for all substitution instance is called a

tautology. Example: By help of truth table we can check that 𝖠 ∨∼ 𝖠 is tautology.

Truth table

𝖠 ∼𝖠 𝖠 ∨∼ 𝖠
T F T
F T T

Contradiction: A statement form which is always flase for all substitution instance is called a
contradiction.

Example: By help of truth table we can check that 𝖠 ∧∼ 𝖠 is contradiction.

Truth table

𝖠 ∼𝖠 𝖠 ∧∼ 𝖠
T F F
F T F

100
 Mathematics – III (CS & E)
) is called contingency.
Contingency: A statement which is neither tautology nor contradiction
So a contingent is sometime true and sometime false depend upon the truth values of
component statements.

Example: By help of truth table we can check that 𝖠 ∨ 𝖠, 𝖠 ∧ 𝖠, ∼ 𝖠 , ∼ 𝖠 are contingency.

𝖠 𝖠 𝖠∨𝖠 𝖠∧𝖠 ∼𝖠 ∼𝖠
T T T T F F
T F T F F T
F T T F T F
F F F F T T

Duality: Two formulae A & A* are said to be duals of each other if either can be obtained from
other by replacing ∨ 𝖠𝖠 ∧ 𝖠𝖠𝖠 ∧ 𝖠𝖠 ∨ .

Example: dual of (𝖠 ∨ 𝖠) ∧ 𝖠 is (𝖠 ∧ 𝖠) ∨ 𝖠.

𝖠 ≡ 𝖠 𝖠ℎ 𝖠𝖠 𝖠∗ ≡ 𝖠∗

So if two statements are equivalence then their dual are also equivalence.

Exercise 30

1) State the Converse, inverse and contrapositive of the following :

(I) It is cold then he wears a hat.

(II) If an integer is multiple of 2 then it is even number.

2) Prove this Equivalence : 𝖠 ≡∼(∼ 𝖠)

3) Prove this Equivalence : 𝖠 ⟹ 𝖠 ≡∼ 𝖠 ∨ 𝖠

4) Prove this Equivalence : 𝖠 ⟺ 𝖠 ≡ (∼ 𝖠 ∨ 𝖠) 𝖠 (∼ 𝖠 ∨ 𝖠)

Let’s check the take away from the lecture

(1) Which of the following is a statement

(a) open the door (b) do your homework

(c) switch on the fan (d) Two plus two is four

(2) If (p ∧ ∼ r ) ⟹ ( q ∨ r ) is false and q and r both false then p is

(a) True (b) False
(c)May be true or false (d) Data insufficient

101
 SE Semester III-CBCGS HME 2023-24
Practice Problems
Using truth tables show that following statement patterns are tautologies.
(1) [(p → q) ∧ ∼q] → (∼p)
(2) [p → (q → r)] ↔ [(p ∧ q) → r]
Using truth tables prove the following logical equivalences:
(1) p ↔ q ≡ (p ∧ q) ∨ (∼p ∧ ∼q)
(2) (p ∧ q) → r ≡ p → (q → r)

Learning from the topic: Students will be able to understand the Mathematical Statements

Normal forms

Lecture – 31

Learning Objective:
1. Student shall be able to learn change of Normal forms.

5.1.10. Normal forms:

Elementary product: A product of variables and their negation is called an elementary

product. Example: 𝖠 𝖠∼ 𝖠, ∼ 𝖠 𝖠∼ 𝖠, ∼ 𝖠 𝖠 𝖠 are elementary product.

Elementary sum: A sum of the variables and their negation is called elementary sum.

Example: 𝖠 ∨ 𝖠, 𝖠 ∨∼ 𝖠, ∼ 𝖠 ∨∼ 𝖠 are elementary sum.

Note: An elementary product is identically false if and only if it contains at least one pair offactor
in which one is negation of other

An elementary sum is identically true if and only if it contain at least one pair of factor in which
one is negation of another.

There are two types of Normal forms:

(i) DNF (Disjunctive Normal form)

(ii) CNF (Conjunctive Normal form)

A) DNF (Disjunctive Normal form): A logical expression is said to be in disjunctive

normalform if it is the sum of the elementary product.

Example: 𝖠 ∨ (𝖠 𝖠 𝖠), 𝖠(∼ 𝖠 𝖠 𝖠) are in DNF. : 𝖠 𝖠 (𝖠 ∨ 𝖠) is not in DNF.

B) CNF (Conjunctive Normal form) : A logical expression is said to be in

Conjunctivenormal form if it is product of the elementary sum.

102
 Mathematics – III (CS & E)
Example: 𝖠 𝖠 (𝖠 ∨ 𝖠), 𝖠 𝖠 (∼ 𝖠 ∨ 𝖠) are in CNF. )

Procedure to obtain DNF/CNF of a given logical expression:

There are three step:

(1) Remove all ⟹ 𝖠𝖠𝖠 ⟺ and by an equivalent expression containing the connective : ∧ ,∨
, ∼ only.

(2) Eliminating ∼ before sum and product by using De Morgan's law .

(3) Apply distributive law until a sum of elementary product is obtained .

Example: Obtain DNF of 𝖠 𝖠 (𝖠 ⟹ 𝖠)

Solution: 𝖠 𝖠 (𝖠 ⟹ 𝖠) ≡ 𝖠 𝖠 (∼ 𝖠 ∨ 𝖠)

≡ (𝖠 𝖠∼ 𝖠) ∨ (𝖠 ∨ 𝖠)

Which is sum of product. So the given expression is in DNF

form Example: Obtain CNF of [𝖠 ∨ (𝖠 𝖠 𝖠)] 𝖠∼ [(𝖠 ∨ 𝖠) 𝖠 𝖠]

Solution: [𝖠 ∨ (𝖠 𝖠 𝖠)] 𝖠∼ [(𝖠 ∨ 𝖠) 𝖠 𝖠]

≡ [𝖠 ∨ (𝖠 𝖠 𝖠)] 𝖠 [∼ (𝖠 ∨ 𝖠) ∨∼ 𝖠]

≡ [(𝖠 ∨ 𝖠) 𝖠 (𝖠 ∨ 𝖠)] 𝖠 [(∼ 𝖠 𝖠∼ 𝖠) ∨∼ 𝖠]

≡ [(𝖠 ∨ 𝖠) 𝖠 (𝖠 ∨ 𝖠)] 𝖠 [(∼ 𝖠 ∨∼ 𝖠) 𝖠 (∼ 𝖠 ∨∼ 𝖠)]

≡ (𝖠 ∨ 𝖠) 𝖠 (𝖠 ∨ 𝖠) 𝖠 (∼ 𝖠 ∨∼ 𝖠)(∼ 𝖠 ∨∼

𝖠) Which is in CNF.

Min terms: Let p and q be two statement variables then 𝖠 𝖠 𝖠, 𝖠 𝖠∼ 𝖠, ∼ 𝖠 𝖠 𝖠, ∼ 𝖠 ∨∼ 𝖠

arecalled min terms of p and q..

Max term: let p and q be to statement variables then 𝖠 ∨ 𝖠, 𝖠 ∨∼ 𝖠, ∼ 𝖠 ∨ 𝖠, ∼ 𝖠 ∨∼ 𝖠 arecalled

max term.

5.1.11. Principal disjunctive Normal Form (PDNF)

Procedure to obtaining PDNF

(i) Obtain a DNF.

(ii) Drop elementary product which are of the type (𝖠 𝖠∼ 𝖠)

(iii) If 𝖠𝖠 𝖠𝖠𝖠 ∼ 𝖠𝖠 are missing in an elementary product 𝖠 then replace 𝖠 by (𝖠 𝖠 𝖠𝖠) ∨(𝖠 𝖠∼
𝖠𝖠).

103
 SE Semester III-CBCGS HME 2023-24
(iv) Repeat step 3 until all elementary product are reduced to sum of min terms. Identical
min terms appearing in DNF are deleted.

NOTE:

PDNF are unique.

Two formulae are equivalent iff their PDNF unique.

If the given proposition is a tautology then its PDNF will contain all possible min-terms of its
component.

Example: Obtain PDNF of ∼ 𝖠 ∨ 𝖠?

Solution: ∼ 𝖠 ∨ 𝖠 ≡ [∼ 𝖠 𝖠 (𝖠 ∨∼ 𝖠) ∨ (𝖠 𝖠 (∼ 𝖠 ∨ 𝖠))]

≡ [(∼ 𝖠 𝖠 𝖠) ∨ (∼ 𝖠 𝖠∼ 𝖠) ∨ (𝖠 𝖠∼ 𝖠) ∨ (𝖠 𝖠 𝖠)]

≡ [(∼ 𝖠 𝖠 𝖠) ∨ (∼ 𝖠 𝖠∼ 𝖠) ∨ (∼ 𝖠 𝖠 𝖠) ∨ (𝖠 𝖠 𝖠)]

≡ (∼ 𝖠 𝖠 𝖠) ∨ (∼ 𝖠 𝖠∼ 𝖠) ∨ (𝖠 𝖠

𝖠) Which is required PDNF.

Principal conjunctive Normal Form (PCNF) :

Procedure to obtaining PCNF

(i) Obtain a CNF.

(ii) Drop elementary sum which are of the type (𝖠 ∨∼ 𝖠) .

(iii) If 𝖠𝖠 𝖠𝖠𝖠 ∼ 𝖠𝖠 are missing in an elementary sum 𝖠 then replace 𝖠 by (𝖠 ∨ 𝖠𝖠) ∧ (𝖠 ∨

∼ 𝖠𝖠).

(iv) Repeat step 3 untill all elementary sum are reduced to product of max terms.
Identicalmax terms appearing in CNF are deleted.

(v) PCNF is unique.

Example: Obtain PCNF of (∼ 𝖠 ⟹ 𝖠) 𝖠 (𝖠 ⟺ 𝖠)

Solution: (∼ 𝖠 ⟹ 𝖠) 𝖠 (𝖠 ⟺ 𝖠)

≡ (∼∼ 𝖠 ∨ 𝖠) 𝖠 (∼ 𝖠 ∨ 𝖠) 𝖠 (∼ 𝖠 ∨ 𝖠)

≡ (𝖠 ∨ 𝖠) 𝖠 (∼ 𝖠 ∨ 𝖠) 𝖠 (∼ 𝖠 ∨ 𝖠)
≡ [(𝖠 𝖠∼ 𝖠) ∨ (𝖠 ∨ 𝖠)] 𝖠 [(∼ 𝖠 ∨ 𝖠) ∨ (𝖠 𝖠∼ 𝖠)] 𝖠 [(∼ 𝖠 ∨ 𝖠) ∨ (𝖠 𝖠∼ 𝖠)

≡ (𝖠 ∨ 𝖠 ∨ 𝖠) 𝖠 (∼ 𝖠 ∨ 𝖠 ∨ 𝖠)(∼ 𝖠 ∨ 𝖠 ∨ 𝖠) 𝖠 (∼ 𝖠 ∨ 𝖠 ∨∼ 𝖠) 𝖠 (𝖠 ∨∼ 𝖠 ∨ 𝖠) 𝖠 (∼ 𝖠 ∨

104
 Mathematics – III (CS & E)
∼ 𝖠 ∨ 𝖠) )

≡ (𝖠 ∨ 𝖠 ∨ 𝖠) 𝖠 (𝖠 ∨∼ 𝖠 ∨ 𝖠) 𝖠 (∼ 𝖠 ∨ 𝖠 ∨ 𝖠) 𝖠 (∼ 𝖠 ∨ 𝖠 ∨ 𝖠) 𝖠 (∼ 𝖠 ∨ 𝖠 ∨∼

𝖠) Which are required PCNF.

5.1.12. Predicates

A part of a declarative sentence describing the properties of an object or relation among objects
is called predicates .

In other words predicate is a variable statement which becomes specific when particular values
are assigned to the variables.

Example: Ram is a good boy. Here

“A good boy” is predicate where

“Ram” is subject.

It can be represented as G(r) where G: a good boy

R: Ram

In other words, a predicate is a word or words in a sentence which express the nature of the
subject.

Example: Every rational number is real number. Here “a real number” is predicate.

The statement x is greater than 3 has two parts. The first part is variable x is subject of the
statement and the second part is predicate “is greater than 3” refers to the property of x it is
denoted by P(x).

P(x) is also said to the value of propositional function P at x. So when we assign the value of x
the P(x) become proposition and has a truth value.

P(x) is called unary predicate.

P(x, y) is called binary predicate.

Example: 𝖠2 + 𝖠2 = 1 is binary predicate.

There are of two types to change predicate (propositional function) into proposition:
(i) Universal quantification

(ii) Existential quantification

105
 SE Semester III-CBCGS HME 2023-24

5.1.13. Universe of discourse

While talking about a set, we need a reference set which we called Universal set U. In the same
way when we talk about all, some, none, etc. we need a reference set which we call Universe of
discourse, represented by UoD.

Example: Some student, Universe of discourse = Set of all students.

(i) Universal quantification: The symbol ∀𝖠 (for all)is used to represent universal quantifier
and represented as

∀𝖠𝖠(𝖠) is read as for all values of x ,P(x) or for every x ,

P(x). Example: 𝖠(𝖠): 𝖠 + 1 > 𝖠

UoD=Set of real numbers Find

Truth value of ∀𝖠𝖠(𝖠).

Solution: Since P(x) is true for all values of x. So ∀𝖠𝖠(𝖠) is true.

5.1.14 Existential quantification: The symbol ∃ (there exist) is used to represent existential
quantifier and read in either of the following ways:

∃ 𝖠 ∈ 𝖠: 𝖠(𝖠) where A is UoD.

∃ 𝖠 𝖠(𝖠) , P(x) is true for some value of A.

Example: P(x): x>3 UoD= Set of Real number.

Find the truth value of ∃ 𝖠 𝖠(𝖠) .

Solution: If x=4 then 4>3. Then truth value of ∃ 𝖠 𝖠(𝖠) is true.

Note : 1

Statement Truth value of P(x) will Truth value of P(x) will be

be true false
∀X 𝖠(𝖠). When P(x) is true for all There is an x for which
value of x. P(x)is false.
∃ 𝖠 𝖠(𝖠) When P(x) is true for some P(x) is false for every x.
value of x.

Note 2: In general, the following logical equivalence holds:

(1) ∀𝖠∀𝖠𝖠(𝖠, 𝖠) = ∀𝖠∀𝖠𝖠(𝖠, 𝖠).

(2) ∃ 𝖠 ∃ 𝖠 𝖠(𝖠, 𝖠) = ∃ 𝖠 ) ∃ 𝖠 𝖠(𝖠, 𝖠)

106
 Mathematics – III (CS & E)
(3) ∃ 𝖠 ∀𝖠 𝖠(𝖠, 𝖠) ≠ ∀𝖠 ∃ 𝖠𝖠(𝖠, )

𝖠) Negation of Quantifier

statement :

Negation of quantified statement changes the quantifier and negates the original statement given
below:

(1) ∼ ∀𝖠 𝖠(𝖠) ≡ ∃ 𝖠 ∼ 𝖠(𝖠)

(2) ∼ ∃ 𝖠 𝖠(𝖠) ≡ ∀𝖠∼ 𝖠(𝖠)

Example: What is the negation of the following statements?

(1) ∀𝖠(𝖠2 > 𝖠) (2) ∃ 𝖠 (𝖠2 = 2)

Solution: (1) The negation of ∀𝖠(𝖠2 >

𝖠) is

∼ ∀𝖠(𝖠2 > 𝖠) ≡ ∃ 𝖠 ∼ (𝖠2 > 𝖠) ≡ ∃ 𝖠 (𝖠2 ≤ 𝖠)

(2) The negation of ∃ 𝖠 (𝖠2 = 2) is

∼ [∃ 𝖠 (𝖠2 = 2)] ≡ ∀𝖠∼ (𝖠2 = 2)] ≡ ∀𝖠(𝖠2 ≠ 2)].

Exercise 31
(1) Q(x) : 𝖠 < 2 UoD = Set of real numbers Find Truth value of ∀𝖠𝖠(𝖠).
(2) Negation of quantified statement changes the quantifier and negates the original
statement
(a) ∼ [∀𝖠∼ 𝖠(𝖠 )] (b) )∼ [∼ ∃ 𝖠 ∼ 𝖠(𝖠)]
(3) Symbolize the following statements?

a. There are positive value of x & y such that 𝖠𝖠 > 0.

b. For every value of x there is some value of y such that 𝖠. 𝖠 = 1.

Learning from the topic: Students will be able to understand the Normal forms

Lecture – 32

Learning Objective:
1. Student shall be able to learn Mathematical Induction.

107
 SE Semester III-CBCGS HME 2023-24

5.1.14. Principal of Mathematical Induction:

Let P(n) be a statement pr proposition defined by the set of positive integers, “𝖠+”
such that it is either true or false for all 𝖠 ∈ 𝖠+. For the given statement P(n), if we can
prove that

(a) P(n) is true for 𝖠 = 𝖠0 and

(b) P(n) is true for 𝖠 = 𝖠 + 1 assuming that it is true for 𝖠 = 𝖠 (𝖠 ≥

𝖠0).Then we can conclude that P(n) is true for all natural numbers 𝖠 ≥

𝖠0. Step of

principle mathematical induction are as follows:

(i) Basis of induction: Assume the validity of the statement for the smallest integral value ofn
for which it is true.

(ii) Induction step If the statement is true for n=k, where k denotes any value of n, then it
isalso true for n=k+1.

(iii) Conclusion: The statement is true for all integral values of n equal to or greater than
that for which it is verified in step 1.

Example: Using the principle of mathematical induction, prove

that P(n): 1+3+5+ ...........+(2n+1 )= 𝖠2

Solution: Step 1. If n=1, then left hand side of P(n) is 1 and right hand side is 1. Hence P(n)is
true for n=1.

Step 2. Assuming that P(n) is true for n=k, then we

get P(k): 1+3+5+………………………..+(2k-1)= 𝖠2

Adding the term (2k+1) on both side of P(k), we get

1+3+5+………………………..+(2k-1)+(2k+1)= 𝖠2+(2k+1)= (𝖠 + 1)2

This shows that if P(n) is true for n=k, then it is also true for n=k+1. Hence , by mathematical
induction P(n) is true for every integral value of n.

Exercise 32
A) Using the principle of mathematical induction, prove that

(1) P(n): =

(2)P(n): 1.2.3+2.3.4+…+n(n+1)(n+2)=
108
 Mathematics – III (CS & E)
)

Let’s check the takeaway from lecture

1. What is the base case for the inequality 7n > n3, where n = 3

(a) 652 > 189 (b) 42 < 132 (c) 343 > 27 (d) 42 ≤ 431

2. For any integer m ≥3, the series 2+4+6+…+(4m) can be equivalent to

(a) m2+3 (b) m+1 (c) mm (d) 3m2+4

Homework Problems for the day
1. Show that by induction that 12-22+32-42…(-1)n-1n2 = (-1)n-1 𝖠(𝖠+1)
2
2. Show that 2n ×2n-1 is divisible by 3 for all n≥1 by induction.
3. Show that 13+23+33…+n3 = (1+2+3+…+n)2
4. Prove by Induction that sum of Cube of three consecutive numbers
are always divisible by 9.

Learning from the topic: Students will be able to understand the Mathematical Induction
Learning Outcomes
1. Know: Student should be able
to

a. Define Logic & Valid Mathematical Statements.

b. Define Arguments and Mathematical Induction.
2. Comprehend: Student should be able to
a. Find the Mathematical Statements.
3. Apply, analyze and synthesize: Student should be able to
a. Solve Mathematical Statements , Mathematical Induction.

Self-Assessment

Name of student: Class & Div: Roll No:

1. Are you able to find Laplace Transform of polynomials?
(a) Yes (b) No

2. Are you able to find the Laplace Transform of trigonometric functions?

(a) Yes (b) No

3. Do you understand the Unit step function and its Laplace Transform?
(a) Yes (b) No

4. Will you able to find the Laplace Transform of Periodic function?

(a) Yes (b) No

5. Do you understand this module?

109
SE Semester III-CBCGS HME 2023-24

(a) Fully understood (b) Partially understood (c) Not at all

Learning Resources:

1. Higher Engineering Mathematics, Dr. B. S. Grewal, Khanna Publications.

2. A textbook of Applied Mathematics, P.N. and J. [Link],Volume 1 and 2, Pune
Vidyarthi Griha.
3. Advanced Engineering Mathematics, Erwin Kreyszing, Wiley Eastern Limited, 8th Ed.

110
SE Semester III-CBCGS HME 2023-24

Module - 6
Algebraic Structures
6.1. Algebraic Structures

6.1.1 Motivation: Groups and fields are algebraic structures. Group theory is the study a
set of elements present in a group, in Mathematics. A group’s concept is fundamental to
abstract algebra. There are many applications in various areas of computer
programming, physics, electrical engineering, control engineering and signal processing.
Groups are used to solve Rubik’s cube. They are also used to express the fundamental
symmetry of many fundamental laws of nature.
6.1.2 Syllabus:

Module 6 Content Duration Self-Study time

6.1 Checking for the groups, semigroup, 3 lectures 6 hours
monoid, cyclic group using definition.
6.2 Fundamental Theorem of 2 lectures 4 hours
Homomorphism, Isomorphism
6.3 Coding and decoding: Error Detection 1 lecture 3 hours

6.1.3 Weightage: 18- 20 Marks

6.1.4 Prerequisite:
Groups and its properties.
*Small Quiz 1 as revision of Algebraic structures & its properties topics.
(via Group discussion mode)
6.1.5. Learning Objective: Student shall be able
 to define group, semigroup, monoid and their properties
 to check cyclic groups using various examples
 to check definition of abelian group using various examples
 to learn fundamental theorem of homomorphism
 to check for the isomorphism of different groups
 to solve error detection problems using group theory

6.1.6. Key Notations:

(1) (𝑮, ∘): Group with binary operation ∘
(2) ≅: Isomorphism
(3) +𝑛: addition modulo n. It will give the remainder when divided by n.
6.1.7. Key Definitions:
(1) Group: A group is a set with binary operation ∘∶ 𝑆 × 𝑆 → 𝑆 satisfying the following
properties:
i) Identity: there exist an element 𝑒 ∈ 𝑆 such that ∀𝑎 ∈ 𝑆, 𝑒 ∘ 𝑎 = 𝑎 = 𝑎 ∘ 𝑒.
ii) Inverse: ∀𝑎 ∈ 𝑆, 𝑎 ∘ 𝑎−1 = 𝑒 = 𝑎−1 ∘ 𝑎.
iii) Associativity: ∀𝑎, 𝑏, 𝑐 ∈ 𝑆, 𝑎 ∘ (𝑏 ∘ 𝑐) = (𝒂 ∘ 𝒃) ∘ 𝑐

(2) Homomorphism: Let (𝐺, ∘) and

(𝐻, ∗) be two groups and 𝑓: 𝐺 → 𝐻 is a mapping. Then,
𝑓 is said to be homomorphism if 𝑓(𝑎 ∘ 𝑏) = 𝑓(𝑎) ∗ 𝑓(𝑏), ∀𝑎, 𝑏 ∈ 𝐺.
110
 Mathematics – III (COMP)

Monoid, Semigroup, Groups

Lecture: 33
Algebraic Structures:
SE Semester III-CBCGS HME 2023-24

Binary Relation / Binary Composition: Let 𝑆 be a non-empty set and ∗: 𝑆 × 𝑆 → 𝑆 is a mapping.

Then, * is said to be binary composition if 𝑎 ∗ 𝑏 ∈ 𝑆, ∀𝑎, 𝑏 ∈ 𝑆.
Example: Addition ‘+’ is binary operation on ℤ (Set of integers).

Question: Show that division is not a binary operation in N.

Solution: Let 𝑎, 𝑏 ∈ 𝑁. Binary operation ÷: ℕ × ℕ → ℕ is 𝑎.
𝑏
Consider 4, 3 ∈ ℕ. But 4 ∉ ℕ. Hence, division is not binary operation on ℕ.
3

Semigroup: Let 𝑆 be a non-empty set and ∗: 𝑆 × 𝑆 → 𝑆 is arbitrary operation on 𝑆. Then, S is said

to be semigroup if (𝑎 ∗ 𝑏) ∗ 𝑐 = 𝑎 ∗ (𝑏 ∗ 𝑐), ∀𝑎, 𝑏, 𝑐 ∈ 𝑆.
Example: ℚ (Set of Rational) with ‘+’ as operation is semigroup.

Question: Let ℤ be the set of integers with operation ∗ ∶ ℤ × ℤ → ℤ defined by

𝑥 ∗ 𝑦 = 𝑥 + 𝑦 − 𝑥𝑦, ∀𝑥, 𝑦 ∈ ℤ. Then, prove that (ℤ, ∗) is semigroup.
Solution:
Let 𝑥, 𝑦 ∈ ℤ. We know that addition, subtraction and multiplication of two integers is
integers. Hence, 𝑥 ∗ 𝑦 ∈ ℤ. Hence, (ℤ, ∗) is closed.
Now, let 𝑥, 𝑦, 𝑧 ∈ ℤ.
Consider, 𝑥 ∗ (𝑦 ∗ 𝑧) = 𝑥 ∗ (𝑦 + 𝑧 − 𝑦𝑧)
= 𝑥 + (𝑦 + 𝑧 − 𝑦𝑧) − 𝑥(𝑦 + 𝑧 − 𝑦𝑧)
= 𝑥 + 𝑦 + 𝑧 − 𝑦𝑧 − 𝑥𝑦 − 𝑥𝑧 + 𝑥𝑦𝑧 …………………(1)
Also, (𝑥 ∗ 𝑦) ∗ 𝑧 = (𝑥 + 𝑦 − 𝑥𝑦) ∗ 𝑧
= (𝑥 + 𝑦 − 𝑥𝑦) + 𝑧 − (𝑥 + 𝑦 − 𝑥𝑦)𝑧
= 𝑥 + 𝑦 − 𝑥𝑦 + 𝑧 − 𝑥𝑧 − 𝑦𝑧 + 𝑥𝑦𝑧
= 𝑥 + 𝑦 + 𝑧 − 𝑦𝑧 − 𝑥𝑦 − 𝑥𝑧 + 𝑥𝑦𝑧 …………………(2)
From (1) & (2), we get 𝑥 ∗ (𝑦 ∗ 𝑧) = (𝑥 ∗ 𝑦) ∗ 𝑧
Hence, ∗ is associative.
(ℤ, ∗) is semigroup.

Monoid: Let 𝑆 be a non-empty set and ∗: 𝑆 × 𝑆 → 𝑆 is binary composition on 𝑆. Then, 𝑆 is said to

be monoid if it satisfies following axioms:
i) (𝑎 ∗ 𝑏) ∗ 𝑐 = 𝑎 ∗ (𝑏 ∗ 𝑐), ∀𝑎, 𝑏, 𝑐 ∈ 𝑆.
ii) there exist an element 𝑒 ∈ 𝑆 such that ∀𝑎 ∈ 𝑆, 𝒆 ∗ 𝒔 = 𝑠̅ = 𝑠̅ ∗ 𝑒.
Example: Ν (set of natural numbers) with ‘+’ as binary operation is monoid.

Question: Let ℝ be the set of real numbers with operation ∘∶ ℝ × ℝ → ℝ defined by 𝑥 ∘

𝑦 = 𝑥 + 𝑦 + 𝑥𝑦, ∀𝑥, 𝑦 ∈ ℝ. Then, prove that (ℝ, ∘) is monoid.
Solution: Let 𝑥, 𝑦 ∈ ℝ. We know that addition, subtraction and multiplication of two real
numbers is real number. Hence, 𝑥°𝑦 ∈ ℝ. Hence, (ℝ, ∘) is closed and ° is the binary
operation on ℝ.
Now, let 𝑥, 𝑦, 𝑧 ∈ ℝ.

= 𝑥 + (𝑦 + 𝑧 + 𝑦𝑧) + 𝑥(𝑦 + 𝑧 + 𝑦𝑧)

= 𝑥 + 𝑦 + 𝑧 + 𝑦𝑧 + 𝑥𝑦 + 𝑥𝑧 + 𝑥𝑦𝑧 …………………(1)
Also, (𝑥 ∘ 𝑦) ∘ 𝑧 = (𝑥 + 𝑦 + 𝑥𝑦) ∘ 𝑧
= (𝑥 + 𝑦 + 𝑥𝑦) + 𝑧 + (𝑥 + 𝑦 + 𝑥𝑦)𝑧
= 𝑥 + 𝑦 + 𝑥𝑦 + 𝑧 + 𝑥𝑧 + 𝑦𝑧 + 𝑥𝑦𝑧
112
 Mathematics – III (COMP)
= 𝑥 + 𝑦 + 𝑧 + 𝑦𝑧 + 𝑥𝑦 + 𝑥𝑧 + 𝑥𝑦𝑧 …………………(2)
From (1) & (2), we get 𝑥 ∘ (𝑦 ∘ 𝑧) = (𝑥 ∘ 𝑦) ∘ 𝑧
Hence, ∘ is associative.

Now, 𝑥 ∘ 0 = 𝑥 + 0 + (𝑥 × 0)
=𝑥
= 0 + 𝑥 + (0 × 𝑥)
=0∘𝑥
Hence, ∃0 ∈ ℝ such that 𝑥 ∘ 0 = 𝑥 = 0 ∘ 𝑥. Hence, 0 is the identity of (ℝ, ∘).
Therefore, (ℝ, ∘) is monoid.

Exercise 33
1. Prove that (ℝ, ÷) is group.
2. Give an example of semigroup and monoid.
3. Give an example for semigroup which is not group.
Learning from the topic: Students will be able to understand the concept of Groups

Lecture: 34
Groups:
 SE Semester III-CBCGS HME 2023-24

Group: An algebraic structure (𝐺, °), where 𝐺 is non- empty set and ∗: 𝐺 × 𝐺 → 𝐺 is binary
composition on 𝐺 is said to be group if it satisfies the following properties:
i) Identity: there exist an element 𝑒 ∈ 𝐺 such that ∀𝑎 ∈ 𝐺, 𝑒 ∘ 𝑎 = 𝑎 = 𝑎 ∘ 𝑒.
ii) Inverse: ∀𝑎 ∈ 𝐺, 𝑎 ∘ 𝑎−1 = 𝑒 = 𝑎−1𝑎.
iii) Associativity: ∀𝑎, 𝑏, 𝑐 ∈ 𝐺, 𝑎 ∘ (𝑏 ∘ 𝑐) = (𝑎 ∘ 𝑏) ∘ 𝑐
Example: (ℝ, ×) is group under multiplication as binary operation.
ℤ𝑛 = {0, 1, 2, 3, 4, … , 𝑛 − 1} is group under addition modulo 𝑛.
ℤ𝑚 × ℤ𝑛 = {(𝑝, 𝑞)|𝑝 ∈ ℤ𝑚 & 𝑞 ∈ ℤ𝑛} is group under composition.

Question: Prove that ℤ6 = {0, 1, 2, 3, 4, 5} is a group under addition modulo 6.

Solution: Let ℤ6 = {0, 1, 2, 3, 4, 5}.
We know that 𝑎+6𝑏 ∈ ℤ6, ∀𝑎, 𝑏 ∈ ℤ6. Hence +6 is binary operation on ℤ6.
i) 0+61 = 1, 0+62 = 2, 0+63 = 3, 0+64 = 4, 0+65 = 5
Hence, 0 ∈ ℤ6 is the identity element of ℤ6.
ii) Here, 0+60 = 0, 1+65 = 0, 2+64 = 0, 3+63 = 0,
4+62 = 0, 5+61 = 0. Hence, inverse of each element exists.
iii) Also, 𝑎+6(𝑏+6𝑐) = (𝑎+6𝑏)+6𝑐, 𝑎, 𝑏, 𝑐 ∈ ℤ6, as addition is associative in ℤ.
Therefore, ℤ6 satisfies all the properties of group.
∴ ℤ6 is a group.
Subgroup: A non-empty subset 𝐻 of 𝐺 is said to be subgroup of 𝐺 if 𝐻 itself is a group under same
binary operation as that of 𝐺.
Remark: A non-empty subset 𝐻 of 𝐺 is said to be subgroup of 𝐺 𝑖𝑓𝑓 𝑎𝑏−1 ∈ 𝐻, ∀𝑎, 𝑏 ∈ 𝐻.
Example: (ℚ{0}, ×) is subgroup of (ℝ, ×).

Question: Show that 𝑛ℤ is a subgroup of ℤ, the group of integers under addition.

Solution: (Subgroups of the integers) Let n ∈ ℤ.

nℤ = {nx | x ∈ ℤ}
𝑛ℤ consists of all multiples of n
First, to show that 𝑛ℤ is closed under addition. If 𝑛𝑥, 𝑛𝑦 ∈ 𝑛ℤ, then,
𝑛𝑥 + 𝑛𝑦 = 𝑛(𝑥 + 𝑦) ∈ 𝑛𝑍.
Therefore, 𝑛ℤ is closed under addition.
i) Identity Element of ℤ is 0. Now 0 = n · 0, so 0 ∈ 𝑛ℤ.
ii) Now to find inverse.
suppose 𝑛𝑥 ∈ ℤ. The additive inverse of 𝑛𝑥 in ℤ is −𝑛𝑥, and −𝑛𝑥 = 𝑛(−𝑥). This
is 𝑛 times something, so it’s in 𝑛ℤ. Thus, 𝑛ℤ is closed under taking inverses.
Therefore, 𝑛ℤ is a subgroup of 𝑛ℤ.
iii) Associativity:
𝑛𝑥 + (𝑛𝑦 + 𝑛𝑧) = (𝑛𝑥 + 𝑛𝑦) + 𝑛𝑧, ∀𝑥, 𝑦, 𝑧 ∈ ℤ, as associativity holds in the
set of integers.
∴ 𝑛ℤ is a subgroup of ℤ.

Order of Group: The number of elements in the group 𝐺 is called order of group. It is denoted by |G|. If
the number of elements is finite, then the group is said to be Finite Group. If there are infinite number of
elements in the groups, then it is called Infinite Group.
Example: ℤ6 has 6 number of elements in it. Hence the order of ℤ6 is 6. i.e. |ℤ6| = 6.

114
 Mathematics – III (COMP)

Order of Element of Group: Order of an element is 𝑟 of group 𝐺 i.e. 𝑂(𝑎) = 𝑟 𝑖𝑓𝑓 𝑎𝑟 = 𝑒, where 𝑒 is
the identity element of 𝐺.
Example: Consider ℤ6 and 2∈ ℤ6.

2 +6 2+6 2 = 0 (6 𝑚𝑜𝑑𝑢𝑙𝑜 6). Hence, order of 2∈ ℤ6 is 3. 𝑜(2) = 3.

Abelian Group:
Definition 1. A group 𝐺 is said to be abelian if it satisfies the commutative law under multiplication. i.e.
𝑎𝑏 ∈ 𝐺, ∀𝑎, 𝑏 ∈ 𝐺.
Example: (ℝ, ×) is abelian group under multiplication as binary operation.
Question: Let ℤ be the group of integers with binary operation ∗ ∶ ℤ × ℤ → ℤ defined by
𝑥 ∗ 𝑦 = 𝑥 + 𝑦 − 𝑥𝑦, ∀𝑥, 𝑦 ∈ ℤ. Then, prove that (ℤ, ∗) is abelian.
Solution:
Let 𝑥, 𝑦, 𝑧 ∈ ℤ.
Consider, 𝑥 ∗ 𝑦 = 𝑥 + 𝑦 − 𝑥𝑦 = 𝑦 + 𝑥 − 𝑦𝑥 = 𝑦 ∗ 𝑥, ∀𝑥, 𝑦 ∈ ℤ.
∴ (ℤ, ∗) is abelian group.

Cyclic Group: A group is said to be cyclic is there exist an element 𝑏 ∈ 𝐺 such that every element of 𝐺 is
power of 𝑏. Here, 𝑏 is said to be generator of 𝐺 and we denote 𝐺 =< 𝑏 >.
Example: ℤ𝑛, for all 𝑛 is cyclic group of order under addition modulo 𝑛.
Question: Consider the group ℤ2 × ℤ3 = {(m, n) | m ∈ ℤ2, n ∈ ℤ3}. Show that
ℤ2 × ℤ3 is cyclic by finding generators.
Solution: The operation is component wise addition
(𝑚, 𝑛) + (𝑚′, 𝑛′) = (𝑚 + 𝑚′, 𝑛 + 𝑛′)

It is routine to verify that this is a group, the direct product of ℤ2 and ℤ3.
The element (1, 1) ∈ ℤ2 × ℤ3 has order 6:

(1, 1) + (1, 1) = (0, 2),

(1, 1) + (0, 2) = (1, 0),
(1, 1) + (1, 0) = (0, 1),
(1, 1) + (0, 1) = (1, 2),
(1, 1) + (1, 2) = (0, 0).
Hence, ℤ2 × ℤ3 is cyclic of order 6. More generally, if (m, n) = 1, then ℤ𝑚 × ℤ𝑛 is cyclic
of order 𝑚𝑛.
Remark:

1) The number of generators of cyclic group 𝐺 of order 𝑛 is equal to 𝜙(𝑛), where 𝜙(𝑛) is the Euler-
𝜙 function. i.e. 𝜙(𝑛) = totaL number of integers which are relatively prime to n.

115
 SE Semester III-CBCGS HME 2023-24

2) The subgroup of cyclic group is cyclic. The converse need not be true.

Statement: Every cyclic group is abelian.

Proof: True. Let G be a cyclic group. All elements of are of the form 𝑎𝑛, n∈ ℕ, where
Let 𝑥, 𝑦 ∈ 𝐺 ∶ 𝑥 = 𝑎𝑝, 𝑦 = 𝑎𝑞
Then,
𝑥𝑦 = 𝑎𝑝 𝑎𝑞 = 𝑎𝑝+𝑞 = 𝑎𝑞+𝑝 = 𝑎𝑞 + 𝑎𝑝 = 𝑦𝑥 .
Thus, 𝑥𝑦 = 𝑦𝑥, for all 𝑥, 𝑦 ∈ 𝐺. (𝑝 + 𝑞 = 𝑞 + 𝑝 as ℤ is an abelian additive group.)
Exercise 34
1. Give an example of non-cyclic group which has cyclic subgroup.
2. Find the number of generators of ℤ44.
3. Let (ℤ100, ∗) be the group. 𝑆 = {ℎ ∈ 𝐺|𝑂(ℎ) = 50}. Then find |𝑆|.
4. Let 𝐺 be a non-abelian group. Let 𝛼 ∈ 𝐺 have order 4 and 𝛽 ∈ 𝐺 have order 3. Then find the
order of element 𝛼𝛽.

Lecture: 35
Homomorphism: Let (𝐺, °) and (𝐻, ∗) be two groups and 𝑓: 𝐺 → 𝐻 is a mapping. Then,
𝑓 is said to be homomorphism if 𝑓(𝑎°𝑏) = 𝑓(𝑎) ∗ 𝑓(𝑏), ∀𝑎, 𝑏 ∈ 𝐺.
Example: 𝑓: (ℤ, +) → (ℤ, +) defined by 𝑓(𝑎 + 𝑏) = 𝑓(𝑎) + 𝑓(𝑏).
Remark: Number of Homomorphism 𝑓: ℤ𝑚 → ℤ𝑛 is equal to gcd(𝑚, 𝑛).
Question: Check whether : (ℤ, +) → (ℤ, +) defined by 𝑓(𝑛) = 𝑛2 is homomorphism or
not.
Solution: Let 𝑛, 𝑚 ∈ ℤ.
Consider, 𝑓(𝑛 + 𝑚) = (𝑛 + 𝑚)2
= 𝑛2 + 𝑚2 + 2𝑚𝑛
≠ 𝑓(𝑛) + 𝑓(𝑚)
Hence, 𝑓 is not homomorphism.

Kernel of Homomorphism: Let 𝑓 be a homomorphism from group 𝐺 into group 𝐺′.

Then, kernel of 𝑓 is defined by 𝑘𝑒𝑟(𝑓) = {𝑥 ∈ 𝐺|𝑓(𝑥) = 𝑒′}, where 𝑒′ is the identity
element of group 𝐺′.
Question: Consider the homomorphism 𝜙: (𝑀∗, ×) →: (𝑀∗, ×) defined by
2 2
𝑎 𝑏 1 1 𝑎 𝑏 1 1 −1
𝜙 ([ ]) = [ ][ ][ ]
𝑐 𝑑 0 1 𝑐 𝑑 0 1

Where, 𝑀2∗ is the set of all invertible matrices. Find 𝑘𝑒𝑟(𝜙).

Solution: Let 𝑀2∗ is the set of all invertible matrices.
∗ ∗ 𝑎 𝑏 1 1 𝑎 𝑏 1 1 −1
𝜙: (𝑀2, ×) →: (𝑀2, ×) defined by 𝜙 ([ ]) = [ ][ ][ ]
𝑐 𝑑 0 1 𝑐 𝑑 0 1
116
 Mathematics – III (COMP)

We know that 𝑘𝑒𝑟( 𝜙) = {𝑥 ∈ 𝑀2∗| 𝜙(𝑥) = 𝑒′}, where 𝑒′ is the identity

Element of 𝑀2∗.
1 0
Now, the identity element of 𝑀∗ is [ ].
2 0 1
∴ 𝑘𝑒𝑟(𝑓) = {𝑥 ∈ 𝑀∗| 𝜙(𝑥) = 𝑒′}
𝑎 𝑏 2 ∗
= {[ ] ∈ 𝑀 | 𝜙 ([𝑎 𝑏]) = [1 0]}
2
𝑐 𝑑 𝑐 𝑑 0 1
𝑏 1]−1 [1
= {[
𝑎 ] ∈ 𝑀 ∗ | [1 1] [𝑎 𝑏] [1 = 0]
}
2
𝑐 𝑑 0 1 𝑐 𝑑 0 1 0 1
] ∈ 𝑀 ∗ | [1 1] [𝑎
𝑎 𝑏 𝑏] = [1 0] [1 1]
= {[ 2 }
𝑐 𝑑 0 1 𝑐 𝑑 0 1 0 1
𝑎 𝑏 ] ∈ 𝑀 ∗ | [𝑎 𝑏 ] = [1 1]−1 [1 0] [ 1 1]
= {[ 2 }
𝑐 𝑑 𝑐 𝑑 0 1 0 1 0 1
𝑎 𝑏 ∗ 𝑎 𝑏 1 0
= {[ ] ∈ 𝑀2 | [ ]=[ ]}
𝑐 𝑑 𝑐 𝑑 0 1

117
 SE Semester III-CBCGS HME 2023-24

1 0
= {[ ]}
0 1

Isomorphism: Let (𝐺, °) and (𝐻, ∗) be two groups and 𝑓: 𝐺 → 𝐻 is a mapping. Then, 𝑓
is said to be isomorphism if 𝑓 is one-one, onto and Homomorphism.
Question: Show that (ℝ, +) is isomorphic to (ℝ, ×).
Solution: Step I: For 𝑥𝜖ℝ, we define 𝑓(𝑥) = 𝑒 𝑥 . This gives a mapping 𝑓: ℝ → ℝ.
Step II: If 𝑓(𝑥) = 𝑓(𝑦) ⟹ 𝑒 𝑥 = 𝑒𝑦 ⟹ 𝑥 = 𝑦, 𝑓𝑜𝑟 𝑎𝑙𝑙 𝑥, 𝑦 ∈ ℝ.
This is one-to-one mapping.
Step III: If 𝑟 ∈ ℝ+, then 𝑓(ln 𝑟) = 𝑒𝑙𝑛𝑟 = 𝑟, 𝑤ℎ𝑒𝑟𝑒 (𝑙𝑛𝑟) ∈ ℝ. Thus 𝑓 is
Onto.
Step IV: For 𝑥, 𝑦 𝜖ℝ, we have 𝑓(𝑥 + 𝑦) = 𝑒𝑥+𝑦 = 𝑒 𝑥 𝑒 𝑦 = 𝑓(𝑥)𝑓(𝑦).
Thus, (ℝ, +) ≅ (ℝ, ×)

Exercise 35
1. 𝑓(𝑥) = 𝑙𝑜𝑔(𝑥) for groups (ℝ+,×) and (ℝ, +) is a group isomorphism.
2. Groups ({0,1,2,3}, +4) and ({2,3,4,1}, +5) are isomorphic.
3. (ℚ, +) is isomorphic to (ℤ, +).
4. Are (ℝ, +) and (ℂ, +) isomorphic additive groups?

Learning from the topic: Students will be able to solve the problems related to algebraic
structures.

Learning Outcomes

1. Know: Student should be able to

a. Define algebraic structures.
b. Define fields, abelian & cyclic groups.
2. Comprehend: Student should be able to
a. Check the properties of groups.
b. Find the homomorphic and isomorphic groups.
3. Apply, analyze and synthesize: Student should be able to
a. Apply the concept of groups and fields in coding-decoding & error detection
technique.
Learning Resources

1. Higher Engineering Mathematics, Dr. B. S. Grewal, Khanna Publications,36th Edition

2010
2. Advanced Engineering Mathematics, Erwin Kreyszing, John Wiley & Sons 9th Edition
2006
3. A textbook of Engineering Mathematics N.P. Bali and Manish Goyal Laxmi
Publications 9th Edition 2008
4. Engineering Mathematics Veerarajan T Tata McGraw-Hill, New Delhi 3rd Edition 2008
116
 Mathematics – III (CS & E)

5. Higher Engineering Mathematics Ramana B.V. Tata McGraw Hill, New Delhi 11th
Edition 2010
6. Linear Algebra: A Modern Introduction D. Poole Brooks/Cole 2nd Edition 2005
7. An introduction to Linear Algebra V. Krishnamurthy, V.P. Mainra and J.L. Arora
Affiliated East–West press - 2005

Lecture:36
Field: A field is an ordered triplet (F, +, .) where F is a non-empty set and + and . are two binary
operations on F satisfying the following axioms.
F1: ( F,+) is a commutative group.
F2: (a.b).c =a.(b.c) for all a,b,c ∈F (. commutative.)
F3: a.(b+c)=a.b+a.c
and (b+c).a=b.a+c.a for all a,b,c ∈F (. Distributes over +).
F4: (F ~0, .) is a commutative group.

Question: Show that the set 

F  a b 2  where a and b are rational numbers is a field
under addition and multiplication.

Solution: Closure: Let X a  b 2, Y  c  d 2where a,b, c, 𝑑 ∈Q.

2

Since   
X  Y  a  b 2  c  d 2   a  c   b  d 


XY  a  b 2 c  d 2  ac  2bd   2 ad  bc
and since a  c,b  d ,ac  2bd ,ad  bc are rational numbers  X  Y and
XY  F. Hence F is closed under addition + and multiplication.
F1: Consider (F,+).
(i) Since for all rational numbers addition is associative, we can show that

X  Y  Z    X  Y   Z. Addition is associative.

(ii) Since a  b 2 0  0 2  a  b 2,0  0 i.e. 0Q is additive

identity.

F3: It can be shown that 117

SE Semester III-CBCGS HME 2023-24

  
2, additive inverse exists.
(iii) Since a  b 2  a  b 2  0  0 a  b

(iv) Since for rational numbers addition is commutative.

Hence (F,+) is a commutative group.

F2: It can be shown that  X Y   Z  X  Y  Z ,X ,Y , Z  F.

Hence . is associative.

118
 Mathematics – III (CS & E)

X  Y  Z   X Y  X  Z
and  X  Y   Z  X  Z  Y  Z ,X ,Y , Z  F.
Hence . is distributes over +.

F4: Consider (F 0, .),

(i) . is associative as noted in F2.

(ii) Since a  b 21 0 2  a  b ,1 0 , is multiplication identity.

X  0 i.e. if a  0,b  0, and X  a  b 2,then

1 1 1 a b 2 a b 2
    2 cd 2
X a  b 2 a  b 2 a  b 2 a  2b
(iii) If
c a ,d   b .
a2  2b a2  2b
1
c, d  Q,  F.
X
Hence (F,+,.) is a field.

Exercise 36
1. Show that the set of integers Z is a ring under addition and multiplication. Is it a field?
2. Prove that (Z5, +, .) is a field where Z5 is a set R of residue classes of {0,1,2,3,4}modulo 5.
a b 
3. Show that the set of matrices M   
, a,b  Z form an integral domain. Is it a
5b a 
field.

Lecture:37
Encoding Function: If an integer n>m and if there is one to one correspondence e : Bm  Bn
then e is called an (m,n) encoding function. In this way every word in Bm is represented by a world in
B n. If bB m then e(b) is called the code word representing b.

Weight: If a world x  Bn then the number of 1’s x is called the weight of x and is denoted by x.
F3: It can be shown that 119
 SE Semester III-CBCGS HME 2023-24

Question: Find the weights of each of the following words in B5.

(i) X=00100 (ii) X=01010 (iii) X=00000 (iv) X=11110

Solution: i x  1ii x  2iii x  0iv x  4.

Group Codes, Decoding and Error Correction:

120
 Mathematics – III (CS & E)

Group Code: An (m,n) coding function e : Bm  Bn is called a group code if

 
e  B m   eb b  B m  Rangee
is a subgroup of Bn.
e : B2  B5 defined by
Question: Show that the (2,5) encoding function
e00  00000,e01  01110,e10  10101,e11  11011 is a group code.
Solution: Let N={00000, 01110, 10101, 11011}.We have to show that N is a subgroup of B5. We shall
now prepare the following table for B5.

We prepare the following table by using 0+0=0, 0+1=1, 1+0=0 and 1+1=0.
For example: 01110+10101=11011; 11011+01110=10101

 | 00000 01110 10101 11011

00000 | 00000 01110 10101 11011
01110 | 01110 00000 11011 10101
10101|10101 11011 00000 01110
11011|11011 10101 01110 00000

(i) From the diagonal elements of the above table we see that the identity(00000) of B5 is in N.

(ii) From the table we see that if X,Y belongs to N then X  Y also belongs to N.
(iii) Every elements is its inverse.

Hence N is a subgroup of B5 and the given encoding function is a group code.

Hamming Distance: If X, Y are words in Bm then the weight of X  Y i.e. X  Y is called the

Hamming distance between X and Y and is denoted by   X ,Y .

Question: Find the distance between X and Y where,

(i) X=110110, Y=000101 (ii) X=001100, Y=010110

Solution: X  Y is obtained from the table

119
 SE Semester III-CBCGS HME 2023-24

+ 0 1
0 0 1
1 1 0

for every digit.

120
 Mathematics – III (CS & E)

110110
(i) X  Y = 000101
 X Y  4
110011

01100
(ii) X  Y = 010110
 X Y  3
011010

Exercise-37

(i) Consider (3,6) encoding function defined below.

e000  000000,e001  000110,e010  010010,e011  010100,

e100  100101,e101  100011,e110  110111, e111  110001.
Show that the encoding function is a group code.
(ii) Find the distance between X and Y where,

(i) X=1100010, Y=1010011 (ii) X=0100100, Y=0011010.

121
SE Semester III-CBCGS HME 2023-24

Online References

1. [Link]
[Link]

2. [Link]
[Link]
3. [Link]
[Link]
equations

122
SE [Link]
esO
terMIIaIp-C
pBinCgGwSitH
hMRE
ev2is0e2d3-B2l4oom’s Taxonomy Level

Sr. Course Outcomes Revised Bloom’s

No. Taxonomy Level
1 Understand the basic concepts of set theory and able to L1, L2
apply basic set operations in problem solving.
2 Understand relation and function and their properties and L1, L2, L3
also able to understand their use in programming
applications.
3 Able to apply PO set and Boolean lattice concepts in L1, L2, L3
various applications.
4 Able to apply graph theory in various fields. L1

5 Apply the Logic in real life applications. L1, L2, L3

6 Apply the concept of group theory in coding-decoding and L1, L2, L3

error detection.

B. CO and PO Mapping

PO
PO1 PO2 PO3 PO4 PO5 PO6 PO7 PO8 PO9 PO10 PO11 PO12
CO
CO1 H H M L L L M
CO2 H H M L L L M
CO3 H H L L L M
CO4 H H M L L L L M
CO5 H H M L L M
CO6 H H M L L L L M

C. CO, PO and PSO Mapping

PO
PSO1 PSO2 PSO3
CO
CO1 H H
CO2 H M
CO3 H M
CO4 H H
CO5 H H
CO6 H H

122