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² and R³. Draw digraph of R,
R² and R³.</b.></span>(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²→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) 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)