Madras University (UnOM) 2000 M.C.A Computer Aplications NTRODUCTION OF DISCRETE STRUCTURE - Question Paper

M.C.A., 1st Year
INTRODUCTION OF DiscRETE STRUCTURES
MAY 2000

Time: 3 hours
Maximum: 75 marks

PART A - (5 x five = 25 marks)

ans ALL ques..
All ques. carry equal marks.

1. (a) Show the equivalence
(P d Q) t (P Ù Q) v ( P Ù Q)

Or

(b) Show the {Ù,v} {v} and { } are not functionally complete.

2. (a) Let Z be the set of integers and let R be the relation called "congruence modulo 3" described by R = {x,y Î|x Î Z Ù y Î Z (x - y) is divisible by 3}. Determine the equivalence classes generated by the elements of Z.

Or

(b) provide an example of a set X such that r( ), x Í is a totally ordered set.

3. (a) State and prove Langrange's theorem.

Or

(b) Prove that every subgroup of a cyclic group is cyclic.

4. (a) discuss the method of finding the adjacency matrix.

Or

(b) How will you represent a graph using arrays.

5. (a) discuss the term 'right derivation' using a grammar to generate a language.

Or

(b) provide a context-free grammar which generates L = {w / w contains twice as many 0s as 1s}

PART B - (5 x 10 = 50 marks)

ans any 5 ques..
All ques. carry equal marks.

6. Show that (x) (P (x) v Q (x)) r(x) P (x) v ( Fx) Q (x).

7. show that R Ù (P v Q) is a valid conclusion from the premises P v Q, Q two R, P two M and M.

8. Show that addition of matrics form an abelian group.

9. Prove that for any commutative monoid M,* , the set of idempotent element s of M forms a submonoid.

10. Show that for any 2 sets A and B A -(A Ç B) = A - B.

11. (a) Show that the set of divisors of a positive integer n is recursive.

(b) Show that the sets of even and odd natural numbers are both recursive.

12. Contrast a context-sensitive grammar for the language { } w w/ *{} {a,b,c '-Ù, where w contains the identical number of a's, b's and c's.

13. discuss the terms 'sentential form', regular grammar and grammars.

Earning:   Approval pending.