Download MU-(University of Mumbai or University of Bombay) MCA (Master of Computer Application) 2019 May 1st Sem 55804 Discrete Mathematics Previous Question Paper
8ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F5840
8ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F5840
8ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F5840
8ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F5840
8ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F5840
8ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F5840
8ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F5840
8ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F5840
8ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F5840
8ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F5840
8ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F5840
8ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F5840
8ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F5840
8ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F5840
8ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F5840
8ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F5840
8ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F5840
8ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F5840
8ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F5840
67799 Page 1 of 2
Duration 3 hours Total 100 marks
N.B: 1) Question No. 1 is compulsory.
2) Attempt any four out of remaining six questions.
3) Figures to the right indicate full marks.
1. (a) Let A={3,5,9,15,24,45} and relation R be defined on B by xRy if
and only if
?x divides y?. Show that R is a partial order relation
1.Draw the diagraph and Hasse diagram of R
2. Determine all minimal & all maximal elements.
3. find all least and greatest elements.
4. Give upper bounds and LUB of A={3,5)
5. Give all lower bounds and the GLB = {15,45}
(10)
(b) (i) Establish the following result using truth tables.
(P ^ Q) ?(?RvQ) v P
(05)
(ii) What is the solution of the recurrence relation an = an-1 + 2an-2,
with initial condition a0= 2, a1 = 7
(05)
2. (a) (i)
(ii)
Write converse , inverse and contra positive of the following
statement.
? If weather will not be good then I will not travel.?
Obtain the disjunctive normal form of (P->Q)^(?P^Q)
(05)
(05)
(b) (i)
(ii)
Find ?an where an = n
2
+ n+ 1 where ? denotes forward
difference.
For the set A = {a,b,c} give all the permutations of A. Show that
the set of all permutations of A is a group under the composition
operation.
(05)
(05)
3. (a) Obtain the recurrence relation and initial conditions to find the
maximum number of regions defined by n lines in a plane. Assume
that the lines are not parallel and lines not intersecting at one point
when n>2. Solve the recurrence relation.
(10)
(b) (i)
(ii)
Draw the transition state diagram of the finite state machine
M=(S,I,O,?,?,s0,) given in the table
? ?
a b a b
S0
S1
S2
S3
S1 S2
S3 S1
S1 S0
S0 S2
x y
y z
z x
z x
Explain with suitable example:- (1) Predicate (2) Proposition
(05)
(05)
4. (a) Determine whether the relation R on a set A is reflective
,irreflective, asymmetric, antisymmetric or transitive.
A = set of all positive integers, aRb iff a?b+1
(10)
Paper / Subject Code: 55804 / Discrete Mathematics
8ABC7E38817571ADA7806931AD0F5840
FirstRanker.com - FirstRanker's Choice
8ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F5840
8ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F5840
8ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F5840
8ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F5840
8ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F5840
8ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F5840
8ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F5840
8ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F5840
8ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F5840
8ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F5840
8ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F5840
8ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F5840
8ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F5840
8ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F5840
8ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F5840
8ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F5840
8ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F5840
8ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F5840
8ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F5840
8ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F5840
67799 Page 1 of 2
Duration 3 hours Total 100 marks
N.B: 1) Question No. 1 is compulsory.
2) Attempt any four out of remaining six questions.
3) Figures to the right indicate full marks.
1. (a) Let A={3,5,9,15,24,45} and relation R be defined on B by xRy if
and only if
?x divides y?. Show that R is a partial order relation
1.Draw the diagraph and Hasse diagram of R
2. Determine all minimal & all maximal elements.
3. find all least and greatest elements.
4. Give upper bounds and LUB of A={3,5)
5. Give all lower bounds and the GLB = {15,45}
(10)
(b) (i) Establish the following result using truth tables.
(P ^ Q) ?(?RvQ) v P
(05)
(ii) What is the solution of the recurrence relation an = an-1 + 2an-2,
with initial condition a0= 2, a1 = 7
(05)
2. (a) (i)
(ii)
Write converse , inverse and contra positive of the following
statement.
? If weather will not be good then I will not travel.?
Obtain the disjunctive normal form of (P->Q)^(?P^Q)
(05)
(05)
(b) (i)
(ii)
Find ?an where an = n
2
+ n+ 1 where ? denotes forward
difference.
For the set A = {a,b,c} give all the permutations of A. Show that
the set of all permutations of A is a group under the composition
operation.
(05)
(05)
3. (a) Obtain the recurrence relation and initial conditions to find the
maximum number of regions defined by n lines in a plane. Assume
that the lines are not parallel and lines not intersecting at one point
when n>2. Solve the recurrence relation.
(10)
(b) (i)
(ii)
Draw the transition state diagram of the finite state machine
M=(S,I,O,?,?,s0,) given in the table
? ?
a b a b
S0
S1
S2
S3
S1 S2
S3 S1
S1 S0
S0 S2
x y
y z
z x
z x
Explain with suitable example:- (1) Predicate (2) Proposition
(05)
(05)
4. (a) Determine whether the relation R on a set A is reflective
,irreflective, asymmetric, antisymmetric or transitive.
A = set of all positive integers, aRb iff a?b+1
(10)
Paper / Subject Code: 55804 / Discrete Mathematics
8ABC7E38817571ADA7806931AD0F5840
8ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F5840
8ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F5840
8ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F5840
8ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F5840
8ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F5840
8ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F5840
8ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F5840
8ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F5840
8ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F5840
8ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F5840
8ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F5840
8ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F5840
8ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F5840
8ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F5840
8ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F5840
8ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F5840
8ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F5840
8ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F5840
8ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F5840
8ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F58408ABC7E38817571ADA7806931AD0F5840
67799 Page 2 of 2
(b) (i)
(ii)
Show by mathematical induction, that for all n ?1,
1+5+9+---------------+(4n-3) =n(2n-1)
Let G be a group. Show that the function f:G ?G defined by
f(a) = a
2
is a homomorphism iff G is abelian.
(05)
(05)
5. (a) (i)
(ii)
Let T be set of even integers. Show that the semigroups (Z,+) and
(T,+) are Isomorphic, where Z is a set of integers.
For the grammar specified below describe precisely the
language,L(G),produced. Also give the corresponding syntax
diagram for the productions of the grammar. G=(V,S,vo,| ?)
V = {v0,a,b}, S = {a,b}
v0| ?aav0 , v0|--> a, v0 | ?b
(05)
(05)
(b) (i) perform the following
i) 0111 ? 1010= ?
ii) (413)8 = (?)10
iii) 10100 ? 100= ?
iv) (1101)2 ? (1001)2 = ?
v) (49.25)10 = (?)2
(10)
6. (a) (i)
(ii)
Determine the validity of the following argument using deduction
method:
? If I study then I will pass examination . If I do not go to picnic
,then I will study. But I failed examination. Therefore , I went to
picnic?
Let G be a group and let ?a? be a fixed element of G. show that the
function fa:G ?G defined by fa(x) =axa
-1
for x?G is an
isomorphism.
(05)
(05)
(b) (i)
(ii)
Let
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
1 0 0
0 1 0
0 0 1
1 1 0
0 1 1
H be a parity check matrix.
Determine the group code eH: B
2
-->B
5
. How many errors will the
above group code detect.
Let A={1,2,3,4}. For the relation
R={(1,1),(1,4),(2,2),(3,3),(2,1),(4,4) find the matrix of transitive
closure by using Warshall?s algorithm.
(05)
(05)
7. (a) Show that (2,5) encoding function e:B
2
--> B
5
defined
bye(00)=00000,e(01)=01110,e(10)=10101, e(11)=11011 is a group
code.
Decode the following words with maximum likelihood technique:
i)11110 ii)10011
(10)
(b) Find the particular solution of ar+5ar-1 +6ar-2 =3r
2
. (10)
*******
Paper / Subject Code: 55804 / Discrete Mathematics
8ABC7E38817571ADA7806931AD0F5840
FirstRanker.com - FirstRanker's Choice
This post was last modified on 05 February 2020