## Discrete Structures - May 2016

### 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)** Find how many integers between 1 and 60 are not divisible by 2 by nor by 3 and nor by 5 repectively.(6 marks)
**1(b)** By using mathematical induction prove that $1+a+a^2+....a^n = \frac{1-a^{n+1}}{1-a} $/, where n≥0(8 marks)
**1(c)** Let A={1,

2,

3,

4,

5} and R be the relation defined by a R b if and only if a<b. compute="" r,="" <br=""> R^{2} and R^{3}. Draw digraph of R,

R^{2} and R^{3}.</b.><>(8 marks)
**2(a)** Show that a group G is Ablian, if and only $ \left ( ab \right )^2 = a^2b^2 $/ for all elements a and b in G.(6 marks)
**2(b)** Let A={1,

2,

3,

4,

6}=B,

a R b if and only if a is multiple of b Find R. Find each of the Following (i) R(4)

ii) R(G)

iii) R{2,

4,

6}).(6 marks)
**2(c)** Show that the (2,

5) encoding function e: B^{2}→B^{5} 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)
**3(a)** State pigeon hole and extended pigeon hole principle. Show that 7 colors are used to paint 50 bicycles, at least 8 bicycle will be of same color.(6 marks)
**3(b)** Define distributive lattice. Show that in a bounded distributive lattice, if a complement exists, its unique.(6 marks)
**3(c)** Functions f,

g,

h are defined on a set, X={1,

2,

3} as f={(1,

2)

(2,

3)

(3,

1)} g = { (1,

2}

(2,

1)

{3,

3)} h = {(1,

1)

(2,

2)

(3,

1) }

i) Find f o g,

g o f are they equal?

ii) Find f o g o h and f o h o g(8 marks)
**4(a)** Define Eular path and Eular circuit, determine whether the given graph has Eular path and Eular circuit.

!mage(6 marks)
**4(b)** Define Hamiltonian path and Hamiltonian circuit, determine whether the given graph has Hamiltonian path and Hamiltonian circuit.

!mage(6 marks)
**4(c)** Define isomorphic graphs. Show that the following two graphs are isomorphic.

!mage(8 marks)
**5(a)** What is an Universal and existential quantifiers? Prove that distribution law.(p∨q∧r)=(p∨q)∧(p∨r)(6 marks)