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

E
USN
Third Semester B.E. Degree Examination, Dee.2019/Jan.2020
Discrete Mathematical Structures
Time: 3 hrs.

--- Content provided by FirstRanker.com ---

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

--- Content provided by FirstRanker.com ---

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.

--- Content provided by FirstRanker.com ---

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

--- Content provided by FirstRanker.com ---

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)]

--- Content provided by FirstRanker.com ---

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

--- Content provided by FirstRanker.com ---

(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.

--- Content provided by FirstRanker.com ---

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

--- Content provided by FirstRanker.com ---

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

--- Content provided by FirstRanker.com ---

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

--- Content provided by FirstRanker.com ---

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

--- Content provided by FirstRanker.com ---

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)

--- Content provided by FirstRanker.com ---

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.

--- Content provided by FirstRanker.com ---

(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]

--- Content provided by FirstRanker.com ---

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)

--- Content provided by FirstRanker.com ---

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

--- Content provided by FirstRanker.com ---

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)

--- Content provided by FirstRanker.com ---

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)

--- Content provided by FirstRanker.com ---

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

--- Content provided by FirstRanker.com ---

OR
4 a. If L0, Li,
L2
are Lucas numbers, then prove that L
n

--- Content provided by FirstRanker.com ---

=
(1+15
-
j
n

--- Content provided by FirstRanker.com ---

(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

--- Content provided by FirstRanker.com ---

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

--- Content provided by FirstRanker.com ---

y
2
z
3
and the number of distinct terms in the expansion of

--- Content provided by FirstRanker.com ---

(3x - 2y - 4z)
7
. (07 Marks)
Module-3
5 a.

--- Content provided by FirstRanker.com ---

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));

--- Content provided by FirstRanker.com ---

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)

--- Content provided by FirstRanker.com ---

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

--- Content provided by FirstRanker.com ---

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)

--- Content provided by FirstRanker.com ---

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

--- Content provided by FirstRanker.com ---

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)}

--- Content provided by FirstRanker.com ---

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)

--- Content provided by FirstRanker.com ---

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

--- Content provided by FirstRanker.com ---

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,

--- Content provided by FirstRanker.com ---

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

--- Content provided by FirstRanker.com ---

n
- 3a
n
i = 5 x 3" for n 1 given that ao= (07 Marks)
!sz'

--- Content provided by FirstRanker.com ---

2 of 3
LiBRg"\' l


FirstRanker.com - FirstRanker's Choice

--- Content provided by FirstRanker.com ---

E
USN
Third Semester B.E. Degree Examination, Dee.2019/Jan.2020
Discrete Mathematical Structures
Time: 3 hrs.

--- Content provided by FirstRanker.com ---

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

--- Content provided by FirstRanker.com ---

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.

--- Content provided by FirstRanker.com ---

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

--- Content provided by FirstRanker.com ---

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)]

--- Content provided by FirstRanker.com ---

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

--- Content provided by FirstRanker.com ---

(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.

--- Content provided by FirstRanker.com ---

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

--- Content provided by FirstRanker.com ---

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

--- Content provided by FirstRanker.com ---

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

--- Content provided by FirstRanker.com ---

are Lucas numbers, then prove that L
n
=
(1+15
-

--- Content provided by FirstRanker.com ---

j
n
(1_ /51"
2 2
. (06 Marks

--- Content provided by FirstRanker.com ---

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)

--- Content provided by FirstRanker.com ---

c. Find the coefficient of x
2
y
2
z

--- Content provided by FirstRanker.com ---

3
and the number of distinct terms in the expansion of
(3x - 2y - 4z)
7
. (07 Marks)

--- Content provided by FirstRanker.com ---

Module-3
5 a.
If f R -> R is defined by f(x) = x
2
+ 5, find f(-1); g2/3); 1

--- Content provided by FirstRanker.com ---

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

--- Content provided by FirstRanker.com ---

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)

--- Content provided by FirstRanker.com ---

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

--- Content provided by FirstRanker.com ---

- 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;

--- Content provided by FirstRanker.com ---

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

--- Content provided by FirstRanker.com ---

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}

--- Content provided by FirstRanker.com ---

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

--- Content provided by FirstRanker.com ---

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

--- Content provided by FirstRanker.com ---

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

--- Content provided by FirstRanker.com ---

\
recurrence relation a
n
- 3a
n

--- Content provided by FirstRanker.com ---

i = 5 x 3" for n 1 given that ao= (07 Marks)
!sz'
2 of 3
LiBRg"\' l

--- Content provided by FirstRanker.com ---

17CS/IS36
OR
8 a. Find the number of nonnegative integer solutions of the equation x
i

--- Content provided by FirstRanker.com ---

+ 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)

--- Content provided by FirstRanker.com ---

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

--- Content provided by FirstRanker.com ---

es in them. (06 Marks)
_
b.
State Handshaking property. Show that b S
2m

--- Content provided by FirstRanker.com ---

? < 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

--- Content provided by FirstRanker.com ---

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.

--- Content provided by FirstRanker.com ---

LIB RAF-;Y
CH KOD1 I
(07 Marks)

--- Content provided by FirstRanker.com ---

3 of 3
FirstRanker.com - FirstRanker's Choice