Discrete Structures - May 2012

Computer Engineering (Semester 3)

TOTAL MARKS: 80
TOTAL TIME: 3 HOURS (1) Question 1 is compulsory.
(2) Attempt any three from the remaining questions.
(3) Assume data if required.
(4) Figures to the right indicate full marks. 1(a) Prove that if A is subset of C and B is subset of C, then (A U B) is subset of C.(5 marks) 1(b) Prove that maximum number of node on level n of a binary tree is 2ⁿ, where n >= 0(5 marks) 1(c) Prove that if any 14 numbers from 1 to 25 are chosen, then one of them is multiple of another(5 marks) 1(d) Prove that in any ring(R+)the additive inverse of each ring element is unique(5 marks) 2(a) Let Q be the set of positive rational numbers which can be expressed in the form 2^a3^b, where a and b are integers. Prove that algebraic structure (Q . ) is a group, Where dot(.) is multiplication operation(7 marks) 2(b) Determine whether the poset with the following Harse diagrams are lattices or not. Justify your answer
(7 marks) 2(c) Let r be the relation on set of real numbers such that aRb if and only if a-b is an integer. Prove that R is an equivalence relation(6 marks) 3(a) Find the solution of recurrence relation: a_n = 5a_n-1 - 6a_n-2 + 7ⁿ(7 marks) 3(b) Show that the following expressions is tautology (use law of logic):
(( P?Q) ? ~(~P(~Q?~R)) ? (~P?~Q) ? (~P?~R))(7 marks) 3(c) Let A={1,2,3,4} for the relation R whose matrix is given below. Find the matrix of transitive closure using warshall algorithm
(6 marks) 4(a) In a survey of 60 people, it was found that 25 read Business India, 26 read India Today, 26 read Times of India, 11 read both Business India and India Today, 09 read both Business India and Times of India, 08 read both India Today and Times of India, 08 read none of the three.
i. How many read all 3?
ii. How many read exactly one?(8 marks) 4(b) Use induction to prove that 7ⁿ - 1 is divisible by 6 for n = 1,2,3...(6 marks) 4(c) Let G be the group and let a and b are elements of G then verify that (ab)^-1 = b^-1a^-1(6 marks) 5(a) Consider (3,8) encoding function e: B³ ? B⁸ 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?(8 marks) 5(b) Prove that if (F,+,.) is a field then it is a integral domain(6 marks) 5(c) A connected planar graph has 9 vertices having degrees 2,2,2,3,3,3,4,4,5. How many edges are there?(6 marks) 6(a) Let G be the group of integers under the operation addition and H be the group of all even integers under the operation of addition. Show that the function f: G ? H is an isomorphism(8 marks) 6(b) Define Eulerian, Hamilton path and circuit with example. What is the necessary and sufficient condition for euler path and circuit?(6 marks) 6(c) Suppose R and S in the relation from A to B, then prove that:
(R ? S)^-1 = R^-1 ? S^-1 and (R U S)^-1 = R^-1 U S^-1(6 marks) 7(a) Consider the chains of divisors of 4 and 9, i.e, L1={1,2.4} and L2={1,3,9} and partial ordering relation of division on L1 and L2. Draw the lattice L1*L2(5 marks) 7(b) Prove that the set {1,2,3,4,5,6} is group under multiplication modulo 7?(5 marks) 7(c) How many paths of length 4 are there from a to d in simple graph as shown below:
(5 marks) 7(d) Find the complement of each element in D20 and D30(5 marks)