Download Visvesvaraya Technological University (VTU) BE ( Bachelor of Engineering) CSE 2018 Scheme 2020 January Previous Question Paper 3rd Sem SCS36 Discrete Mathematical Structures
( f
:14?
1E'
SCS36
Third Semester B.F. Degree Examination, Dec.200MAif:2020
Discrete Mathematical Structures
Time: 3 hrs. Max. Marks: 100
Note: Answer FIVE full questions, choosing ONE full question from each module.
.....
t
o
1 a. Prove that, for any propositions p, q, r the compound proposition
Module-1
E.
[(p ---> q) A (q ?> r) --> (p --> r)] is a tautology. (06 Marks)
b. Test the validity of the following argument.
-0
If I study, 1 will not fail in the examination.
If I do not watch TV in the evenings, I will study.
(
,
3
A
ci 7,
. ,,,, I failed in the examination.
cz ?
.--
.--' 6
.
... I must have watched TV in the evenings (07 Marks)
to II
44
.
1,]: kr)
I
C. Let p(x) : x
2
?7x +10 =0 , q(x) : x
2
?2x +3 --- - 0, r(x): x < 0. Find the truth or falsity of
00 =
;:- - +
the following statements, when the universe U contains only the integers 2 and 5,
.
m
._ c-.1
-t
E ,b
P v (i) Vx,p(x) ?> ?r(x) (ii) Vx , q(x)?>r(x)
(iii) 3x , q(x)-->r(x) (iv) ]x,p(x) ?>r(x)
!,. .. .7.. .
(07 Marks)
0
,,
a.: OR
.- .
..., .0
ii,
2 a. Prove that, for any three propositions p, q, r
P
-
C
Kp v qj ?> ri <=> RI) ?> OA (q ?> r)1 (06 Marks)
m
-
c ---- b.
Prove that, the following are valid arguments:
0 -0
(i) p (q r)
p 4-> q
o
q r
q -->? p
-
74
? t
-P
? r
0
_
0
.,_.
.-
4 7
. , P
..,..
... r (07 Marks)
f
t :6:
C.
Give :
9 ?
v
s
.
3
? (i) a direct proof
11
(ii) an indirect proof
,...,. .
._
(iii) proof by contradiction for the following statement.
,.. --'
:_ -0 .r,
" "
,-,
If n is an odd integer, then n+9 is an even integer.
0 .-
(07 Marks)
t ?,,, -,
c to Module-2
? a
3 a. Prove that for each 1
2
+ 2' +3' +-....
,
47 n
2
= ?
I
n(n +1)(2n + 1) . (06 Marks)
O
?
L.,
6
CJ
c .
>,
f."
-
- .?
b. Determine the coefficient of,
.,-"
,-..i
(i)
xyz
2
in the expansion of (2x ? y?z)
4
.
? ?
"c3'
u
(ii) x
2
y
2
z
3
in the expansion of (3x ? 2y? 4z)
7
.
Z
(07 Marks)
,_.
c. A woman has 11 close relatives and she wishes to invite 5 of them to dinner. In how many
o ways can she invite them in the following situations:
0_.
E (i) There is no restriction on the choice.
(ii) TWO particular persons will not attend separately.
(iii) Two particular persons will not attend together. (07 Marks)
FirstRanker.com - FirstRanker's Choice
USN
( f
:14?
1E'
SCS36
Third Semester B.F. Degree Examination, Dec.200MAif:2020
Discrete Mathematical Structures
Time: 3 hrs. Max. Marks: 100
Note: Answer FIVE full questions, choosing ONE full question from each module.
.....
t
o
1 a. Prove that, for any propositions p, q, r the compound proposition
Module-1
E.
[(p ---> q) A (q ?> r) --> (p --> r)] is a tautology. (06 Marks)
b. Test the validity of the following argument.
-0
If I study, 1 will not fail in the examination.
If I do not watch TV in the evenings, I will study.
(
,
3
A
ci 7,
. ,,,, I failed in the examination.
cz ?
.--
.--' 6
.
... I must have watched TV in the evenings (07 Marks)
to II
44
.
1,]: kr)
I
C. Let p(x) : x
2
?7x +10 =0 , q(x) : x
2
?2x +3 --- - 0, r(x): x < 0. Find the truth or falsity of
00 =
;:- - +
the following statements, when the universe U contains only the integers 2 and 5,
.
m
._ c-.1
-t
E ,b
P v (i) Vx,p(x) ?> ?r(x) (ii) Vx , q(x)?>r(x)
(iii) 3x , q(x)-->r(x) (iv) ]x,p(x) ?>r(x)
!,. .. .7.. .
(07 Marks)
0
,,
a.: OR
.- .
..., .0
ii,
2 a. Prove that, for any three propositions p, q, r
P
-
C
Kp v qj ?> ri <=> RI) ?> OA (q ?> r)1 (06 Marks)
m
-
c ---- b.
Prove that, the following are valid arguments:
0 -0
(i) p (q r)
p 4-> q
o
q r
q -->? p
-
74
? t
-P
? r
0
_
0
.,_.
.-
4 7
. , P
..,..
... r (07 Marks)
f
t :6:
C.
Give :
9 ?
v
s
.
3
? (i) a direct proof
11
(ii) an indirect proof
,...,. .
._
(iii) proof by contradiction for the following statement.
,.. --'
:_ -0 .r,
" "
,-,
If n is an odd integer, then n+9 is an even integer.
0 .-
(07 Marks)
t ?,,, -,
c to Module-2
? a
3 a. Prove that for each 1
2
+ 2' +3' +-....
,
47 n
2
= ?
I
n(n +1)(2n + 1) . (06 Marks)
O
?
L.,
6
CJ
c .
>,
f."
-
- .?
b. Determine the coefficient of,
.,-"
,-..i
(i)
xyz
2
in the expansion of (2x ? y?z)
4
.
? ?
"c3'
u
(ii) x
2
y
2
z
3
in the expansion of (3x ? 2y? 4z)
7
.
Z
(07 Marks)
,_.
c. A woman has 11 close relatives and she wishes to invite 5 of them to dinner. In how many
o ways can she invite them in the following situations:
0_.
E (i) There is no restriction on the choice.
(ii) TWO particular persons will not attend separately.
(iii) Two particular persons will not attend together. (07 Marks)
OR
4 a. Prove that every positive integer n 24 can be written as a sum of 5's and / or 7's.
(06 Ma.
Find the number of permutations of the letters of the word MASSASAUGA. In how may
of these all four A's are together? How many of them begin with S? (07 Marks
In how many ways can one distribute eight identical balls into four distinct containers, so
b.
C.
5 a.
that, (i) No containers
(ii) The fourth
For any non empty sets
is left empty.
container gets an odd number of balls.
Module-3
A, B, C prove that,
(i) Ax(BuC)=(Ax 8)u(AxC)
(ii) x(B?C))=(A x BHA xC)
b. Let f : R --> R be defined by f(x) =
3x ?5 for x > 0
?3x +1 for x 0
(i) Determine f(0), f (ii) Find f {? 5,5] ).
;)
c. Let f, g, h be functions form z to z defined by f(x) = x ?I,
J
O if x is even
h(x)--
)
. Verify that (f a g)0 h(x) = f 0 (g 0 h )(x ) .
if x is odd
(07 Marks)
(06 Marks)
(07 Marks)
g(x) =3
(07 Markst--?
OR
6 a.
Let A =11,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 a matrix and draw its diagraph. (06 Marks)
b.
Draw the Hasse diagram representing the positive divisors of 36. (07 Marks)
C.
Let A = 11?2,3,4,51, define a relation R on A x A, by (x
l
,y
i
)R(x,,y
2
) if and only if
x, +y, =x, +y,
(i) Verify that R is an equivalence relation.
( ii) Find the partition of A x A induced by R. (07 Marks)
Module-4
7 a. There are eight letters to eight different people to be placed in eight different addressed
envelopes. Find the number of ways of doing this so that at least one letter gets to the right
person. (06 Marks)
b. In how many ways can the 26 letters of the English alphabet be permuted so that none of the
patterns CAR, DOG, PUN or BYTE occurs? (07 Marks,--
c. By using the expansion formula, obtain the rook polynomial for the board C. (07 Marks)
1
2 3
5
7 8
OR
8 a. An apple, a banana, a mango and an orange are to be distributed to four boys B1, B2,
B3, B4.
The boys B
1
and B2 do not wish to have apple. The boy B3 does not want banana or mango,
and B4 refuses orange. In how many ways the distribution can be made so that no boy is
displeased? (06 Marks)
b.
If ao = 0, al = 1, a2 = 4 and a4 ---- 37 satisfy the recurrence relation 4+2 + banfi + ca
n
= 0, for
n > 0 , find the constants b and c, and solve the relation a
n
.
C.
How many integers between 1 and 300 (inclusive) are,
(i)
Divisible by at least one of 5, 6, 8?
(ii) Divisible by none of 5, 6, 8?
2 of3
FirstRanker.com - FirstRanker's Choice
USN
( f
:14?
1E'
SCS36
Third Semester B.F. Degree Examination, Dec.200MAif:2020
Discrete Mathematical Structures
Time: 3 hrs. Max. Marks: 100
Note: Answer FIVE full questions, choosing ONE full question from each module.
.....
t
o
1 a. Prove that, for any propositions p, q, r the compound proposition
Module-1
E.
[(p ---> q) A (q ?> r) --> (p --> r)] is a tautology. (06 Marks)
b. Test the validity of the following argument.
-0
If I study, 1 will not fail in the examination.
If I do not watch TV in the evenings, I will study.
(
,
3
A
ci 7,
. ,,,, I failed in the examination.
cz ?
.--
.--' 6
.
... I must have watched TV in the evenings (07 Marks)
to II
44
.
1,]: kr)
I
C. Let p(x) : x
2
?7x +10 =0 , q(x) : x
2
?2x +3 --- - 0, r(x): x < 0. Find the truth or falsity of
00 =
;:- - +
the following statements, when the universe U contains only the integers 2 and 5,
.
m
._ c-.1
-t
E ,b
P v (i) Vx,p(x) ?> ?r(x) (ii) Vx , q(x)?>r(x)
(iii) 3x , q(x)-->r(x) (iv) ]x,p(x) ?>r(x)
!,. .. .7.. .
(07 Marks)
0
,,
a.: OR
.- .
..., .0
ii,
2 a. Prove that, for any three propositions p, q, r
P
-
C
Kp v qj ?> ri <=> RI) ?> OA (q ?> r)1 (06 Marks)
m
-
c ---- b.
Prove that, the following are valid arguments:
0 -0
(i) p (q r)
p 4-> q
o
q r
q -->? p
-
74
? t
-P
? r
0
_
0
.,_.
.-
4 7
. , P
..,..
... r (07 Marks)
f
t :6:
C.
Give :
9 ?
v
s
.
3
? (i) a direct proof
11
(ii) an indirect proof
,...,. .
._
(iii) proof by contradiction for the following statement.
,.. --'
:_ -0 .r,
" "
,-,
If n is an odd integer, then n+9 is an even integer.
0 .-
(07 Marks)
t ?,,, -,
c to Module-2
? a
3 a. Prove that for each 1
2
+ 2' +3' +-....
,
47 n
2
= ?
I
n(n +1)(2n + 1) . (06 Marks)
O
?
L.,
6
CJ
c .
>,
f."
-
- .?
b. Determine the coefficient of,
.,-"
,-..i
(i)
xyz
2
in the expansion of (2x ? y?z)
4
.
? ?
"c3'
u
(ii) x
2
y
2
z
3
in the expansion of (3x ? 2y? 4z)
7
.
Z
(07 Marks)
,_.
c. A woman has 11 close relatives and she wishes to invite 5 of them to dinner. In how many
o ways can she invite them in the following situations:
0_.
E (i) There is no restriction on the choice.
(ii) TWO particular persons will not attend separately.
(iii) Two particular persons will not attend together. (07 Marks)
OR
4 a. Prove that every positive integer n 24 can be written as a sum of 5's and / or 7's.
(06 Ma.
Find the number of permutations of the letters of the word MASSASAUGA. In how may
of these all four A's are together? How many of them begin with S? (07 Marks
In how many ways can one distribute eight identical balls into four distinct containers, so
b.
C.
5 a.
that, (i) No containers
(ii) The fourth
For any non empty sets
is left empty.
container gets an odd number of balls.
Module-3
A, B, C prove that,
(i) Ax(BuC)=(Ax 8)u(AxC)
(ii) x(B?C))=(A x BHA xC)
b. Let f : R --> R be defined by f(x) =
3x ?5 for x > 0
?3x +1 for x 0
(i) Determine f(0), f (ii) Find f {? 5,5] ).
;)
c. Let f, g, h be functions form z to z defined by f(x) = x ?I,
J
O if x is even
h(x)--
)
. Verify that (f a g)0 h(x) = f 0 (g 0 h )(x ) .
if x is odd
(07 Marks)
(06 Marks)
(07 Marks)
g(x) =3
(07 Markst--?
OR
6 a.
Let A =11,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 a matrix and draw its diagraph. (06 Marks)
b.
Draw the Hasse diagram representing the positive divisors of 36. (07 Marks)
C.
Let A = 11?2,3,4,51, define a relation R on A x A, by (x
l
,y
i
)R(x,,y
2
) if and only if
x, +y, =x, +y,
(i) Verify that R is an equivalence relation.
( ii) Find the partition of A x A induced by R. (07 Marks)
Module-4
7 a. There are eight letters to eight different people to be placed in eight different addressed
envelopes. Find the number of ways of doing this so that at least one letter gets to the right
person. (06 Marks)
b. In how many ways can the 26 letters of the English alphabet be permuted so that none of the
patterns CAR, DOG, PUN or BYTE occurs? (07 Marks,--
c. By using the expansion formula, obtain the rook polynomial for the board C. (07 Marks)
1
2 3
5
7 8
OR
8 a. An apple, a banana, a mango and an orange are to be distributed to four boys B1, B2,
B3, B4.
The boys B
1
and B2 do not wish to have apple. The boy B3 does not want banana or mango,
and B4 refuses orange. In how many ways the distribution can be made so that no boy is
displeased? (06 Marks)
b.
If ao = 0, al = 1, a2 = 4 and a4 ---- 37 satisfy the recurrence relation 4+2 + banfi + ca
n
= 0, for
n > 0 , find the constants b and c, and solve the relation a
n
.
C.
How many integers between 1 and 300 (inclusive) are,
(i)
Divisible by at least one of 5, 6, 8?
(ii) Divisible by none of 5, 6, 8?
2 of3
18CS36
Module-5
9 a. Show that the following two graphs shown in Fig. Q9 (a) ? (i) and Fig. Q9 (a) ? (ii) are
isomorphic, (06 Marks)
b.
Fig. Q9 (a) ? (i)
Define the following with example of each,
(i) Simple graph (ii) Sub graph
Fig. Q9 (a) ? (ii)
(iii) Compliment of a graph (iv) Spanning sub graph (07 Marks)
c. Construct an optimal pro fix code for the symbols a, o, q, u, y, z that occurs with frequencies
20, 28, 4, 17, 12, 7 respectively. (07 Marks)
OR
10 a. Prove that two simple graphs G
1
and G2 are isomorphic if and only if their complements are
isomorphic. (06 Marks)
b. Let G = (V, E) be a simple graph of order IV n and size 1E1= m , if G is a bipartite graph.
Prove that 4m < n
2
. (07 Marks)
c. Construct an optimal prefix code for the letters of the word ENGINEERING. Hence deduce
the code for this word. (07 Marks)
3 of 3
FirstRanker.com - FirstRanker's Choice
This post was last modified on 02 March 2020