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

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

USN
?
7/ S CZN, D
: ' 1
Ilifl'
t
r
1
LIBRARY .",?
' ? ; -- --- ?
/,--,\' -.;
7
r
-.- \
CHIKOE:; .,-.:1, 15CS36
'
,
..,c
23
;?_____/:?)_i- i
Third Semester B.E. Degree Examination, Dec.20i9aan.2020
Discrete Mathematical Structures
Time: 3 hrs. Max. Marks: 80
Note: Answer any FIVE full questions, choosing ONE full question from each module.
Module-1
Prove that the compound proposition
is tautology. (05 Marks)
1 a. Define tautology and contradiction.
[(p -> q)v(p r) 4-> [p (q v r)]
b. Test the validity of the argument
p q
q -> (r A s)
?ir v(-itvu)
ISA t
.*. U
(05 Marks)
c.
Give (i) direct proof, (ii) indirect proof and (iii) Proof by contradiction, for the statement
"Square of an odd integer, is an odd integer". (06 Marks)
OR
2 a. Prove the following logical equivalence without using truth table.
(p -> q) n [--,q n (r v 4-> v q) (05 Marks)
b. Establish the validity of the argument using the rules of inferences.
No engineering student of first or second semester studies Logic
Anil is an engineering student who studies logic.
Anil is not in second semester. (05 Marks)
c. Let p(x) : x
2
- 7x + 10 = 0; q(x) = x
2
- 2x - 3 = 0; r(x) = x < 0
Determine the truth value of the following statements, if universe contains only the integers
2 and 5.
(i) Vx, p(x) -,r(x) (ii) Vx, q(x) r(x)
(iii) 3x, p(x) -> r(x) (iv) 3x, q(x) --> r(x) (06 Marks)
t:
Module-2
3 a. Prove by mathematical induction for any integer n 1.
1 1 1
2.5
. +
5.8 ....................(3n -1)(3n + 2) 6n + 4
b. How many positive integers n can be formed using the digits 3, 4, 4, 5, 5, 6, 7
to exceed 50,00,000?
c. Find the coefficient of
(i) x
12
in the expansion of (1 - 2x)
1?
x
3

(ii) x
11
)1
4
in the expansion of (2x
3
-
3
xy
2
z
2
)
6
15
0
(iii) the constant term in the expansion of 3x
2
- -
2
x
(05 Marks)
if we want n
(05 Marks)
(06 Marks)
1 of 3
FirstRanker.com - FirstRanker's Choice
USN
?
7/ S CZN, D
: ' 1
Ilifl'
t
r
1
LIBRARY .",?
' ? ; -- --- ?
/,--,\' -.;
7
r
-.- \
CHIKOE:; .,-.:1, 15CS36
'
,
..,c
23
;?_____/:?)_i- i
Third Semester B.E. Degree Examination, Dec.20i9aan.2020
Discrete Mathematical Structures
Time: 3 hrs. Max. Marks: 80
Note: Answer any FIVE full questions, choosing ONE full question from each module.
Module-1
Prove that the compound proposition
is tautology. (05 Marks)
1 a. Define tautology and contradiction.
[(p -> q)v(p r) 4-> [p (q v r)]
b. Test the validity of the argument
p q
q -> (r A s)
?ir v(-itvu)
ISA t
.*. U
(05 Marks)
c.
Give (i) direct proof, (ii) indirect proof and (iii) Proof by contradiction, for the statement
"Square of an odd integer, is an odd integer". (06 Marks)
OR
2 a. Prove the following logical equivalence without using truth table.
(p -> q) n [--,q n (r v 4-> v q) (05 Marks)
b. Establish the validity of the argument using the rules of inferences.
No engineering student of first or second semester studies Logic
Anil is an engineering student who studies logic.
Anil is not in second semester. (05 Marks)
c. Let p(x) : x
2
- 7x + 10 = 0; q(x) = x
2
- 2x - 3 = 0; r(x) = x < 0
Determine the truth value of the following statements, if universe contains only the integers
2 and 5.
(i) Vx, p(x) -,r(x) (ii) Vx, q(x) r(x)
(iii) 3x, p(x) -> r(x) (iv) 3x, q(x) --> r(x) (06 Marks)
t:
Module-2
3 a. Prove by mathematical induction for any integer n 1.
1 1 1
2.5
. +
5.8 ....................(3n -1)(3n + 2) 6n + 4
b. How many positive integers n can be formed using the digits 3, 4, 4, 5, 5, 6, 7
to exceed 50,00,000?
c. Find the coefficient of
(i) x
12
in the expansion of (1 - 2x)
1?
x
3

(ii) x
11
)1
4
in the expansion of (2x
3
-
3
xy
2
z
2
)
6
15
0
(iii) the constant term in the expansion of 3x
2
- -
2
x
(05 Marks)
if we want n
(05 Marks)
(06 Marks)
1 of 3
15
OR
4 a.
b.
c.
Let a
n
=
positive
If L0,
LI,
L
=
In how
so that (i)
balls?
1, al = 2, a
2

integer n
L2, ........
are
(
1+ Jj
n

= 3 and
?
1/5
Lucas numbers,
a
n
= an_ i + an_ 2 + a _3 for n 3. Prove that a
n
5 3" for all
(05 Marks)
then prove that
n
(05 Marks)
distribute eight identical bulls into four distinct containers
empty? (ii) the fourth container contains an odd number cf
(06 Marks)
many ways
no container
2
can one
is left
Module-3
5 a. Let f, g, h be functions from R to R defined by f(x) = x
2
, g(x) = x + 5, h(x) =Vx
2
+2 , verify
Let f : R ---->
f(x)
(i) f(-1)
that(hog)of=ho(gofi.
R be defined by
3x ?5 for x > 0
then find
?3x+1 for x5-0
(ii) f(5/3) (iii) f
-
'(3) (iv) f
-1
(-6) (iv) f
-1
([-5, 5]).
(05 Marks)
(05 Marks)
c.
Define partially ordered set. Draw the Hasse diagram representing the positive divisors
of 36.
(06 Marks)
OR
6 a. Determine the following relations are functions or not. If relation is function, find its range
(i) {(x, y)/x, yez, y = 3x+1 } ; (ii) {(x, y)/x, yez, y = x
2
+3 }
(iii)1(x, y)/x, yeR, y
2
= x ; (iv) {(x, y)/x, yEQ, x
2
+y
2
=1 } (05 Marks)
b. State the Pigeonhole principle and generalization of the pigeonhole principle. Prove that if
30 dictionaries in a library contains a total of 61,327 pages, then at least one of the
dictionaries must have at least 2045 pages.
(05 Marks)
c.
Let A = {1, 2, 3, 4, 6} and R be a relation on A defined by aRb if and only if a is a multiple
of b. Represent the relation R as matrix and draw its digraph. (06 Marks)
Module-4
7 a. Determine the number of positive integers n, such that 1 5_ n 5 300, and n is
(i) not divisible by 5, 6, 8
(ii) divisible by at least one of 5, 6, 8 (05 Marks)
b. Four persons P1,1
3,
, P3, P4 who arrive late for a dinner party, find that only one chair at each
of five tables T1, T2, T3, T
4
, T5 is vacant. P1 will not sit T1 or T2 , P2 will not sit at T
2
, P3 will
not sit at T3 or T4 and P4 will not sit at T4 or Ts. Find the number of way they can occupy the
vacant chairs.
(05 Marks)
c. Solve the recurrence relation:
= 3a
1
, + 5 x 7'
1
for n ?_ 0, give that a
n
= 2.
(06 Marks)
OR
8 a. Find the number of permutations of the digits 1 through 9 in which the blocks 36. 78, 672 do
not appear.
(06 Marks)
b.
2 of 3
FirstRanker.com - FirstRanker's Choice
USN
?
7/ S CZN, D
: ' 1
Ilifl'
t
r
1
LIBRARY .",?
' ? ; -- --- ?
/,--,\' -.;
7
r
-.- \
CHIKOE:; .,-.:1, 15CS36
'
,
..,c
23
;?_____/:?)_i- i
Third Semester B.E. Degree Examination, Dec.20i9aan.2020
Discrete Mathematical Structures
Time: 3 hrs. Max. Marks: 80
Note: Answer any FIVE full questions, choosing ONE full question from each module.
Module-1
Prove that the compound proposition
is tautology. (05 Marks)
1 a. Define tautology and contradiction.
[(p -> q)v(p r) 4-> [p (q v r)]
b. Test the validity of the argument
p q
q -> (r A s)
?ir v(-itvu)
ISA t
.*. U
(05 Marks)
c.
Give (i) direct proof, (ii) indirect proof and (iii) Proof by contradiction, for the statement
"Square of an odd integer, is an odd integer". (06 Marks)
OR
2 a. Prove the following logical equivalence without using truth table.
(p -> q) n [--,q n (r v 4-> v q) (05 Marks)
b. Establish the validity of the argument using the rules of inferences.
No engineering student of first or second semester studies Logic
Anil is an engineering student who studies logic.
Anil is not in second semester. (05 Marks)
c. Let p(x) : x
2
- 7x + 10 = 0; q(x) = x
2
- 2x - 3 = 0; r(x) = x < 0
Determine the truth value of the following statements, if universe contains only the integers
2 and 5.
(i) Vx, p(x) -,r(x) (ii) Vx, q(x) r(x)
(iii) 3x, p(x) -> r(x) (iv) 3x, q(x) --> r(x) (06 Marks)
t:
Module-2
3 a. Prove by mathematical induction for any integer n 1.
1 1 1
2.5
. +
5.8 ....................(3n -1)(3n + 2) 6n + 4
b. How many positive integers n can be formed using the digits 3, 4, 4, 5, 5, 6, 7
to exceed 50,00,000?
c. Find the coefficient of
(i) x
12
in the expansion of (1 - 2x)
1?
x
3

(ii) x
11
)1
4
in the expansion of (2x
3
-
3
xy
2
z
2
)
6
15
0
(iii) the constant term in the expansion of 3x
2
- -
2
x
(05 Marks)
if we want n
(05 Marks)
(06 Marks)
1 of 3
15
OR
4 a.
b.
c.
Let a
n
=
positive
If L0,
LI,
L
=
In how
so that (i)
balls?
1, al = 2, a
2

integer n
L2, ........
are
(
1+ Jj
n

= 3 and
?
1/5
Lucas numbers,
a
n
= an_ i + an_ 2 + a _3 for n 3. Prove that a
n
5 3" for all
(05 Marks)
then prove that
n
(05 Marks)
distribute eight identical bulls into four distinct containers
empty? (ii) the fourth container contains an odd number cf
(06 Marks)
many ways
no container
2
can one
is left
Module-3
5 a. Let f, g, h be functions from R to R defined by f(x) = x
2
, g(x) = x + 5, h(x) =Vx
2
+2 , verify
Let f : R ---->
f(x)
(i) f(-1)
that(hog)of=ho(gofi.
R be defined by
3x ?5 for x > 0
then find
?3x+1 for x5-0
(ii) f(5/3) (iii) f
-
'(3) (iv) f
-1
(-6) (iv) f
-1
([-5, 5]).
(05 Marks)
(05 Marks)
c.
Define partially ordered set. Draw the Hasse diagram representing the positive divisors
of 36.
(06 Marks)
OR
6 a. Determine the following relations are functions or not. If relation is function, find its range
(i) {(x, y)/x, yez, y = 3x+1 } ; (ii) {(x, y)/x, yez, y = x
2
+3 }
(iii)1(x, y)/x, yeR, y
2
= x ; (iv) {(x, y)/x, yEQ, x
2
+y
2
=1 } (05 Marks)
b. State the Pigeonhole principle and generalization of the pigeonhole principle. Prove that if
30 dictionaries in a library contains a total of 61,327 pages, then at least one of the
dictionaries must have at least 2045 pages.
(05 Marks)
c.
Let A = {1, 2, 3, 4, 6} and R be a relation on A defined by aRb if and only if a is a multiple
of b. Represent the relation R as matrix and draw its digraph. (06 Marks)
Module-4
7 a. Determine the number of positive integers n, such that 1 5_ n 5 300, and n is
(i) not divisible by 5, 6, 8
(ii) divisible by at least one of 5, 6, 8 (05 Marks)
b. Four persons P1,1
3,
, P3, P4 who arrive late for a dinner party, find that only one chair at each
of five tables T1, T2, T3, T
4
, T5 is vacant. P1 will not sit T1 or T2 , P2 will not sit at T
2
, P3 will
not sit at T3 or T4 and P4 will not sit at T4 or Ts. Find the number of way they can occupy the
vacant chairs.
(05 Marks)
c. Solve the recurrence relation:
= 3a
1
, + 5 x 7'
1
for n ?_ 0, give that a
n
= 2.
(06 Marks)
OR
8 a. Find the number of permutations of the digits 1 through 9 in which the blocks 36. 78, 672 do
not appear.
(06 Marks)
b.
2 of 3
15CS36
b. Find the rook polynomial for the board in the Fig.Q8(b). Using expansion formula and
product formula.
(06 Marks)
1 2
3 4 5
6 7 8
Fig.Q8(b)
c. If are = 0, al = 1, a2 = 4 and a3 = 37, satisfy the recurrence relation
an+
,
+ + ca? = 0 for n 0,
determine the constants b and c and then solve the relation for an . (04 Marks)
Module-5
9 a. Define complete graph and complete bipartite graph. Hence draw
(i) Kuratowaski's first graph K
5
,
(ii) Kuratowaski's second graph K33
(iii) 3-regular graph with 8 vertices.
(05 Marks)
b. Discuss the solution of Kongsberg bridge problem.
(05 Marks)
c. Obtain an optimal prefix code for the message LETTER RECEIVED. Indicate the code.
(06 Marks)
OR
10 a. State Handshaking property, how many vertices will a graphs have, if they contain
(i) 16 edges and all vertices of degree 4?
(ii) 21 edges, 3 vertices of degree 4 and other vertices of degree 3?
(iii) 12 edges, 6 vertices of degree 3 and other vertices of degree less than 3. (05 Marks)
b. Define isomorphism of two graphs. Show that following pair of graphs are isomorphic.
[Refer Fig.Q10(b)].
Fig.Q10(b)
c. Define tree and prove that tree with n vertices has n ? 1 edges.
(05 Marks)
(06 Marks)

3 of 3
FirstRanker.com - FirstRanker's Choice