Discrete Structures - Dec 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 by mathematical induction xⁿ-yⁿ is divisible by x-y.(5 marks) 1 (b) How many vertices are necessary to construct a graph with exactly 6 edges in which each vertex is of degree 2.(5 marks) 1 (c) Show that a relation is reflexive and circular if and only if it is an equivalence relation.(5 marks) 1 (d) Prove that the set G={1,2,3,4,5,6} is an abelian group under multiplication modulo 7.(5 marks) 2 (a) Is it possible to draw a tree with five vertices having degrees 1,1,2,2,4?(4 marks) 2 (b) Find how many integers between 1 and 60 are
i) not divisible by 2 nor by 3 and nor by 5.
ii) Divisible by 2 but not by 3 and nor by 5.(8 marks) 2 (c) Solve the recurrence relation a_r+2-a_r+1-6a=4.(8 marks) 3 (a) Show that A?(B?C)=(A?B)?(A?C)(4 marks) 3 (b) State and explain Pigeonhole principle, extended Pigeonhole principle. How many numbers must be selected from the set {1,2,3,4,5,6} to guarantee that at least one pair of these numbers add up to 7?(8 marks) 3 (c) Let R be a relation on set A={1,2,3,4}, given as
R={(1,1), (1,4), (2,2), (2,3), (3,2), (3,3), (4,1), (4,4)}.
Find transitive closure using Warshall's Algorithm.(8 marks) 4 (a) Find the generating function for the following sequence
i) 1,2,3,4,5,6......
ii) 3,3,3,3,3......(4 marks) 4 (b) Show that the (2,5) encoding function e:B²?B⁵ defined by
e(00)=00000 e(01)=01110
e(10)=10101 e(11)=11011 is a group code.
How many errors will it detect and correct.(8 marks) 4 (c) Draw Hasse Diagram of D₄₂. Find the complement of each element in D₄₂.(8 marks) 5 (a) Define Distributive Lattice along with one appropriate example.(4 marks) 5 (b) Let the functions f,g and h defined as follows:
f:R→R, f(x)=2x+3
g:R→R, g(x)=3x+4
h:R→R, h(x)=4x
Find gof, fog, hof, gofoh(8 marks) 5 (c) $$ Let \ H= \begin{vmatrix} 1 &0 &0 \\0 &1 &1 \\1 &1 &1 \\1 &0 &0 \\0 &1 &0 \\0 &0 &1 \end{vmatrix} $$ Be a parity check matrix. Determine the group code e_H: B³ ? B⁶.(8 marks) 6 (a) Determine $$ [(p\Rightarrow q)\wedge q]\Rightarrow \neg p $$ is a tautology.(4 marks) 6 (b) Define isomorphic graphs. Show that following graphs are isomorphic (8 marks) 6 (c) R be a relation on set of integers Z defined by
R={(x,y)|x-y is divisible by 3}
Show that R is an equivalence relation and describe the equivalence classes.(8 marks)