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

Discrete Structures (DS) Semester 3 (Revised Course) (3 Hours) December 2011
MP-4117 [Total Marks : 60]
N.B:	(1)	Question no.1 is compulsory.
	(2)	Answer any four out of remaining six questions.
	(3)	Assumptions made should be clearly stated.
	(4)	Assume any suitable data wherever required but justify the same.
	(5)	Figures to the right indicate marks.
	(6)	illustrate answer with sketches wherever required.
1.	(a)	A survey on a sample of 25 new cars being sold of a local auto dealer was conducted to see which of three popular options, air conditioning A, radio R, and popular windows W, were already installed. The survey found, 15  had air conditioning 12  had radio 11  had power windows 5   had air conditioning and power window 9   had air conditioning and radio 4   had radio and power windows 5   had all three options. Find the no. of cars having: (i) Only one of these options (ii) radio & power windows but not air conditioning (iii) none of these options.	06
	(b)	Explain the following terms with suitable example.   (i)  Disjoint set   (ii)  Symmetric difference   (iii)  Partition product.	04
	(c)	Given A= {1, 2, 3, 4} and B {x, y, z}. Let R be the following relation from  A to B : R= {(1,y), (1,z), (3,y), (4,x), (4,z)} (i)  Determine the matrix of the relation. (ii)  Draw the arrow diagram of R. (iii)  Find the inverse realtion R-1 of R (iv)   Determine the domain and range of R.	06
	(d)	Prove the mathematical induction that 6n+2 + 72n+1 is divisible by 43 for each +ve integer n.	04
2.	(a)	Write English sentences for following where: P(x) : x is even,  Q(x): x is prime, R(x,y) : x + y is oven (i)   ∃x ∀y R(x,y) (ii)  ∀x ∃y R(x,y) (iii)  ∼(∃x P(x)) (iv)  ∼(∀x Q(x)) (v)   ∀x ∃y R(x,y) (vi)  ∃x ∀y R(x,y) (vii) ∀x (∼Q(x)).	07
	(b)	Show that if 30 dictionaries in a library contain total of 61,327 pages, then one of the dictionaries must have at least 2045 pages.	06
	(c)	Let G = {0, 1, 2, 3, 4, 5} (i)  Prepare composition table with respect to '+6' (ii)  prove that G is an abelian group with respect to '+6' (iii)  Find the inverse of 2, 3 and 5. (iv)  Is it cyclic? (v)   Find the order of 2, 3 and sub groups generated by these elements.	07
3.	(a)	Determine whether following graphs are isomorphic:	06
	(b)	(x1 ∧ x2) V (x1 ∧x3) V (x2 ∧x3) be the Boolean expression. Write E(x1, x2, x3) in Disjunctive & Conjuunctive Normal Form.	07
	(c)	f: R→R is defined as f(x) =4x2+1 h: R→R is defined as h(x) =7x-1 find the rule of defining (hog)of, go (hof).	07
4.	(a)	Explain the Eulerian & Hamiltonian path & circuit with suitable example.	06
	(b)	What is the hamming distance? Consider (3,8) encoding function e: B3→B8 defined by   e(000) = 00000000 e(001) = 10111000 e(010) = 00101101 e(011) = 10010101 e(100) = 10100100 e(101) = 10001001 e(110) = 00011100 e(111) = 00110001 and let d be the (8,3) maximum likelihood decoding function associated with e. How many errors can (e,d) correct?	07
	(c)	Determine whether D625 is a Boolean algebra. justify your answer.	07
5.	(a)	A function f : R {7/3} → R - {4/3} is  defined as:                     f (x) = 4x - 5/3x - 7 Prove that 'f' is bijective and find the rule for 'f'.	07
	(b)	Let A = }1, 2, 3, 4, 6} and let R be the relation on A defined by "x divides y" written x/y (Note x/y if there exists an integer z such that xz=y.) (i)  Write R as a set of ordered pairs. (ii)  Draw its directed graph. (iii)  Find the inverse relation of R.	06
	(c)	Let A = {11, 12, 13, 14} and Let R = {(11,12), (12,13), (13,14), (12,11)}. Find transitive Closure of R using warshall's algorithm.	07
6.	(a)	Let R be the following equivalence relation on the set A={1, 2, 3, 4, 5, 6}:       R = {(1,1), (1,5), (2,2), (2,3), (2,6), (3,2), (3,3), (3,6), (4,4), (5,1), (5,5), (6,2), (6,3), (6,6)}. Find the partitions of A inducted by R, i.e., find the equivalence classes of R.	06
	(b)	Define a lattice. Let X = {1,3,5,15,30,60,90,180,} with the relation of divisibility. Draw the hasse diagram for it. Whether it is a lattice? Justify your answer. Find the complements of all them elements.	07
	(c)	Determine the sequence whose recurrence relation is an=4an-1+5an-2 with a1=2 &  a2=6.	06
7.	(a)	Explain various operations on the binary trees.	06
	(b)	Verify whether (Use laws of logic)           ((PVQ) ∧⌉(⌉P∧(⌉QV⌉R))V(⌉P∧⌉)V(⌉P∧⌉R) is tautology. Define universal and existential quantifier with suitable example.	07
	(c)	Define a Ring & Field. Let R = {0, 2, 4, 6, 8}. Show that R is a Commutative ring under additions and multiplication modulo 10. Verify  whether it is field or not.	07