## 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^{n} - 3^{n} 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_{0}=5, a_{1}= -9 and a_{2}=15(7 marks)
**4 (a)** show that a group G is abelian if and only if (ab)^{2}=a^{2}b^{2} 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 a*b=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_{105} (b) D_{72}(6 marks)