Gujarat Vidyapeeth 2010 M.C.A Discrete Mathematics For Computer Science - Question Paper

Q.1 (a) ans the following:
(i) Express the subsequent using predicates, quantifiers, and logical
connectives. Also verify the validity of the consequence.
Everyone who graduates gets a job.
Ram is graduated.
Therefore, Ram got a job.
04
(ii) Prove by contradiction that two is an irrational number. 03
(b) Draw Hasse Diagram of the poset {2,3,5,6,9,15,24,45},D . obtain
(i) Maximal and Minimal elements
(ii) Greatest and lowest members, if exist.
(iii) Upper bound of {9,15} and l.u.b. of{9,15} , if exist.
(iv) Lower bound of {15,24} and g.l.b. of{15,24} , if exist.
07
Q.2 (a) When a poset stated to be lattice? discuss. Is every poset a lattice? Justify.
Is the poset {Ø,{ p},{q},{ p, q, r}}, ? lattice?
07
(b) Show that the lattice , n S D for n = 100 is isomorphic to the direct
product of lattices for n = four and n = 25.
07
OR
(b) With proper justification provide an example of
(1) A bounded lattice which is complemented but not distributive.
(2) A bounded lattice which is distributive but not complemented.
(3) A bounded lattice which is neither distributive nor complemented.
(4) A bounded lattice which is both distributive and complemented.
07
Q.3 (a) ans the following:
(i) describe sub-Boolean algebra. State the necessary and sufficient
condition for a subset becomes sub-algebra. obtain all sub Boolean
algebra of 110 S , D .
05
(ii) Prove the subsequent Boolean identities:
(1) ( x'? y)*( x? y) = y (2) ( x? y? z )*( y? z ) = ( y? z )
02
(b) Use the Quine-Mccluskey algorithm to obtain the prime implicants and
also find a minimal expression for
function: f (a,b,c,d)=S(15,14,13,6,5,2,1) .
07
OR
Q.3 (a) Use Karnaugh map to obtain a minimal sum-of-product expression for the
function provided by S(0,1, 2,3,6,7,13,14) in 4 variables w, x, y, z.
07
2
(b) ans the following:
(i) provided an expression ( a a,b,c, d)=S(2,3,6,8,12,15) , determine
the value of a (3,5,10,30) where 30 3,5,10,30? S ,D .
04
(ii) obtain the sum of products expansions of Boolean functions
f (x, y, z) = (x + z) y
03
Q.4 (a) describe group homomorphism; prove that group homomorphism
preserves identities, inverses and subgroups.
07
(b) describe cyclic group. obtain generators of 12 12 Z ,+ . Also obtain its all
subgroups. Which subgroups are isomorphic to four 4 Z ,+ ? Justify.
07
OR
Q.4 (a) Show that if every element in a group is its own inverse, then the group
must be abelian. Is the converse true? Justify.
07
(b) describe symmetric group 3S , ? . Write its composition table. Determine
all the proper subgroups of 3S , ? . Which subgroup is normal
subgroup? Support your ans with cause.
07
Q.5 (a) describe isomorphic graphs. Determine whether the digraphs G and H
provided in figure – one (a), (b) are isomorphic.
07
(b) describe node base of a digraph. obtain all node base of the digraph shown
in figure – 2. List out all the properties of a node base. discuss why no
node in node base is reachable from any other node in node base.
07
OR
Q.5 (a) Define: path, simple path, elementary path. For the graph provided in
Figure – 3:
(i) obtain an elementary path of length two from v1 to v3.
(ii) obtain a simple path from v1 to v3, which is not elementary.
(iii)Find all possible paths from node v2 to v4 and how many of them are
simple and elementary?
07
(b) describe a directed tree. Draw the graph of the tree represented by
( A(B(C(D)(E))(F (G)(H )( J )))(K (L)(M )( (P)(Q(R)))))Obtain
the binary tree corresponding to it.
07

Earning:   Approval pending.