Madurai Kamraj University (MKU) 2006-1st Year M.C.A Computer Aplications All subject s - Question Paper

M.C.A 1st Year MAY 2006


Paper I - MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE


Time: 3 hours Maximum: 100 marks


PART A ans ALL ques.. (8 x five =40 marks)

1. (a) Construct the truth table for Or
(b) find disjunctive normal form of

2. (a) Show that is a valid conclusion from the premises P v Q,
Q
R, P
M and M.
(b)Show that P v Q follows from P.


3. (a) explain the connection ranging from groups and monoids. Or
(b) Prove that the intersection of any 2 subgroups of a group G is again a subgroup of G.


4. (a) describe a cyclic group. Also prove that every cyclic group G is abelian. Or
(b) describe a field. provide a suitable example.


5. (a) Show that the function f described by f (x ) = X / two when X is even
= X – two when X is odd, primitive recursive.
Or
(b) Show that the set of divisions B of a positive integer n is recursive.


6. (a) describe posets with an example. Let (L ,<=)be a poset and a1,, a2EL . If a1 and a2 have a
greatest lower bound (GLB) , then show that this GLB is unique. Or
(b) Let (L,:::;) be a lattice and a,b,c E L . Then prove that a ??a=a and a *a =a .


7. (a) discuss Normal forms. Or
(b) obtain a grammar G such that L(G) = { an b n : n >= 1}.


8. (a) discuss Pumping Lemma. Or
(b) Design finite state automata that accepts precisely those strings over {a, b} that
contains an
Odd number of a's.


PART B ans ALL ques.. (5 x 12 =60 marks)


9. (a) (i) discuss the difference ranging from direct proof and indirect proof with suitable
examples.
(ii) Without constructing a truth table, show that A /\E is not a valid consequence of
A ?B B ?(C ^ D) ) C ? ( A V E) A V E Or
(b) (i) Derive P
(Q
R ) , Q
(R
S ) => P
(Q
S) using rule CP
if necessary.
(ii) Using indirect method if needed, prove that (R
Q), R v S, S
Q,
P
Q = P.


10. (a) (i) Show that every cyclic monoid is commutative.
(ii) Prove that a commutative ring (R , +, .) is an integral domain if and only if
the Cancellation legal regulations a . b =a . c and a  b => b = c , a, b, c E R holds.
Or
(b) State and prove Lagrange's theorem.


11. (a) (i) Let (L,  ) be a lattice. Then show that for any a,b,c EL , the distributive inequalities.
(ii) Show that in a lattice (L , ), for any

Earning:   Approval pending.