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

Discrete Structures (DS) Semester 3 (Revised Course) (3 Hours) December 2010
GT-6232 [Total Marks : 60]
N.B:	(1)	Question no.1 is compulsory.
	(2)	Attempt any four questions out of remaining six questions.
1.	(a)	Using mathmetical Induction prove that 5n-1 is divisible by 4 for n>∼1	05
	(b)	What is the minimum number of students required in Discrete Structure class to be sure that at least six will receive the same grade. if there are five possible grades A,B,C,D,E?	05
	(c)	Show that if relation on set A transitive and irreflexive then it is symmetric	05
	(d)	Draw the Hasse diagram of D60 and check if it is lattice?	05
2.	(a)	Among the integers 1 to 1000:   (i) How many of them are not divisible by 3, nor by 5, nor by 7?   (ii) How many are not divisible by 5 and 7 but divisible by 3?	10
	(b)	Define Universal and Existential quantifiers. Transcribe the following into logical notation. Let the universe of discourse be the real numbers.      (i) There are positive values of x and y such that x.y > 0      (ii) For every value of x there is some value of y such that x.y = 1      (iii) There is a value of x such that if y is positive then x+y is negative.	10
3.	(a)	Explain Warshwall's algorithm. Let A = {1,2,3,4,5} and let R be a relation on A Such that R= {(1,1),(1,4),(2,2),(3,4),(3,5),(4,1),(5,2),(5,5)} Find transitive elesure of R by Warshwall's algorithm.	10
	(b)	Define Equivalence relation. let Z be set of integers. Define R on Z iff 6 divides (a-b). Show that R is equivalence relation. Find Z/R.	10
4.	(a)	Let f R → R f(x)=x3, g: R → R g(x)=4x2 + 1, h:R→R h(x)=7x-2 Find  (i) go(hog)     (ii) go(hof)	06
	(b)	Define with example injective, surjective and bijective function	06
	(c)	Define Hamiltonian path and Hamiltonian circuit and find it in K4,3	04
	(d)	Define with example Reflexive closure and symmetric closure	04
5.	(a)	Prove that if (F, +,.) is a field it is an integral domain.	10
	(b)	Consider the group G={1,2,3,4,5,6} under multiplication modulo 7.      (i) Find multiplication table of G, is G abelian Group.      (ii) Find the identity and inverse of each element	10
6.	(a)	Find the solution of recurrence relation: a3 = 5 an-1 - 6an-2 + 7n	04
	(b)	Consider the (2,5) group encoding function - e:B2 → B5 defined by e(00) = 00000     e(10) = 10101     e(01) = 01110     e(11) = 11011 Decode the following relative to maximum likelihood decoding function. (i) 11110     (ii) 10011      (iii) 10100	06
	(c)	R={0,2,4,6,8} Show that R is commutative ring under addition and multiplication modulo 10	06
	(d)	Define subgroup and normal subgroup with example.	04
7.	(a)	Determine whether lattice D30 is distributive, complemented or both. Justify your answer.	06
	(b)	Let G be the group integers under the operation addition, and H be group of all even integers under the operation of addition, show that the function f: G→H is as isomorphism.	06
	(c)	Define and explain bipartite graph, complete bipartifc graph with example.	04
	(d)	Find all spanning trees of the following graph	04