UnFoldPrep
Browse Archive
Gujarat Technological UniversityWinter 2023 Examination

GTU 3140708 Discrete Mathematics (DM) Winter 2023 Paper Solution & PDF

B.E. · Computer Engineering · Semester 4 · Subject Code: 3140708
Download Official GTU PDF
Share:
Total Marks70 MarksExternal theory exam
Passing Marks23 Marks33% minimum cutoff
Exam Duration2.5 Hours10:30 AM – 1:00 PM
Paper Structure5 QuestionsWith internal OR choices
Jump toQ1Q2Q3Q4Q5

Question 1

14 MarksMedium
(a)
A function 𝑓: ℝ+ → ℝ is defined by 𝑓(𝑥) = 𝑥2 − 8. Check whether 𝑓 is
one-one and onto.
3 Marks
(b)

Determine the relation ∥ (parallel) on the set L of lines in the plane are reflexive, symmetric, anti-symmetric, transitive, irreflexive.

4 Marks
(c)
(
i)Show that the functions 𝑓(𝑥) = 𝑥3 and 𝑔(𝑥) = 𝑥1 3 for 𝑥 ∈ ℝ are inverses of one another.
ii)Check whether the following graphs are isomorphic.3 Marks
7 Marks

Question 2

14 MarksMedium
(a)
Identify the statement (𝑝⋀𝑞) ⋀ ¬(𝑝⋁ 𝑞) is tautology or contradiction.
3 Marks
(b)
(
i)Show that in a group (𝐺,∗), for any 𝑎, 𝑏 ∈ 𝐺 if (𝑎 ∗ 𝑏)2 = 𝑎2 ∗ 𝑏2 then (𝐺,∗) must be abelian.
ii)If (𝐺,∗) be a group then for any two elements 𝑎 and 𝑏 of (𝐺,∗), prove that (𝑎 ∗ 𝑏)−1 = 𝑏−1 ∗ 𝑎−1.
4 Marks
(c)
Use a truth table to determine whether the following argument form is
valid.
𝑝 → 𝑞
𝑞 → 𝑟
∴ 𝑝 → 𝑟
7 Marks
OR OPTION
(c)

Express the following using predicate, quantifier and logical connectives. Also verify the validity of the consequence.

i)Every computer science major takes discrete mathematics. Natasha is taking discrete mathematics. Therefore, Natasha is a computer science major.
ii)All parrots like fruit. My pet bird is not a parrot. Therefore, my pet bird does not like fruit.
7 Marks

Question 3

14 MarksMedium
(a)

Show that (ℤ5 ∗ ,×6) is cyclic group, where ℤ5 ∗ = ℤ5\{0}.

3 Marks
(b)

Given A = {x ∶ x is an integer and 1 ≤ x ≤ 5}, 𝐵 = {3, 4, 5, 17}, and 𝐶 = {1, 2, 3, . . . }, find 𝐴 ∩ 𝐵, 𝐴 ∪ 𝐵, 𝐴 ∩ 𝐵 ∩ 𝐶 and 𝐴 ∪ 𝐶.

4 Marks
(c)
(
i)Show that every subgroup of a cyclic group is normal
ii)The subset 𝐻 = {0,2} is a subgroup of (ℤ4, +4). Find all left and right cosets of 𝐻 in (ℤ4, +4). Is 𝐻 a normal subgroup?3 Marks
7 Marks
OR OPTION
(a)
Define 𝑓: (ℕ × ℕ,∗) → (ℚ,×) by 𝑓(𝑎, 𝑏) = 𝑎
𝑏. Show that 𝑓 is a
homomorphism.
3 Marks
(b)

In a class of 50 students, 12 enrolled for both Mathematics and Science, 32 enrolled for Science. If the students of the class enrolled for at least one of the two subjects, then how many students enrolled for only Mathematics but not Science?

4 Marks
(c)

Consider the ring ℤ10 = {0, 1, 2, … ,9} of integers modulo 10.

aFind the units of ℤ10.
bFind −3, −8 and 3−1.
cLet 𝑓 (𝑥) = 2𝑥2 + 4𝑥 + 4. Find the roots of 𝑓 (𝑥) over ℤ10.
7 Marks

Question 4

14 MarksMedium
(a)

Let 𝑋 = {1, 2, 3, 4} and 𝑅 = {〈𝑥, 𝑦〉/ 𝑥 > 𝑦} . Draw the graph of 𝑅 and also give its matrix.

3 Marks
(b)

Find out maximal compatibility blocks of following simplified graph of digraph and write its relation matrix.

4 Marks
(c)
Prove that 〈𝑆30, 𝐷〉 is a Boolean algebra.
7 Marks
OR OPTION
(a)

Define equivalence relation. Let 𝑋 = {1, 2, 3, 4,5}, 𝑅 = {〈𝑥, 𝑦〉/ 𝑥 is divisible by 𝑦}. Check whether the relation an equivalence relation?

3 Marks
(b)

Let 𝐴 = {𝑎, 𝑏, 𝑐, 𝑑} and 𝜌(𝐴) its power set. Let ⊆ be the inclusion relation on the elements of 𝜌(𝐴). Draw the Hasse diagram of 〈𝜌(𝐴), ⊆〉.

4 Marks
(c)

Solve 𝑎𝑛 = 11𝑎𝑛−1 − 39𝑎𝑛−2 + 45𝑎𝑛−3, 𝑎0 = 5, 𝑎1 = 11, 𝑎2 = 25.

7 Marks

Question 5

14 MarksMedium
(a)

A tree 𝑇 has 3 vertices of degree 4, 3 vertices of degree 3. Find the number of pendant vertices in tree 𝑇.

3 Marks
(b)

Find reachable set of each node of the given digraph. Also find 𝑑(𝑉1, 𝑉3), 𝑑(𝑉3, 𝑉1).

4 Marks
(c)

Define Strong, unilateral, week component. Also Find strong, unilateral, week component from the given digraph.

7 Marks
OR OPTION
(a)
Define null graph, centre of a graph and complete graph.
3 Marks
(b)
Find the path matrix using adjacency matrix of the following graph.
4 Marks
(c)

Define tree. In which order does a pre-order, in-order and post-order traversal visit the vertices of the ordered rooted tree shown in figure?

GTU Discrete Mathematics (3140708) Winter 2023 Question 5 OR (c) Diagram
7 Marks
College Exam Groups

Studying for Discrete Mathematics?

Circulate this solved paper with KaTeX formulas and 1-click AI step solvers to your batchmates on WhatsApp or Telegram.

Related papers

About this Examination Paper & Attribution

Official Gujarat Technological University (GTU) examination paper and step-by-step solutions for Discrete Mathematics (DM) (Winter 2023, B.E. · Computer Engineering, Sem 4). Features complete 70-mark regular & remedial examination pattern, official marking distribution across all 5 questions, and direct 1-click official PDF download.

Transcribed for student exam preparation from Gujarat Technological University official examination archives. Questions, syllabus guidelines, and curriculum marking schemes remain the intellectual property of Gujarat Technological University.

Download PDF