 MORE IN Discrete Structures
MU Computer Engineering (Semester 3)
Discrete Structures
May 2016
Total marks: --
Total time: --
INSTRUCTIONS
(1) Assume appropriate data and state your reasons
(2) Marks are given to the right of every question
(3) Draw neat diagrams wherever necessary

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 R2 and R3. Draw digraph of R,
R2 and R3.
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}).
6 M
2(c) Show that the (2,
5) encoding function e: B2→B5 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 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
8 M

4(a) Define Eular path and Eular circuit, determine whether the given graph has Eular path and Eular circuit.
!mage
6 M
4(b) Define Hamiltonian path and Hamiltonian circuit, determine whether the given graph has Hamiltonian path and Hamiltonian circuit.
!mage
6 M
4(c) Define isomorphic graphs. Show that the following two graphs are isomorphic.
!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