[go: up one dir, main page]
Scribd
Upload
116 views3 pages

DM Winter 2024

This document is an examination paper for the Discrete Mathematics course at Gujarat Technological University for the Winter 2024 semester. It includes various questions covering topics such as functions, relations, group theory, truth tables, and graph theory, with a total of 70 marks. Students are instructed to attempt all questions and make necessary assumptions, with the use of simple scientific calculators permitted.

Uploaded by

ayushmodi1910
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
116 views3 pages

DM Winter 2024

This document is an examination paper for the Discrete Mathematics course at Gujarat Technological University for the Winter 2024 semester. It includes various questions covering topics such as functions, relations, group theory, truth tables, and graph theory, with a total of 70 marks. Students are instructed to attempt all questions and make necessary assumptions, with the use of simple scientific calculators permitted.

Uploaded by

ayushmodi1910
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 3

Enrolment No.

/Seat No_______________

GUJARAT TECHNOLOGICAL UNIVERSITY


BE- SEMESTER–IV (NEW) EXAMINATION – WINTER 2024
Subject Code:3140708 Date:26-11-2024
Subject Name:Discrete Mathematics
Time:02:30 PM TO 05:00 PM Total Marks:70
Instructions:
1. Attempt all questions.
2. Make suitable assumptions wherever necessary.
3. Figures to the right indicate full marks.
4. Simple and non-programmable scientific calculators are allowed.

Marks
Q.1 (a) Define onto function. Check whether the function 𝑓: ℝ → ℝ 03
defined by 𝑓(𝑥) = 𝑥 2 is one-one and onto.
(b) For the relation R = {(1, 1), (1, 2), (2, 1), (2, 2), (3, 3), (4,4)} 04
on the set 𝐴 = {1,2,3,4}. Check whether it is reflexive, symmetric,
anti-symmetric, transitive.
(c) (i) A history class contains 8 male students and 6 female students. 03
Find the number 𝑛 of ways that the class can elect:
(a) 1 class representative (b) 2 class representatives, 1 male and 1
female (c) 1 president and 1 vice president.
(ii) Define elementary cycle, loop, tree and pendent vertex.
04
Q.2 (a) Show that if every element in a group is its own inverse, then the 03
group must be abelian.
(b) Identify the statement (𝑝 → 𝑞) ⇆ (¬𝑝⋁𝑞) is tautology or 04
contradiction.
(c) Use a truth table to determine whether the following argument form 07
is valid.
𝑝→𝑞
𝑞→𝑟
∴𝑝→𝑟
OR

(c) (i) Symbolize the following expressions 03


“𝑥 is the father of the mother of 𝑦”
where
𝑃(𝑥): 𝑥 is a person.
𝐹(𝑥, 𝑦): 𝑥 is the father of 𝑦.
𝑀(𝑥, 𝑦): 𝑥 is the mother of 𝑦.
04
(ii) Show that the premises “Everyone in this discrete mathematics
class has taken a course in computer science” and “Marla is a
student in this class” imply the conclusion “Marla has taken a
course in computer science.”

1
Q.3 (a) Define homomorphism. Let 𝐺 be the group of real numbers under 03
addition, and let 𝐺′ be the group of positive real numbers under
multiplication. Check whether the mapping 𝑓 ∶ 𝐺 → 𝐺′ defined by
𝑓(𝑎) = 2𝑎 is a homomorphism.

(b) Suppose that 100 mathematics students at a college taking at least 04


one of the languages French, German, and Russian, given the
following data:
65 study French, 45 study German, 42 study Russian, 20 study
French and German, 25 study French and Russian, 15 study German
and Russian.
(1) Find the number of students who study all the three languages.
(2) Find the number of students who study only French.
(c) (i) The subset 𝐻 = {0, 2} is a subgroup of (ℤ4 , +4). Is 𝐻 a normal 03
subgroup? 04
(ii) Let ℤ𝑚 denotes the integers modulo 𝑚. Check whether ℤ𝑚 is a
group under addition. If so, is it abelian group?
OR
Q.3 (a) Find all the generators of cyclic group (ℤ5 , +5). 03
(b) Prove that 𝐴 ∩ 𝐵̅ = 𝐴 ∩ 𝐶̅ if and only if 𝐴 ∩ 𝐵 = 𝐴 ∩ 𝐶. 04
(c) Consider the ring ℤ30 = {0, 1, 2, … ,29} of integers modulo 30. 07
(a) Find −8 and −17.
(b) Find 11−1 , 13−1 and 14−1 .
(c) Let 𝑓 (𝑥) = 2 𝑥 + 4. Find the roots of 𝑓(𝑥) over ℤ30 .

Q.4 (a) Let 𝐴 = {1, 2, 3, 4} and the relation 𝑅 = 03


{(1, 1), (1, 4), (4, 1), (4, 4), (2, 2), (2, 3), (3, 2), (3, 3)} on 𝐴. Write
the matrix of 𝑅 and check whether the relation is an equivalence.
(b) Let 𝑋 = {2, 3, 6, 12, 24, 36} and the relation ≤ be such that 𝑥 ≤ 04
𝑦 if 𝑥 divides 𝑦. Find
(i) Lower bound of {3,6},
(ii) Upper bound of {3,6},
(iii) GLB of {3,6}, if exist,
(iv) LUB of {3,6}, if exist.
(c) Solve the recurrence relation using the method of generating 07
function
𝑎𝑛 − 5 𝑎𝑛−1 + 6𝑎𝑛−2 = 3𝑛, 𝑛 ≥ 2, 𝑎0 = 0, 𝑎1 = 2.

OR

Q.4 (a) Let the relation 𝑅 = {(1, 2), (2, 3), (3, 3)} on 𝐴 = {1, 2, 3}. Find 03
the transitive closure of 𝑅.
(b) Solve 𝑎𝑛 = 2 𝑎𝑛−1 + 3𝑎𝑛−2 , 𝑎0 = 1, 𝑎1 = 2. 04
(c) Draw Hasse diagram of 〈𝑆30 , 𝐷〉. Prove that 〈𝑆30 , 𝐷〉 is a lattice, 07
where 𝐷 is the relation of “division” in ℕ such that for any 𝑎, 𝑏 ∈
ℕ, 𝑎𝐷𝑏 if and only if 𝑎 divides 𝑏 and 𝑆𝑛 , (𝑛 ∈ ℕ) is the set of all
divisors of 𝑛.

Q.5 (a) Find the number of edges in a 𝑟-regular graph with 𝑛 vertices. 03
2
(b) Check whether the following graphs are isomorphic or not. 04

(c) In which order does a pre-order, in-order and post-order traversal 07


visit the vertices of the ordered rooted tree shown in figure?

OR
Q.5 (a) A tree 𝑇 has 4 vertices of degree 2, 3 vertices of degree 3, 03
1 vertex of degree 4. Find the number of pendant vertices in the tree
𝑇.
(b) Find reachable set of each node of the given digraph. 04

(c) Define adjacency matrix. Use Warshall's algorithm to obtain path 07


matrix from the adjacency matrix of

*****

You might also like