Download VTU BE 2020 Jan CSE Question Paper 17 Scheme 3rd Sem Discrete Mathematical Structures

Download Visvesvaraya Technological University (VTU) BE ( Bachelor of Engineering) CSE 2017 Scheme 2020 January Previous Question Paper 3rd Sem Discrete Mathematical Structures

E
USN
Third Semester B.E. Degree Examination, Dee.2019/Jan.2020
Discrete Mathematical Structures
Time: 3 hrs.
Max. Marks: 100
Note: Answer any FIVE full questions, choosing
ONE full question from each module.
Module-1
1 a. Define tautology and contradiction. Prove that for any propositions p, q, r the compound
proposition 1p n (p n r) ----> s} ---> (r --> s) is tautology.
(06 Marks)
b. Establish the validity of the argument: If A get the superwiser's position and work hard, then
he will get raise.
If he gets a raise, then he will buy a new car.
He has not bought a new car.
Therefore, he does not get a superwiser's position or he did not work hard.
(07 Marks)
c.
Determine the truth value of each of the following quantified statements; if the universe
being the set of all non-zero integers.
i) 3x, 3y [xy = 2]
ii) 3x, Vy [xy = 2]
iii) Vx, 3y [xy = 2]
iv) 3x, 3y, [(3x + y = 8) A (2X ? y = 7)]
v) 3x, 3y [(4x + 2y = 3) n (x ? y = 1 )1
(07 Marks)
OR
2 a. Define dual of a logical statement and prove the logical equivalence using laws of logic
[(--ipvq)A(pn(pAq))]apAq
(06 Marks)
b. Establish the validity of the argument : All Engineering students study physics. All
engineering students of computer science study logic.
Ravi is an engineering student who does not study logic
Sachin studies logic but does not study physics.
Therefore, Ravi is not a student of computer science and Sachin is not an engineering
student. (07 Marks)
c. Give: i) Direct proof ii) Indirect proof and "If n is an odd integer, then n + 7 is an even
integer". (07 Marks)
Module-2
3 a. Prove that every positive integer greater than or equal to 14 may be written as sum of 3's
and /or 8's. (06 Marks)
b. Find the number of arrangements of all the letters in TALLAHASSEE. How many of these
arrangements have no adjacent A's? (07 Marks)
c. In how many ways can one distribute eight identical balls into four distinct containers so that
i) No container is left empty ii) the fourth container gets an odd number of balls. (07 Marks)
1 of 3
FirstRanker.com - FirstRanker's Choice
E
USN
Third Semester B.E. Degree Examination, Dee.2019/Jan.2020
Discrete Mathematical Structures
Time: 3 hrs.
Max. Marks: 100
Note: Answer any FIVE full questions, choosing
ONE full question from each module.
Module-1
1 a. Define tautology and contradiction. Prove that for any propositions p, q, r the compound
proposition 1p n (p n r) ----> s} ---> (r --> s) is tautology.
(06 Marks)
b. Establish the validity of the argument: If A get the superwiser's position and work hard, then
he will get raise.
If he gets a raise, then he will buy a new car.
He has not bought a new car.
Therefore, he does not get a superwiser's position or he did not work hard.
(07 Marks)
c.
Determine the truth value of each of the following quantified statements; if the universe
being the set of all non-zero integers.
i) 3x, 3y [xy = 2]
ii) 3x, Vy [xy = 2]
iii) Vx, 3y [xy = 2]
iv) 3x, 3y, [(3x + y = 8) A (2X ? y = 7)]
v) 3x, 3y [(4x + 2y = 3) n (x ? y = 1 )1
(07 Marks)
OR
2 a. Define dual of a logical statement and prove the logical equivalence using laws of logic
[(--ipvq)A(pn(pAq))]apAq
(06 Marks)
b. Establish the validity of the argument : All Engineering students study physics. All
engineering students of computer science study logic.
Ravi is an engineering student who does not study logic
Sachin studies logic but does not study physics.
Therefore, Ravi is not a student of computer science and Sachin is not an engineering
student. (07 Marks)
c. Give: i) Direct proof ii) Indirect proof and "If n is an odd integer, then n + 7 is an even
integer". (07 Marks)
Module-2
3 a. Prove that every positive integer greater than or equal to 14 may be written as sum of 3's
and /or 8's. (06 Marks)
b. Find the number of arrangements of all the letters in TALLAHASSEE. How many of these
arrangements have no adjacent A's? (07 Marks)
c. In how many ways can one distribute eight identical balls into four distinct containers so that
i) No container is left empty ii) the fourth container gets an odd number of balls. (07 Marks)
1 of 3
OR
4 a. If L0, Li,
L2
are Lucas numbers, then prove that L
n
=
(1+15
-
j
n
(1_ /51"
2 2
. (06 Marks
b. A question paper contains 10 questions of which 7 are to be answered. In how many ways a
student can select the 7 questions
i) If he can choose any seven?
ii) If he should select three questions from first five and four questions from the last five?
iii) If he should select at least three from the first five? (07 Marks)
c. Find the coefficient of x
2
y
2
z
3
and the number of distinct terms in the expansion of
(3x - 2y - 4z)
7
. (07 Marks)
Module-3
5 a.
If f R -> R is defined by f(x) = x
2
+ 5, find f(-1); g2/3); 1
1
(1); f'([6, 10]); 1([-4, 5));
f 5]).
(06 Marks)
b. State Pigeonhole principle. ABC is an equilateral triangle whose sides are of length 3cm
each. If we select 10 points inside the triangle, prove that at least two of these points are
such that the distance between them is less than lcm. (07 Marks)
c. ,' Let A = II, 2, 3, 4, 51. Define a relation R on A x A by (xi, yi) R(x2, y,) if and one if
+ yi = x2 + y2. Then verify that R is an equivalence relation on A x A and hence find d_
equivalence classes [(1, 3)], [(2, 4)] and [(I, 1)]. (07 Marks)
OR
6 a. LetA=B= R, the set of all real numbers, and the functions f : A -> B and g : B -> A be
I3
defined by f(x) = 2x
3
- I, V x E A; g(y)= (y+ l) , V yE B . Show that each of f and g
is the inverse of the other. (06 Marks)
b. Define one-to-one function and on to function. Determine in each of the following cases
where f is one-to-one or onto or both or neither [f : A -> B].
i) A = B = 11, 2, 3, 41;
f= 1( 1, 1), (2, 3), (3, 4), (4, 2)}
ii) A= 1a, b, cl, B= 11, 2, 3, 41
f= 1(a, 1), (b, 1), (c, 3)1
iii) A= {1, 2,3},B= 11,2,3,4,51
f= 1(1, 1), (
2
, 3), (3, 4)}
iv) A= 11, 2,31,B= 11,2,3, 4,5)
f= 1(1, 1), (2, 3), (3, 3)}
v) A = 11, 2, 3, 41, B = {a, b, c, d}
f = 1(1, a) (2, a), (3, d), (4, c)1 (07 Marks)
c. Draw Hasse diagram representing the positive divisors of 36. (07 Marks)
Module-4
7 a.
Determine the number of positive integers n such that 1 n 300 and n is not divisible by
5, 6, 8 and divisible by at least one of 5, 6, 8. (06 Marks)
b. Four persons P1, P2, P3. P4 who arrive late for a dinner party, find that only one chair at each
of five tables T1, T2, T3, T4 and T5 is vacant, Pi will not sit at T, or
-
1,, 1
3
, will not sit at T2,
P3 will not sit at T3 or T4 and P4 will not sit at T4 or T5. Find the number of ways they can
occupy the vacant chair. (07 Marks)
c. Define Homogeneous and non-homogeneous recurrence relations er and solve the
\
recurrence relation a
n
- 3a
n
i = 5 x 3" for n 1 given that ao= (07 Marks)
!sz'
2 of 3
LiBRg"\' l


