GOVERNMENT ENGINEERING COLLEGE, MODASA
Semester-4 (CE/IT) A. Y. 2025-26
Discrete Mathematics and Graph Theory (BE04000261)
Tutorial-3
Topics: Functions, Algebraic Structures
1. Define injective (one-one), surjective(onto) and bijective(one-one onto) function. Let N
be set of natural numbers including zero. Determine whether the function f : N → N,
f (j) = j 2 + 2 is injective, surjective or bijective.
√
2. Let f : R → R be given by f (x) = −x2 and g : R+ → R+ be given by g(x) = x
where R+ is the set of non-negative real numbers and R is the set of real numbers. Find
a
f ◦ g. Is g ◦ f defined? Justify your answer. Determine whether (i) f is one-one (ii) g
is one-one.
as
3. Define Composition of a function. Let X = {1, 2, 3} and f, g, h and s be functions from
X to X given by f = {(1, 2), (2, 3), (3, 1)}, g = {(1, 2), (2, 1), (3, 3)}, h = {(1, 1), (2, 2), (3, 1)},
s = {(1, 1), (2, 2), (3, 3)} Find f ◦ g, g ◦ f , f ◦ h ◦ g, s ◦ g, g ◦ s, s ◦ s. Are functions s
od
and f invertible?
4. Let I be the set of integers and + , × denote usual operations of addition and multiplication
respectively. (i) Is (I, +) a group? Justify your answer. (ii) Is (I, ×) a group? Justify
your answer.
,M
5. Prove that set G = {1, 2, 3, 4, 5, 6} is a finite abelian group of order 6 with respect to
multiplication modulo 7 (Prove that ⟨Z∗ 7 , ×7 ⟩ is an abelian group). Also find generators
of this group.
6. Define left coset of a subgroup ⟨H, ∗⟩ in the group ⟨G, ∗⟩. Find left cosets and right
EC
cosets of {0, 3} in the group ⟨Z6 , +6 ⟩.
7. Show that if every element in a group is its own inverse, then the group must be abelian.
8. Show that every subgroup of a cyclic group is normal.
9. Prove that every cyclic group is abelian, but converse is not true.
G
10. Write down the properties of cyclic group. Show that ⟨Z6 , +6 ⟩ is a cyclic group of order
6 and also find its generators.
11. Define (i) a group homomorphism (ii) Kernel of group homomorphism. Let g be a
homomorphism from a group (G, ∗) to a group (H, △). Show that g(eG ) = eH and for
any a ∈ G, g(a−1 ) = (g(a))−1 .
12. Consider the ring Z14 = {0, 1, . . . , 13} of integers modulo 14. (a) Find the units of Z14 .
(b) Find the roots of f (x) = x2 + 5x + 6 over Z14 .
Discrete Mathematics and Graph Theory Page 2 of 2
GOVERNMENT ENGINEERING COLLEGE, MODASA
Semester-4 (CE/IT) A. Y. 2025-26
Discrete Mathematics and Graph Theory (BE04000261)
Assignment-3
Topics: Functions, Algebraic Structures
1. Let X = {1, 2, 3, 4, 5} and f and g be functions from X to X given by f = {(1, 2), (3, 4), (2, 2)},
g = {(4, 2), (2, 5), (3, 1), (1, 3)} find f ◦ g, g ◦ f, f ◦ f, g ◦ g.
2. Let f : R → R and g : R → R where R is the set of real numbers. Find f ◦ g and g ◦ f
where f (x) = x2 − 2 and g(x) = x + 4. State whether these functions are injective,
surjective, and bijective.
a
3. Let X = {1, 2, 3, 4}. Define a function f : X → X such that f ̸= Ix and is one-one.
as
Find f ◦ f = f 2 , f 3 = f ◦ f 2 , f −1 , and f ◦ f −1 . Can you find another one-one function
g : X → X such that g ̸= Ix but g ◦ g = Ix ?
4. Show that the set of all positive rational number forms an abelian group under the
od
composition defined by a ∗ b = ab/2.
5. (i) Show that in a group (G, ∗), for any a, b ∈ G if (a ∗ b)2 = a2 ∗ b2 then (G, ∗) must be
abelian.
,M
(ii) If ⟨G, ∗⟩ be a group then for any two elements a and b of ⟨G, ∗⟩, prove that (a∗b)−1 =
b−1 ∗ a−1 .
6. Define a subgroup. Let (H1 , ∗) and (H2 , ∗) be subgroups of a group (G, ∗). Show that
(H1 ∩ H2 , ∗) is also a subgroup of (G, ∗). Show that in general, (H1 ∪ H2 , ∗) is not a
subgroup of (G, ∗), except when H1 ⊆ H2 or H2 ⊆ H1 .
EC
7. Show that ⟨{1, 4, 13, 16}, ×17 ⟩ is a subgroup of ⟨Z∗ 17 , ×17 ⟩.
8. State the Lagrange’s theorem. Define: Cyclic Group. Find the generator of (Z6 , +6 ).
9. Show that (Z4 , +4 ) is a cyclic group and find all the subgroups of (Z4 , +4 ).
G
10. Show that (Z∗ 5 , ×5 ) is a cyclic group and find all the generators of (Z∗ 5 , ×5 ) Where
Z∗ 5 = Z5 \ [0].
11. Consider the ring Z20 = {0, 1, . . . , 19} of integers modulo 20. (a) Find −3, −5 and −19.
(b) Find 3−1 , 13−1 and 16−1 .