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

USN
?
7/ S CZN, D
: ' 1
Ilifl'

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

t
r
1
LIBRARY .",?
' ? ; -- --- ?

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

/,--,\' -.;
7
r
-.- \
CHIKOE:; .,-.:1, 15CS36

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

'
,
..,c
23
;?_____/:?)_i- i

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

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

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

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

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

p q
q -> (r A s)
?ir v(-itvu)
ISA t
.*. U

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

(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

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

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.

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

Anil is not in second semester. (05 Marks)
c. Let p(x) : x
2
- 7x + 10 = 0; q(x) = x
2

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

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

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

t:
Module-2
3 a. Prove by mathematical induction for any integer n 1.
1 1 1
2.5

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

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

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

(i) x
12
in the expansion of (1 - 2x)
1?
x

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

3

(ii) x
11
)1

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

4
in the expansion of (2x
3
-
3

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

xy
2
z
2
)

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

6
15
0
(iii) the constant term in the expansion of 3x
2

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

- -
2
x
(05 Marks)
if we want n

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

(05 Marks)
(06 Marks)
1 of 3
FirstRanker.com - FirstRanker's Choice
USN

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

?
7/ S CZN, D
: ' 1
Ilifl'
t

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

r
1
LIBRARY .",?
' ? ; -- --- ?
/,--,\' -.;

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

7
r
-.- \
CHIKOE:; .,-.:1, 15CS36
'

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

,
..,c
23
;?_____/:?)_i- i
Third Semester B.E. Degree Examination, Dec.20i9aan.2020

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

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

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

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

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

q -> (r A s)
?ir v(-itvu)
ISA t
.*. U
(05 Marks)

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

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.

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

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

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

c. Let p(x) : x
2
- 7x + 10 = 0; q(x) = x
2
- 2x - 3 = 0; r(x) = x < 0

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

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:

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

Module-2
3 a. Prove by mathematical induction for any integer n 1.
1 1 1
2.5
. +

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

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

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

12
in the expansion of (1 - 2x)
1?
x
3

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

(ii) x
11
)1
4

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

in the expansion of (2x
3
-
3
xy

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

2
z
2
)
6

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

15
0
(iii) the constant term in the expansion of 3x
2
- -

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

2
x
(05 Marks)
if we want n
(05 Marks)

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

(06 Marks)
1 of 3
15
OR
4 a.

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

b.
c.
Let a
n
=

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

positive
If L0,
LI,
L
=

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

In how
so that (i)
balls?
1, al = 2, a
2

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

integer n
L2, ........
are
(

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

1+ Jj
n

= 3 and
?

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

1/5
Lucas numbers,
a
n
= an_ i + an_ 2 + a _3 for n 3. Prove that a

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

n
5 3" for all
(05 Marks)
then prove that
n

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

(05 Marks)
distribute eight identical bulls into four distinct containers
empty? (ii) the fourth container contains an odd number cf
(06 Marks)
many ways

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

no container
2
can one
is left
Module-3

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

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

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

Let f : R ---->
f(x)
(i) f(-1)
that(hog)of=ho(gofi.
R be defined by

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

3x ?5 for x > 0
then find
?3x+1 for x5-0
(ii) f(5/3) (iii) f
-

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

'(3) (iv) f
-1
(-6) (iv) f
-1
([-5, 5]).

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

(05 Marks)
(05 Marks)
c.
Define partially ordered set. Draw the Hasse diagram representing the positive divisors
of 36.

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

(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

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

+3 }
(iii)1(x, y)/x, yeR, y
2
= x ; (iv) {(x, y)/x, yEQ, x
2

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

+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

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

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)

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

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

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

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

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

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)

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

c. Solve the recurrence relation:
= 3a
1
, + 5 x 7'
1

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

for n ?_ 0, give that a
n
= 2.
(06 Marks)
OR

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

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

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

FirstRanker.com - FirstRanker's Choice
USN
?
7/ S CZN, D
: ' 1

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

Ilifl'
t
r
1
LIBRARY .",?

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

' ? ; -- --- ?
/,--,\' -.;
7
r
-.- \

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

CHIKOE:; .,-.:1, 15CS36
'
,
..,c
23

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

;?_____/:?)_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.

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

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

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

b. Test the validity of the argument
p q
q -> (r A s)
?ir v(-itvu)
ISA t

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

.*. 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)

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

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

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

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

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

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)

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

(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

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

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?

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

c. Find the coefficient of
(i) x
12
in the expansion of (1 - 2x)
1?

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

x
3

(ii) x
11

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

)1
4
in the expansion of (2x
3
-

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

3
xy
2
z
2

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

)
6
15
0
(iii) the constant term in the expansion of 3x

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

2
- -
2
x
(05 Marks)

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

if we want n
(05 Marks)
(06 Marks)
1 of 3
15

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

OR
4 a.
b.
c.
Let a

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

n
=
positive
If L0,
LI,

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

L
=
In how
so that (i)
balls?

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

1, al = 2, a
2

integer n
L2, ........

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

are
(
1+ Jj
n

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

= 3 and
?
1/5
Lucas numbers,
a

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

n
= an_ i + an_ 2 + a _3 for n 3. Prove that a
n
5 3" for all
(05 Marks)

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

then prove that
n
(05 Marks)
distribute eight identical bulls into four distinct containers
empty? (ii) the fourth container contains an odd number cf

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

(06 Marks)
many ways
no container
2
can one

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

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

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

2
+2 , verify
Let f : R ---->
f(x)
(i) f(-1)

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

that(hog)of=ho(gofi.
R be defined by
3x ?5 for x > 0
then find
?3x+1 for x5-0

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

(ii) f(5/3) (iii) f
-
'(3) (iv) f
-1
(-6) (iv) f

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

-1
([-5, 5]).
(05 Marks)
(05 Marks)
c.

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

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

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

(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

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

= x ; (iv) {(x, y)/x, yEQ, x
2
+y
2
=1 } (05 Marks)

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

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.

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

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

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

(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

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

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

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

vacant chairs.
(05 Marks)
c. Solve the recurrence relation:
= 3a
1

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

, + 5 x 7'
1
for n ?_ 0, give that a
n
= 2.

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

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

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

b.
2 of 3
15CS36
b. Find the rook polynomial for the board in the Fig.Q8(b). Using expansion formula and
product formula.

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

(06 Marks)
1 2
3 4 5
6 7 8
Fig.Q8(b)

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

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)

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

Module-5
9 a. Define complete graph and complete bipartite graph. Hence draw
(i) Kuratowaski's first graph K
5
,

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

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

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

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?

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

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

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

c. Define tree and prove that tree with n vertices has n ? 1 edges.
(05 Marks)
(06 Marks)

3 of 3

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

FirstRanker.com - FirstRanker's Choice