FirstRanker.com - FirstRanker's Choice
E
USN
Third Semester B.E. Degree Examination, Dee.2019/Jan.2020
Discrete Mathematical Structures
Time: 3 hrs.
Max. Marks: 100
Note: Answer any FIVE full questions, choosing
ONE full question from each module.
Module-1
1 a. Define tautology and contradiction. Prove that for any propositions p, q, r the compound
proposition 1p n (p n r) ----> s} ---> (r --> s) is tautology.
(06 Marks)
b. Establish the validity of the argument: If A get the superwiser's position and work hard, then
he will get raise.
If he gets a raise, then he will buy a new car.
He has not bought a new car.
Therefore, he does not get a superwiser's position or he did not work hard.
(07 Marks)
c.
Determine the truth value of each of the following quantified statements; if the universe
being the set of all non-zero integers.
i) 3x, 3y [xy = 2]
ii) 3x, Vy [xy = 2]
iii) Vx, 3y [xy = 2]
iv) 3x, 3y, [(3x + y = 8) A (2X ? y = 7)]
v) 3x, 3y [(4x + 2y = 3) n (x ? y = 1 )1
(07 Marks)
OR
2 a. Define dual of a logical statement and prove the logical equivalence using laws of logic
[(--ipvq)A(pn(pAq))]apAq
(06 Marks)
b. Establish the validity of the argument : All Engineering students study physics. All
engineering students of computer science study logic.
Ravi is an engineering student who does not study logic
Sachin studies logic but does not study physics.
Therefore, Ravi is not a student of computer science and Sachin is not an engineering
student. (07 Marks)
c. Give: i) Direct proof ii) Indirect proof and "If n is an odd integer, then n + 7 is an even
integer". (07 Marks)
Module-2
3 a. Prove that every positive integer greater than or equal to 14 may be written as sum of 3's
and /or 8's. (06 Marks)
b. Find the number of arrangements of all the letters in TALLAHASSEE. How many of these
arrangements have no adjacent A's? (07 Marks)
c. In how many ways can one distribute eight identical balls into four distinct containers so that
i) No container is left empty ii) the fourth container gets an odd number of balls. (07 Marks)
1 of 3
OR
4 a. If L0, Li,
L2
are Lucas numbers, then prove that L
n
=
(1+15
-
j
n
(1_ /51"
2 2
. (06 Marks
b. A question paper contains 10 questions of which 7 are to be answered. In how many ways a
student can select the 7 questions
i) If he can choose any seven?
ii) If he should select three questions from first five and four questions from the last five?
iii) If he should select at least three from the first five? (07 Marks)
c. Find the coefficient of x
2
y
2
z
3
and the number of distinct terms in the expansion of
(3x - 2y - 4z)
7
. (07 Marks)
Module-3
5 a.
If f R -> R is defined by f(x) = x
2
+ 5, find f(-1); g2/3); 1
1
(1); f'([6, 10]); 1([-4, 5));
f 5]).
(06 Marks)
b. State Pigeonhole principle. ABC is an equilateral triangle whose sides are of length 3cm
each. If we select 10 points inside the triangle, prove that at least two of these points are
such that the distance between them is less than lcm. (07 Marks)
c. ,' Let A = II, 2, 3, 4, 51. Define a relation R on A x A by (xi, yi) R(x2, y,) if and one if
+ yi = x2 + y2. Then verify that R is an equivalence relation on A x A and hence find d_
equivalence classes [(1, 3)], [(2, 4)] and [(I, 1)]. (07 Marks)
OR
6 a. LetA=B= R, the set of all real numbers, and the functions f : A -> B and g : B -> A be
I3
defined by f(x) = 2x
3
- I, V x E A; g(y)= (y+ l) , V yE B . Show that each of f and g
is the inverse of the other. (06 Marks)
b. Define one-to-one function and on to function. Determine in each of the following cases
where f is one-to-one or onto or both or neither [f : A -> B].
i) A = B = 11, 2, 3, 41;
f= 1( 1, 1), (2, 3), (3, 4), (4, 2)}
ii) A= 1a, b, cl, B= 11, 2, 3, 41
f= 1(a, 1), (b, 1), (c, 3)1
iii) A= {1, 2,3},B= 11,2,3,4,51
f= 1(1, 1), (
2
, 3), (3, 4)}
iv) A= 11, 2,31,B= 11,2,3, 4,5)
f= 1(1, 1), (2, 3), (3, 3)}
v) A = 11, 2, 3, 41, B = {a, b, c, d}
f = 1(1, a) (2, a), (3, d), (4, c)1 (07 Marks)
c. Draw Hasse diagram representing the positive divisors of 36. (07 Marks)
Module-4
7 a.
Determine the number of positive integers n such that 1 n 300 and n is not divisible by
5, 6, 8 and divisible by at least one of 5, 6, 8. (06 Marks)
b. Four persons P1, P2, P3. P4 who arrive late for a dinner party, find that only one chair at each
of five tables T1, T2, T3, T4 and T5 is vacant, Pi will not sit at T, or
-
1,, 1
3
, will not sit at T2,
P3 will not sit at T3 or T4 and P4 will not sit at T4 or T5. Find the number of ways they can
occupy the vacant chair. (07 Marks)
c. Define Homogeneous and non-homogeneous recurrence relations er and solve the
\
recurrence relation a
n
- 3a
n
i = 5 x 3" for n 1 given that ao= (07 Marks)
!sz'
2 of 3
LiBRg"\' l


