Amrita Vishwa Vidyapeetham 2007 M.C.A Discrete Mathematics - Question Paper

M.C.A Nov 2007
Discrete Mathematics
Time : 3 hours Maximum : 100 marks
ans any 5 ques..
All ques. carry equal marks.
1. (a) Construct the truth table for Also show that
(b) Obtain the principle disjunctive normal form of .
2. (a) Show that SVR is tautologically implied by .
(b) Symbolize the expression ‘All the world loves a lover’. Also show that
3. (a) Show that .
(b) Let and
show that R is an equivalence relation on X. Also draw the graph of R.1 obtain and .
4. (a) Define characteristic function and hence show that
(i) and
(ii) .
(b) For any commutative monoid , prove that set of idem potent elements of M forms a submonoid.
(c) Define semi group Homomorphism and monoid homomorphism.
5. (a) Let be a finite cyclic group generated by an element If is of order n, then P.T so that . Furthermore , n is the lowest positive integer for which .
(b) State and prove Lagrange’s theorem
6. (a) Show that every finite group of order n is isomorphic to a permutation of degree n.
(b) Let g be a homomorphism from a group to a group and let K be the kernel of g and be the image set of g in H.P.T is isomorphic to .
7. (a) Define kernel of a homomorphism and show that kernel of a homomorphism g from a group to is a subgroup of .
(b) Show that the intersection of 2 normal subgroups is a normal subgroup.
8. (a) Define isomorphism ranging from graphs and test the isomorphism property ranging from the 2 graphs:

(b) Show that the sum of indegrees of all the nodes of a simple digraph is equal to the sum of out degrees of all its nodes and this sum is equal to the number of edges of the graph.
(c) In a simple graph G, show that every node of the digraph lies in exactly 1 strong component.

Earning:   Approval pending.