Download Mumbai University (MU) MCA 2019 May 1st Sem 55804 Discrete Mathematics Question Paper

Duration: 3 hours Total: 100 marks

1. Question No. 1 is compulsory.
2. Attempt any four out of remaining six questions.

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

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. (10)
   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}

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

   5. Give all lower bounds and the GLB = {15,45}
2. (a) Establish the following result using truth tables. (05)
   (P ? Q) ? (¬R v Q) v P
3. (a) What is the solution of the recurrence relation a_n= a_n-1 + 2a_n-2, with initial condition a₀=2, a₁=7 (05)

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

4. (a) Write converse, inverse and contra positive of the following statement. (05)
   “If weather will not be good then I will not travel.”
5. (a) Obtain the disjunctive normal form of (P?Q) ? (¬P ? Q) (05)
6. (a) Find ?a_n, where a_n=n²+n+1 where ? denotes forward difference. (05)
7. (a) 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. (10)

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

8. (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. (05)
9. (a) Draw the transition state diagram of the finite state machine M=(S,I,O,d,?,S₀) given in the table (05)
   

   	I		O
   	a	b	a	b
   S0	S1	S2	X	Y
   S1	S3	S1	Y	Z
   S2	S1	S0	Z	X
   S3	S0	S2	Z	X

10. (a) Explain with suitable example:- (1) Predicate (2) Proposition (10)
11. (a) Determine whether the relation R on a set A is reflexive, irreflexive, asymmetric, antisymmetric or transitive. (05)
    

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

    A = set of all positive integers, aRy iff a < b+1
12. (a) Show by mathematical induction, that for all n >1, (05)
    1+5+9+...+(4n-3) = n(2n-1)
13. (a) Let G be a group. Show that the function f:G?G defined by f(a) =a^-1 is a homomorphism iff G is abelian. (05)
14. (a) Let T be set of even integers. Show that the semigroups (Z,+) and (T,+) are Isomorphic, where Z is a set of integers. (05)

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

15. (a) 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,V₀,?) (05)
    V ={V₀,a,b}, S={a,b}
    V₀?aV₀, V₀? a, V₀?b
16. (a) Perform the following (10)
    1. i) 0111 x 1010=?
    2. ii) (413)₅ = (?)₁₀

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

    3. iii) 10100 + 100=?
    4. iv) (1101)₂ = (1001)₂=?
    5. v) (49.25)₁₀=(?)₂
17. (a) Determine the validity of the following argument using deduction method: (05)
    

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

    “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”
18. (a) Let G be a group and let ’a’ be a fixed element of G. show that the function f:G?G defined by f(x) =axa^-1 for x?G is an isomorphism. (05)
19. (a) Let H =

    [1	1	0	1]
    [0	1	1	]
    [1	0	1	]
    [0	0	1	]

    be a parity check matrix. (05)
    Determine the group code e: B³?B⁶. How many errors will the above group code detect.
20. (a) 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)

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

21. (a) Show that (2,5) encoding function e:B²? B⁵ defined by e(00)=00000, e(01)=01110, e(10)=10101, e(11)=11011 is a group code. (10)
    Decode the following words with maximum likelihood technique:
    i) 11110 ii) 10011
22. (a) Find the particular solution of a_r+5a_r-1 +6a_r-2 =3r². (10)

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