17CS/IS36
OR
8 a. Find the number of nonnegative integer solutions of the equation x
i
+ x2 + x3 + x4 = 18
under the condition x, 5 7, for i = 1, 2, 3, 4. (06 Marks)
b. Define derangements and determine the rook polynomial of the board in Fig.Q.8(b) using
expansion formula by selecting square 1 as ? (07 Marks)
Fig.Q.8(b)
c. Solve the recurrence relation a? = a?_1 + al = 1, a, = 3. (07 Marks)
Module-5
9 a. Define complete graph and complete bipartite graph. Draw Kuratowski's first graph K5 and
second graph K3,3 and hence find the number of ed
g
es in them. (06 Marks)
_
b.
State Handshaking property. Show that b S
2m
? < A , for a given graph with n vertices and in
edges, if 6 is the minimum and A is the maximum of the degree of vertices. (07 Marks)
c. Obtain an optimal prifix code for the message MISSION SUCCESSFUL. Indicate the code
and find the optimal weight. (07 Marks)
OR
10 a. Define circuit and Euler circuit in graphs and discuss the solution of Konigsberg bridge
problem. (06 Marks)
b. Define isomorphism. Verify the two graphs are isomorphic in Fig.Q.l0(b). (07 Marks)
Fig.Q.10(b)
c. Define tree and show that a tree with n vertices has n ? I edges.
LIB RAF-;Y
CH KOD1 I
(07 Marks)


3 of 3
FirstRanker.com - FirstRanker's Choice