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

USN
( f
:14?
1E'
SCS36

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

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

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

t
o
1 a. Prove that, for any propositions p, q, r the compound proposition
Module-1
E.

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

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

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

(
,
3
A
ci 7,

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

. ,,,, I failed in the examination.
cz ?
.--
.--' 6

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

.
... I must have watched TV in the evenings (07 Marks)
to II

44

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

.
1,]: kr)
I
C. Let p(x) : x
2

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

?7x +10 =0 , q(x) : x
2
?2x +3 --- - 0, r(x): x < 0. Find the truth or falsity of
00 =
;:- - +

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

the following statements, when the universe U contains only the integers 2 and 5,
.
m

._ c-.1

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

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

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

(07 Marks)
0
,,
a.: OR
.- .

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

..., .0
ii,
2 a. Prove that, for any three propositions p, q, r
P
-

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

C
Kp v qj ?> ri <=> RI) ?> OA (q ?> r)1 (06 Marks)
m
-

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

c ---- b.
Prove that, the following are valid arguments:
0 -0
(i) p (q r)
p 4-> q

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

o
q r
q -->? p
-
74

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

? t
-P
? r
0
_

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

0
.,_.
.-
4 7
. , P

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

..,..
... r (07 Marks)
f
t :6:

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

C.
Give :
9 ?
v
s

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

.
3
? (i) a direct proof
11
(ii) an indirect proof

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

,...,. .
._
(iii) proof by contradiction for the following statement.
,.. --'
:_ -0 .r,

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

" "
,-,
If n is an odd integer, then n+9 is an even integer.
0 .-
(07 Marks)

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

t ?,,, -,
c to Module-2
? a
3 a. Prove that for each 1
2

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

+ 2' +3' +-....
,
47 n
2
= ?

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

I
n(n +1)(2n + 1) . (06 Marks)
O
?
L.,

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

6
CJ
c .
>,
f."

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

-
- .?
b. Determine the coefficient of,
.,-"
,-..i

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

(i)
xyz
2
in the expansion of (2x ? y?z)
4

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

.
? ?
"c3'
u
(ii) x

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

2
y
2
z
3

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

in the expansion of (3x ? 2y? 4z)
7
.
Z
(07 Marks)

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

,_.
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.

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

(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

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

:14?
1E'
SCS36
Third Semester B.F. Degree Examination, Dec.200MAif:2020
Discrete Mathematical Structures

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

Time: 3 hrs. Max. Marks: 100
Note: Answer FIVE full questions, choosing ONE full question from each module.
.....
t
o

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

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.

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

-0
If I study, 1 will not fail in the examination.
If I do not watch TV in the evenings, I will study.
(
,

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

3
A
ci 7,

. ,,,, I failed in the examination.

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

cz ?
.--
.--' 6
.
... I must have watched TV in the evenings (07 Marks)

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

to II

44
.
1,]: kr)

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

I
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. Find the truth or falsity of
00 =
;:- - +
the following statements, when the universe U contains only the integers 2 and 5,
.

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

m

._ c-.1
-t
E ,b

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

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

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

,,
a.: OR
.- .
..., .0
ii,

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

2 a. Prove that, for any three propositions p, q, r
P
-
C
Kp v qj ?> ri <=> RI) ?> OA (q ?> r)1 (06 Marks)

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

m
-

c ---- b.
Prove that, the following are valid arguments:

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

0 -0
(i) p (q r)
p 4-> q
o
q r

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

q -->? p
-
74
? t
-P

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

? r
0
_
0
.,_.

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

.-
4 7
. , P
..,..
... r (07 Marks)

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

f
t :6:

C.
Give :

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

9 ?
v
s
.
3

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

? (i) a direct proof
11
(ii) an indirect proof
,...,. .
._

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

(iii) proof by contradiction for the following statement.
,.. --'
:_ -0 .r,
" "
,-,

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

If n is an odd integer, then n+9 is an even integer.
0 .-
(07 Marks)
t ?,,, -,
c to Module-2

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

? a
3 a. Prove that for each 1
2
+ 2' +3' +-....
,

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

47 n
2
= ?
I
n(n +1)(2n + 1) . (06 Marks)

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

O
?
L.,
6
CJ

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

c .
>,
f."
-
- .?

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

b. Determine the coefficient of,
.,-"
,-..i
(i)
xyz

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

2
in the expansion of (2x ? y?z)
4
.
? ?

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

"c3'
u
(ii) x
2
y

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

