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 M

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 M

1(c)
Let A={1,

2,

3,

4,

5} and R be the relation defined by a R b if and only if a R

R

2,

3,

4,

5} and R be the relation defined by a R b if and only if a

^{2}and R

^{3}. Draw digraph of R,

R

^{2}and R

^{3}.

8 M

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 M

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}).

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 M

2(c)
Show that the (2,

5) encoding function e: B

e(01) = 01110

e(10) =10101

e(11) = 11011 is a group code. How many errors will it detect and correct?

5) encoding function e: B

^{2}→B^{5}defined by e(00) =00000e(01) = 01110

e(10) =10101

e(11) = 11011 is a group code. How many errors will it detect and correct?

8 M

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 M

3(b)
Define distributive lattice. Show that in a bounded distributive lattice, if a complement exists, its unique.

6 M

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

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 M

4(a)
Define Eular path and Eular circuit, determine whether the given graph has Eular path and Eular circuit.

!mage

!mage

6 M

4(b)
Define Hamiltonian path and Hamiltonian circuit, determine whether the given graph has Hamiltonian path and Hamiltonian circuit.

!mage

!mage

6 M

4(c)
Define isomorphic graphs. Show that the following two graphs are isomorphic.

!mage

!mage

8 M

5(a)
What is an Universal and existential quantifiers? Prove that distribution law.(p∨q∧r)=(p∨q)∧(p∨r)

6 M

More question papers from Discrete Structures