Rajasthan Technical University 2011 M.C.A I - Sem(Main & Back)- , Subject: Discrete Mathematics (-105) - Question Paper

	Rnll Nn		Total Printed Pages : j 3 j
mi		1C7105
r \	M. C. A. (Sent. I) (Main/Back) Examination, January - 2011
w	MCA-105 Discrete Mathematics
m

[Total Marks : 80 [Min. Passing Marks : 32

Attempt all questions.

Use of following supporting material is permitted during examination. (Mentioned in form No. 205)

Nil

(a)    Define disjoint sets.

(b)    How many relations can be defined on a set which contains n elements?

(c)    Define coset of a subgroup.

(d)    Write the numeric function for which a₀~l and a_r = 7a_r_i, r > 1.

(e)    What do you mean by Eulerian Path?

(f)    Explain logical equivalence of two propositions by using suitable example.

(g)    Define homomorphism of groups.

(h)    How many words can be formed by using all letters of the word MISSISSIPr?

(i)    Define bounded lattice with example.

(j) In how many ways can 4 prizes be distributed in 3 students?

2 (a) How many positive integers not exceeding 500 are divisible by 7 or 11?

ic7io5] | Ell 11! IIII 111! II III!

1 C 7 1 Q 5

(e) A grammar G is specified below. Describe precisely the language, L(G), produced by this grammar.

G = (V, S, v₀, > )

V = {vo,V\,a,b},S = {a,b) i-: v₀ i- avi

V] I 6Vq Vj h->a

5x4=20

(a)    Obtain the principal conjuctive normal form of the formula

S given by (~P- R) ^A (Q 4= P). By using this obtained

PCNF, find out the principal disjunctive normal form of the same formulas.

(b)    Show that the order of a cycle of length r is r.

(c)    Write short note on Finite State Machine.

3x5=15

(a)    Prove by the principle of mathematical induction that n(n+l) (2n+l) is divisible by 6 for all nEN.

(b)    If R and S are two equivalence relations on a set A, then prove that (RnS) is also an equivalence relation on A.

2x10=20

INI HI 111 11

Attachment: rajasthan-technical-university-2011-m-c-a--36702-1.pdf

Earning:   Approval pending.