Discrete Structures (DS) Semester 3 (Revised Course) (3 Hours) December 2009

Discrete Structures (DS) Semester 3 (Revised Course) (3 Hours) December 2009
SP-7370 [Total Marks : 100]
N.B:	(1)	Question no.1 is compulsory.
	(2)	Attempt any four questions out of remaining six questions.
	(3)	Figures to the right indicate full marks.
1.	(a)	Prove by Mathematical induction method-       12 + 22 + 32 + ..................+n2 =n(n+1) (2n+1)⁄6	05
	(b)	If A=B=C=R where R is set of real number and f: A→B, g : B → C are functions defined by f(x) = x + 1, g(x) = X2 + 2, then find (g o f) (x) and (f o g) (2).	05
	(c)	Show that a group (G, *) is abelian if and only if (a * b)2 = a2 * b2.	05
	(d)	In a Boolean algebra, prove that text a Λ b = a v b.	05
2.	(a)	Show that the relation R = {(x, y) is divisible by 4; where x, y are int ehers} is an equivalence relation. Write the equivalence classes given by R.	06
	(b)	Solve the recurrence relation an+2 - 5an+1 + 6an = 2 with initial conditions a0 = 1, a1 = - 1.	06
	(c)	Explain Quantifiers. Negate the statement '√2 is not a rational number'.	04
	(d)	Draw all Hasse diagrams of posets with three elements.	04
3.	(a)	Find the transitive closure of the relation R on set A defined by the given digraph using Warshall's Algorithm.	06
	(b)	Show that te (2, 5) encoding function e : A2→B5 defined by   e(00) = 00000 e(01) = 01110 e(10) = 10101 e(11) = 11011 is a group code. Find the minimum distance.	06
	(c)	Find the lower and upper bounds of the subsets {a, b, c} and {a, c, d, f} of given poset.	04
	(d)	Show that if any five integers form 1 to 8 are selected, then the sum of at least two of them will be 9.	04
4.	(a)	Consider the relation R on set of integers defined as xRy iff y = xk ; k is positive integer. Show that R is a partial order relation.	06
	(b)	Determine the Eulerian path and hamiltonian path, if exist, in the following graph.	06
	(c)	Check if the set A = {2, 4, 12, 16} is a lattice under divisibility.	04
	(d)	Find the generating function of the following sequences         (i) 1, 0 - 1, 0, 1, 0 - 1, 0, .........  (ii)  1, 1, 1, 1, 1,.........	04
5.	(a)	Let H = [ 1 1 0 1 0 0 0 1 1 0 1 0 0 0 1 0 0 1 be a parity check matrix. Decode the following words relative to maximum likelihood decoding function (i) 011001  (ii) 101011  (iii) 111010.	06
	(b)	Show that the lattices given in the following Hasse diagrams are non distributive	06
	(c)	Find the number of vertices of the graph having 16 edges if degree of each vertex is 2.	04
	(d)	For sets A, B, C prove that A x (B∪C) = (A x B) ∪ (A x C)	04
6.	(a)	Define isomorphic graphs. Determine whether the given graphs are isomorphic or not	06
	(b)	Draw Hasse diagrams of D4 x D9 is the set of positive divisors of n.	06
	(c)	Show that (I, ⊕, ⊕) is a commutative ring with identity where the operations ⊕ and ⊗ are defined as a ⊗ b = a + b - 1 and a ⊗ b = a + b - ab.	06
			04
7.	(a)	Show that {0, 1, 2, 3, 4, 5} is an abelian group under the operation+6.	06
	(b)	Define the following with example.      (i) Ring homomorphism      (ii) Field      (iii) Spanning tree.	06
	(c)	Show that the function f : R-{2} → R -{0} where R is set of real numbers defined by f(x) = 1/x-2 is a bijection. Find its inverse.