UnFoldPrep
Browse Archive
Gujarat Technological UniversitySummer 2024 Examination

GTU 3140708 Discrete Mathematics (DM) Summer 2024 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)

Define injective function. Given 𝐴 = {2, 5, 6}, 𝐵 = {3, 4, 2}, find (𝐴 − 𝐵) and (𝐵 − 𝐴).

3 Marks
(b)

Determine the relation ≤ (less than or equal) on the set ℤ of integers are reflexive, symmetric, anti-symmetric, transitive.

4 Marks
(c)
(
i)Check whether the function 𝑓(𝑥) = 𝑥3 − 2, for 𝑥 ∈ ℝ is invertible function. If so, find 𝑓−1(𝑥).
ii)Prove that a tree with 𝑛 vertices has 𝑛 − 1 edges.3 Marks
7 Marks

Question 2

14 MarksMedium
(a)
Identify the statement (¬𝑞⋀(𝑝 → 𝑞)) → ¬𝑝 is tautology or contradiction without
constructing the truth table.
3 Marks
(b)

Let 𝐺 be the subset of 2 × 2 real matrices with a nonzero determinant. Check whether 𝐺 is group under matrix multiplication. If so, is it abelian group?

4 Marks
(c)
(
i)Symbolize the expression “John is a bachelor and this painting is red”.
ii)Express the following using predicate, quantifier and logical connectives. Also verify the validity of the consequence. Everyone who graduates gets a job. Ram is graduated. Therefore, Ram got a job.3 Marks
7 Marks
OR OPTION
(c)
Use a truth table to determine whether the following argument form is valid.
𝑝 → 𝑞
𝑝 → 𝑟
∴ 𝑝 → 𝑞 ∨ 𝑟
7 Marks

Question 3

14 MarksMedium
(a)

Let 𝑔 be a homomorphism from a group (𝐺,∗) to a group (𝐻, ∆). Show that 𝑔(𝑒𝐺) = 𝑒𝐻 and for any 𝑎 ∈ 𝐺, 𝑔(𝑎−1) = (𝑔(𝑎))−1.

3 Marks
(b)
Prove that : 𝐴 ∪ (𝐵 ∩ 𝐶) = (𝐴 ∪ 𝐵) ∩ (𝐴 ∪ 𝐶).
4 Marks
(c)
(
i)Prove that every cyclic group is abelian.
ii)Consider the set of positive integers ℕ. Check which of (ℕ, +) and (ℕ,×) are semigroup and which are monoid?3 Marks
7 Marks
OR OPTION
(a)
Find left cosets and right cosets of 𝐻 = {0,3} in the group (ℤ6, +6).
3 Marks
(b)
(
i)Suppose repetitions are not allowed, how many four digit numbers can be formed from six digits 1,2,3,5,7,8?
ii)How many of such numbers less than 4000?
iii)How many in
i)are even?
iv)How many in
i)are divisible by 10?
4 Marks
(c)

Show that (𝑅, +, ×) is an integral domain, where 𝑅 = {𝑎 + 𝑏√5 / 𝑎, 𝑏 ∈ ℤ }.

7 Marks

Question 4

14 MarksMedium
(a)

Let 𝑆 = {1, 2, 3, 4} and 𝑅 = {(1,1), (1,4), (2,2), (2,3), (3,2), (3,3), (4,1), (4,4)} . Draw the graph of 𝑅 and hence write partition of 𝑆.

3 Marks
(b)

Define Lattice. Draw the Hasse diagram of (𝑆12, 𝐷), where 𝐷 is the relation of “division” in ℕ such that for any 𝑎, 𝑏 ∈ ℕ , 𝑎𝐷𝑏 iff 𝑎 divides 𝑏 and 𝑆12 is the set of all divisors of 12.

4 Marks
(c)
Let ⟨𝐿, ≤⟩ be a lattice. Show that for 𝑎, 𝑏, 𝑐 ∈ 𝐿, following inequalities holds.
i)𝑎 ⊕ (𝑏 ∗ 𝑐) ≤ (𝑎 ⊕ 𝑏) ∗ (𝑎 ⊕ 𝑐) and
ii)𝑎 ∗ (𝑏 ⊕ 𝑐) ≥ (𝑎 ∗ 𝑏) ⊕ (𝑎 ∗ 𝑐).
7 Marks
OR OPTION
(a)
Let the POSET (ρ(A), ≤) where A = {a, b, c}, relation is subset. Find
i)Upper bound of {{ }, {a}, {c}},
ii)GLB of {{ }, {a}, {c}}, if exist,
ii)LUB of {{ }, {a}, {c}}, if exist.
3 Marks
(b)
Solve 𝑎𝑛 = 𝑎𝑛−1 + 𝑎𝑛−2, 𝑎0 = 0, 𝑎1 = 1.
4 Marks
(c)

Given the relation matrices 𝑀𝑅 and 𝑀𝑆, find 𝑀𝑅∘𝑆, 𝑀𝑅̃ , 𝑀𝑆̃ , 𝑀𝑅∘𝑆 ̃ , and show that 𝑀𝑅∘𝑆 ̃ = 𝑀𝑆̃ ∘ 𝑀𝑅̃ . MR = [ 1 0 1 1 1 0 1 1 1 ] and MS = [ 1 0 0 1 0 1 0 1 0 1 0 0 1 1 0 ].

7 Marks

Question 5

14 MarksMedium
(a)
Define Isolated node, Binary tree and Regular graph.
3 Marks
(b)
Check whether the following graphs are isomorphic or not.
4 Marks
(c)

Define path matrix. Warshall's algorithm to obtain path matrix from the adjacency matrix of following graph

7 Marks
OR OPTION
(a)

A graph 𝐺 has 15 edges, 3 vertices of degree 4 and other vertices of degree 3. Find the number of vertices in 𝐺.

3 Marks
(b)
Find all the node base of the given digraph. Also find 𝑑(𝑉3, 𝑉6), 𝑑(𝑉6, 𝑉3).
4 Marks
(c)

Draw binary trees whose post-order produced the string d-e-c-g-j-h-f-b-l-n-q-r-p-m-k-a and pre-order produced the string a-b-d-h-e-i-j-c- f-g-k and in-order produced the string h-d-b-i-e-j-a-f-c-k-g.

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) (Summer 2024, 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