M.C.A- 1st Sem MT11 : 105 - DISCRETE MATHEMATICS(University of Pune, Pune-2013)

M.C.A. (Management Faculty) (Semester - I) Examination, 2013

MT11 : 105 - DISCRETE MATHEMATICS

(New) (2012 Pattern)

Time : 3 Hours                                                                                                             Max. Marks : 70

Instructions : i) Question No. 1 is compulsory.

ii) Solve any two questions from question Nos. 2, 3 and 4.

iii) Use of scientific calculator and Statistical Tables are

allowed.

iv) Figures to the right indicate full marks.

1. a) Show the following equivalence :                                                                                        5

((P® Q) Ù (R ® Q)⇔ (P Ú R) ® Q

b) Obtain PCNF of the following :                                                                                            5

(PÚ Q) Ú ( P Ù R) Ú (Q Ù R)

c) Prove following binomial identity by combinatorial arguments :                                5

2n   = 2  n   + n2

that boys and girls sit on alternate seats.                                                                       5

e) Define abelian group.                                                                                                             5

f) Define equivalence relation. Give example.                                                                    5

P.T.O.

2. a) Write the following in symbolic form :                                                                                5

If Tina marries Rahul, she will be in Pune. If Tina Marries Ram, she will be in

Mumbai. If she is either in Pune or in Mumbai, she will be definitely settled in life. She is not settled in life. Thus she did not marry Rahul or Ram.

b) Find the coefficient of the term x6y6z5 from the expansion of

(2x2 - 3y3 + 4z)10.                                                                                                                   5

c) Prove that the conclusion S is valid from the statements :                                         5

P,(PÙ Q) ® R, S ® R, Q

d) Define : Universe of Discourse, Universal Quantifier, Existential Quantifier.        5

3. a) Find the transitive closure for the relation                                                                         5

R = {< a, a >, < a, b >, < b, a >, < b, d >, < c, c >, < c, d >, < d, b >}

defined over the set A = {a, b, c, d}.

b) For the given relation matrix, find the relation set and draw its digraph.                 5

⎡1     1    0    0    0⎤

⎢0       1      0     1      0 ⎢       

MR =   ⎢0    0    1    0   0⎢ 

c) Let R = {<x, x>, <y, x>, <z, z>} and S = {<x, x>, <x, y>, <y, z>, <z, y>}.

Find R• S, (R• R)• S and S2.                                                                                                    5

d) Find whether the given function f(x) = x(x3 - 5) for all positive integers of x is

bijective or not.                                                                                                                       5

4. a) Find the number of non negative integer solutions for x1 + x2 + x3 = 31 where

x1³ 4, x2 > 7 and x3 ³ 10 .                                                                                                         7

b) Find the code words generated by the parity check matrix                                         7

⎛1 1 0 1 1 0 0⎞

⎜

               H = ⎜1 1 1 0 0 1 0 ⎟

⎜ 1 0 1 1 0 0 1⎟

⎝                             ⎠

c) State and prove derangement formula.                                                                             6

————————

B

Add comment