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

Discrete Structures (DS) Semester 3 (Revised Course) (3 Hours) May 2009
VR-3330 [Total Marks : 60]
N.B:	(1)	Question no.1 is compulsory.
	(2)	Attempt any four questions out of remaining six questions.
	(3)	Assumptions made should be clearly stated.
	(4)	Figures to the right indicate full marks.
	(5)
1.	(a)	Prove that A x(B ∩ C) = (A x B) ∩ (A x C).	04
	(b)	Prove there is no rational number p/q whose square is 2.	04
	(c)	Show than n3+2n is divisible by 3 for all n > 1.	06
	(d)	Among the integers 1 and 300,      (i) How many of them are divisible by 3,5 or 7 and are not divisible by 3 nor by           by 5 nor by 7?      (ii) How many of them are divisible by 3 but not 5 nor by 7?	06
2.	(a)	Prove that if any 14 integers from 1 to 25 are chosen, than one of them is a multiple of another	04
	(b)	Solve the recurrence relation dn = 2dn-1- dn-2 with initial conditions d1=1.5 and d2 = 3.	04
	(c)	Let A = Z, the set of integers and let R be the relation less than. Is R Transitive?	06
	(d)	Negate the statement. For all real numbers x, if x> 3 then x2>9.	06
3.	(a)	Let A = {a, b, c, d, e}and       R = { (a,a), (a,b), (b,c), (c,e), (c,d), (d,e) } Compute (i) R2 and R∞.	06
	(b)	Let A = { 1, 2, 3, 4 } and let R = { (1,2), (2,3), (3,4), (2,1) } Find Transitive Closure of R using Warshall's algorithms.	06
	(c)	Explain the Equivalence Class with an Example.	04
	(d)	Explain with an Example dual of the poset.	04
4.	(a)	Show that in bounded is distributive lattice, if a complement exists. it is unique.	06
	(b)	Determine whether the following posets are boolean algebras. Just your answers      (i) A = { 1, 2, 3, 6} with divisibility.      (ii) D20 : divisors of 20 with "divisibility".	06
	(c)	Explain primitive Recursive Function. Every primitive recursive function is a total function, justify.	04
	(d)	(i)  Is every Eulerian graph as Hamiltonian? (ii)  is every Hamiltonian graph an Eulerian ?       Justify with the necessary graph.	04
5.	(a)	So that if set A has 3 elements, than we can find 8 relations on A that all have the same symmetric closure.	06
	(b)	Draw the Hasse diagram of the poset A = { 2, 3, 6, 12, 24, 36, 72 } Under the relation of divisibilty. is this poset a lattice? justify.	06
	(c)	Let A = { 0, -1, 1} and B = { 0, 1}, Let f : A → B where f(a) = | a |. Is f onto?	04
	(d)	State and prove right or left cancellation property for a group.	04
6.	(a)	Prove that every field is an integral domain.	06
	(b)	Consider the chains of divisors of 4 and 9 i.e.,L1= {1, 2, 4} And L2= {1, 3, 9}. Find partial ordering relationsof division on L1 and L2. Draw lattice of L1 x L2.	04
	(c)	Explain the linear recurrence relations with constant co-efficeints.	04
	(d)	Explain the types of generating function with an example.	04

7.	(a)	Consider the (3, 5) froup encoding function e : B3 → B5 defined by --     e (000) = 00000   e (100) = 10011 e (001) = 00110   e (101) = 10101 e (010) = 01001   e (110) = 11010 e (011) = 01111   e (111) = 11100 Decode the following words relative to a maximum likelihood decoding function-      (i) 11001     (ii) 01010     (iii) 00111	06
	(b)	Let G be the set of all nonzero real numbers and let     a * b = ab / 2. Show that (G, *) is an Abelian group.	06
	(c)	Let m = 2, n = 5 and   H = 1 1 0 0 1 1 1 0 0 0 1 0 0 0 1 Determine the group code B2 → B2	04
	(d)	Explain congruence relation with an example.	04