2
z
3
in the expansion of (3x ? 2y? 4z)
7

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

.
Z
(07 Marks)
,_.
c. A woman has 11 close relatives and she wishes to invite 5 of them to dinner. In how many

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

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)

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

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

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

In how many ways can one distribute eight identical balls into four distinct containers, so
b.
C.
5 a.
that, (i) No containers

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

(ii) The fourth
For any non empty sets
is left empty.
container gets an odd number of balls.
Module-3

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

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

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

?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

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

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

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

(07 Marks)
(06 Marks)
(07 Marks)
g(x) =3
(07 Markst--?

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

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.

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

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

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

i
)R(x,,y
2
) if and only if
x, +y, =x, +y,

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

(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

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

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

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

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,

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

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

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

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

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

n > 0 , find the constants b and c, and solve the relation a
n
.
C.

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

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

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

FirstRanker.com - FirstRanker's Choice
USN
( f
:14?
1E'

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

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.

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

.....
t
o
1 a. Prove that, for any propositions p, q, r the compound proposition
Module-1

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

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.

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

If I do not watch TV in the evenings, I will study.
(
,
3
A

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

ci 7,

. ,,,, I failed in the examination.
cz ?
.--

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

.--' 6
.
... I must have watched TV in the evenings (07 Marks)
to II

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

44
.
1,]: kr)
I
C. Let p(x) : x

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

2
?7x +10 =0 , q(x) : x
2
?2x +3 --- - 0, r(x): x < 0. Find the truth or falsity of
00 =

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

;:- - +
the following statements, when the universe U contains only the integers 2 and 5,
.
m

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

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

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

!,. .. .7.. .
(07 Marks)
0
,,
a.: OR

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

.- .
..., .0
ii,
2 a. Prove that, for any three propositions p, q, r
P

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

-
C
Kp v qj ?> ri <=> RI) ?> OA (q ?> r)1 (06 Marks)
m
-

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

c ---- b.
Prove that, the following are valid arguments:
0 -0
(i) p (q r)

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

p 4-> q
o
q r
q -->? p
-

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

74
? t
-P
? r
0

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

_
0
.,_.
.-
4 7

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

. , P
..,..
... r (07 Marks)
f
t :6:

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

C.
Give :
9 ?
v

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

s
.
3
? (i) a direct proof
11

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

(ii) an indirect proof
,...,. .
._
(iii) proof by contradiction for the following statement.
,.. --'

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

:_ -0 .r,
" "
,-,
If n is an odd integer, then n+9 is an even integer.
0 .-

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

(07 Marks)
t ?,,, -,
c to Module-2
? a
3 a. Prove that for each 1

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

2
+ 2' +3' +-....
,
47 n
2

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

= ?
I
n(n +1)(2n + 1) . (06 Marks)
O
?

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

L.,
6
CJ
c .
>,

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

f."
-
- .?
b. Determine the coefficient of,
.,-"

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

,-..i
(i)
xyz
2
in the expansion of (2x ? y?z)

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

4
.
? ?
"c3'
u

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

(ii) x
2
y
2
z

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

3
in the expansion of (3x ? 2y? 4z)
7
.
Z

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

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

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

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.

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

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

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

C.
5 a.
that, (i) No containers
(ii) The fourth
For any non empty sets

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

is left empty.
container gets an odd number of balls.
Module-3
A, B, C prove that,
(i) Ax(BuC)=(Ax 8)u(AxC)

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

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

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

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

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

)
. Verify that (f a g)0 h(x) = f 0 (g 0 h )(x ) .
if x is odd
(07 Marks)
(06 Marks)

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

(07 Marks)
g(x) =3
(07 Markst--?
OR
6 a.

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

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.

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

Let A = 11?2,3,4,51, define a relation R on A x A, by (x
l
,y
i
)R(x,,y

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

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)

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

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

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

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

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

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

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

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.

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

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

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

.
C.

How many integers between 1 and 300 (inclusive) are,
(i)

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

Divisible by at least one of 5, 6, 8?
(ii) Divisible by none of 5, 6, 8?
2 of3
18CS36
Module-5

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

9 a. Show that the following two graphs shown in Fig. Q9 (a) ? (i) and Fig. Q9 (a) ? (ii) are
isomorphic, (06 Marks)

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

b.
Fig. Q9 (a) ? (i)
Define the following with example of each,
(i) Simple graph (ii) Sub graph
Fig. Q9 (a) ? (ii)

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

(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

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

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

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

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

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

FirstRanker.com - FirstRanker's Choice