Discrete Structures - May 2014

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 8ⁿ - 3ⁿ is a multiple of 5 by mathematical induction, n ≥ 1(5 marks) 1 (b) Show that if a relation on set A is transitive an irreflexive, then it is asymmetric.(5 marks) 1 (c) Function f(x)=(4x+3)/(5x-2). Find f^-1(5 marks) 1 (d) What is the total number of vertices in a full binary tree with 20 leaves?(5 marks) 2 (a) Let f(x)=x+2, g(x)=x-2 and h(x)=3x for all x ? R. (R is the set of real number). Find (i) f° g° h (ii)h° g° f (iii) f° f° f(8 marks) 2 (b) Let R be a relation on the set of integers Z defined by a Rb if and only if a=m(mod 5). Prove that R is an equivalence relation. Find Z/R.(8 marks) 2 (c) Show that A x (B ∩ C) = (A x B) ∩ (A x B)(4 marks) 3 (a) Let A={1,2,3,4) and R={ (1,2), (2,3), (3,4), (2,1) }. Find the transitive closure using Warshall's algorithm.(6 marks) 3 (b) Consider the lattices L1={1,2,4}, L2={1,3,9} under divisibility. Draw the lattice L1 x L2.(7 marks) 3 (c) Solve the recurrence relation a_n = -3(a_n-1 + a_n-2) - a_n-3 with a₀=5, a₁= -9 and a₂=15(7 marks) 4 (a) show that a group G is abelian if and only if (ab)²=a²b² for all a,b ∈ G(6 marks) 4 (b) Prove that the set G={1,2,3,4,5,6} is an abellian group under multiplication modulo 7.(6 marks) 4 (c) Find the generating function for the following series
(i) {0,1,2,3,4,??}
(ii) {1,2,3,4,5 . . . . . .}
(iii) {2,2,2,2,2 . . . . . . .}
(iv) {0,0,0,1,1,1,1, . . . . . . . .}
(8 marks) 5 (a) Let $$H=\left[\begin{array}{cccccc}1 & 0 & 0 \\1 & 1 & 0 \\0 & 1 & 1 \\1 & 0 & 0 \\0 & 1 & 0 \\0 & 0 & 1\end{array}\right]$$ be parity check matrix.
Decode the following words relative to maximum likelyhood decoding function.
(i) 011001 (ii) 101011 (iii) 111010 (iv) 110110
(8 marks) 5 (b) Determine the Eulerian and Hamiltonian path, if exist, in the following graphs :-
(6 marks) 5 (c) Let G be the set of real numbers and let Let G be the set of real numbers and let ab=ab/2. Showthat (G,) is a abellian group (6 marks) 6 (a) (8 marks) 6 (b) Use the laws of logic to determine the following expression as tautology or contradiction.
[p^ (p ⇒ q)] ⇒ q(6 marks) 6 (c) Draw the Hasse Diagram of the following:
(a) D₁₀₅ (b) D₇₂(6 marks)