Gujarat Technological University 2010 M.C.A Discrete Mathematics for Computer Science - Question Paper
Seat No. Enrolment No.
GUJARAT TECHNOLOGICAL UNIVERSITY
MCA Sem-I Remedial Examination April 2010
Subject code: 610003
Subject Name: Discrete Mathematics For Computer Science Date: 06 / 04 / 2010 Time: 12.00 noon - 02.30 pm
Total Marks: 70
Instructions:
1. Attempt all questions.
2. Make suitable assumptions wherever necessary.
3. Figures to the right indicate full marks.
Q.1 (a) Answer the following:
(i) Express the following using predicates, quantifiers, and logical 04 connectives. Also verify the validity of the consequence.
Everyone who graduates gets a job.
Ram is graduated.
Therefore, Ram got a job.
(ii) Prove by contradiction that -s/2 is an irrational number. 03 (b) Draw Hasse Diagram of the poset{2,3,5,6,9,15,24,45},. Find 07
(i) Maximal and Minimal elements
(ii) Greatest and Least 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.
Q.2 (a) When a poset said to be lattice? Explain. Is every poset a lattice? Justify. Is the poset {0,{p},{q},{p,q,r}}, lattice?
07
07
07
(b) Show that the lattice (Sn, D) for n = 100 is isomorphic to the direct
product of lattices for n = 4 and n = 25.
OR
(b) With proper justification give 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.
Q.3 (a) Answer the following:
(i) Define sub-Boolean algebra. State the necessary and sufficient condition for a subset becomes sub-algebra. Find all sub Boolean
05
algebra of(S110, D
02
07
(ii) Prove the following Boolean identities:
(1) (x' y )*( x y) = y (2) (x y z)*(y z) = (y z)
(b) Use the Quine-Mccluskey algorithm to find the prime implicants and also obtain a minimal expression for function: f (a,b,c,d) = (15,14,13,6,5,2,1) .
OR
Q.3 (a) Use Karnaugh map to find a minimal sum-of-product expression for the function given by (0,1,2,3,6,7,13,14) in four variables w, x, y, z.
(b) Answer the following:
(i) Given an expression a(a, b, c, d) = (2,3,6,8,12,15), determine 04
the value of a (3,5,10,30) where3,5,10,30 e(S30, D).
(ii) Find the sum of products expansions of Boolean functions 03
f (X , z ) = (x + z) y
Define group homomorphism; prove that group homomorphism 07 preserves identities, inverses and subgroups.
(a)
(b)
(a)
(b)
Define cyclic group. Find generators of(Z12, +12). Also find its all 07 subgroups. Which subgroups are isomorphic to( Z4, +4)? Justify.
OR
Show that if every element in a group is its own inverse, then the group 07 must be abelian. Is the converse true? Justify.
Q.4
Define symmetric group/ S3, . Write its composition table. Determine 07
all the proper subgroups of(S3, 0). Which subgroup is normal subgroup? Support your answer with reason.
Q.5 (a) Define isomorphic graphs. Determine whether the digraphs G and H given in figure - 1 (a), (b) are isomorphic.
07
07
07
(b) Define node base of a digraph. Find all node base of the digraph shown in figure - 2. List out all the properties of a node base. Explain why no node in node base is reachable from any other node in node base.
OR
Q.5 (a) Define: path, simple path, elementary path. For the graph given in Figure - 3:
(i) Find an elementary path of length 2 from vi to v3.
(ii) Find 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?
(b) Define a directed tree. Draw the graph of the tree represented by
07
( A (B ( C ( D)( E))(F (G)(H)( J )))(K (L)(M)(N ( P)(Q ( R)))))
Obtain
the binary tree corresponding to it.
 |
|
Figure - 3 |
Figure - 2
 |
Ui |
Graph H: Figure - 1 (b)
Graph G: Figure - 1 (a)
3
|
Attachment: |
| Earning: Approval pending. |
