PARALA MAHARAJA ENGINEERING COLLEGE

Registration No :

-- 2
Total Number of Pages : 02 02 3 Course: B.Tech
8/ 2 Sub_Code: RCS4C001

1 2 /0
09 -
4th Semester Regular/Back Examination: 2022-23
SUBJECT: Discrete Mathematics
1
BRANCH(S): CST,CSEAI,CSE,CSEAIME
Time : 3 Hour
Max Marks : 100
- 2
Q.Code : M218
-
2 0 23
Answer Question No.1 (Part-1) which is compulsory, any eight from Part-II and any two
from Part-III.
08 /
The figures in the right hand margin indicate marks.

1 2 /
Q1
1Answer 9-
0 the following questions:
Part-I
2 equivalent. (2 x 10)
a) Show that ∼ ∀x P(x) → Q(x) and ∃𝑥 𝑃(𝑥) ∧∼ 𝑄(𝑥) are logically
3 - -
b) Let 𝐶 be “Today is clear”, 𝑅 be “It is raining today” and 2
Then translate the symbolic notation 𝐶 → ¬(𝑅⋀𝑆)/into
0 𝑆 be “It is snowing today”.
2 acceptable English.
c) Using induction, show that 1 + 2 + 3 + ⋯ 𝑛 /=0
8
( )

- 2 .
1 example of it.
d) Define Partial order set. Also provide suitable
e) Suppose A = {1,2,3,4}. Which order
1 9
0 pair(s) are in the relation
R = {(a, b) | a divides b}?
f) Solve the recurrence relation 𝑎 = 6 𝑎
g) Give an example of an abelian group which - 2
−9𝑎 .
- has exactly 4 elements.
h) Define Lattice. 2 3
0 is remain a simple graph after removing its
2
i) Prove or disprove that a simple/digraph
8
direction. / 0
2be there in a planar graph having 7 regions and 5 vertices?
j) How many edges must
- 1
1 09 Part-II
- - 2
Q2 Only Focused-Short Answer Type Questions- (Answer Any2Eight
2 3 out of (6 × 8)
Twelve) -- 0
2
a) Translate 3 8 /
the statement “If either labor or management is stubborn,
2 then the strike
/ 2 0be settled 𝑖𝑓𝑓 the government obtains an injuction,2but
will /0troops are not sent into
/ 0 8 the mills. ’’ in symbolic form. Also construct its9truth
- 1 table.
- 1 2 b) Prove or disprove that every partial order sets10are totally ordered.
109 c) Solve the recurrence relation 𝑎 = 6𝑎 − 9𝑎 with the initial conditions
𝑎 = 1, 𝑎 = 6.
d) Use mathematical induction to prove that 𝑛 − 𝑛 is divisible by 3 whenever 𝑛 is a
positive integer.
e) Students are awarded 4 grades A, B, C, and D. How many students must be there in
a group so that at least 6 students get the same grade?
f) Let 𝑅 be the relation on the set of real numbers such that 𝑎𝑅𝑏 iff 𝑎 − 𝑏 is an
 integer. Is 𝑅 an equivalence relation? Justify your answer.
g)
-- 2
Find the particular solution of the recurrence relation an  5an 1  6 an  2  3n 2 .
h)
i) 02 3
State Lagrange’s theorem. Also discuss the converse of the theorem.
Find all the distinct left cosets of 𝐻 = 5ℤ in the group (ℤ, +).
j)
8/ 2
Explain Boolean algebra with the help of an example.
k)
2 /0
If 𝐺 is minimally connected then prove that 𝐺 is a tree.
1
l) -
Prove or disprove that there is no connected Eulerian simple graph that has even
09
number of vertices and odd number of edges.
1
Part-III
Only Long Answer Type Questions (Answer Any Two out of Four)
- - 2
Q3 2 3 principle. Students are awarded 4 grades
a) Define generalized Pigeon-hole
0 (8x2)
A, B, C, and D./2 How many students must be there in a group so that at least 6
/ 8
students get0the same grade?

-
b) Solve1 2
the following recurrence relation using generating function
9
10 𝑎 − 2𝑎 − 15𝑎 = 0, for 𝑛 ≥ 2 and 𝑎 = 0,-𝑎-2= 1.
Q4
0
a) What is a Tautology? Construct the truth table of (𝑃 →2 3𝑄⋀𝑅)⋁(¬𝑃⋀𝑄). (8x2)

8 /
b) In a distributive lattice, show that if an element
2 has a complement, then this
complement is unique. 2 / 0
9 - 1
Q5 Define integral domain. Show that0every field is an integral domain but converse is (16)
1
not true. When an integral domain becomes a field? Explain the answer in details.

Q6 a) Show that a graph - - 2

is connected iff it has a spanning tree. (8x2)
2 3
b) Prove that every plannar graph0
8 / 2 is 6-vertex colorable.

2 / 0
9 - 1
10 3 -- 2
- - 2 2 02
0 2 3 8/
/ 2 2 /0
/ 0 8 9 - 1
- 1 2 1 0
109