B3B036S Pages: 2

Reg. No. Name:
APJ ABDUL KALAM TECHNOLOGICAL UNIVERSITY
THIRD SEMESTER BTECH DEGREE EXAMINATION JULY 2017

Course Code: CS 201
Course Name: DISCRETE COMPUTATIONAL STRUCTURES (CS, IT)
Max Marks: 100 Duration: 3 hrs
PART A

Answer all questions, 3marks each.
1. Draw the Hasse diagram for the divisibility relation on the set A ={2,3,6,12,24,36}
2. Define equivalence relation? Give an example of a relation that is not an equivalence relation?
3. In how many different ways can the letters of the word 'MATHEMATICS' be arranged such
that the vowels must always come together?

4. Define homomorhism and isomorphism?

PART 8
Answer any 2 Questions, 9 marks each.

5. (a) Consider {£ and h are functions on integers ता) = 77, g(n) =n + 1, h(n) = ೧-1. Determine

i) fogoh ii) gofoh 114) hofog (6)
(b) State Pigeonhole Principle. Prove that at least two of the children were born on the same
day of the week. (3)
6. (a) Solve the recurrence relation a, = 48 ‏مےم 1 74 بے‎ +(n +1) 2" (6)
(b) Show that set of all integers is countable (3)

7. (a) Find the number of integers between | and 250 both inclusive that are not divisible by any

of integers 2,3,5 and 7. (5)

(0) If * isthe binary operation on the set र of real numbers defined by a*b=a+b+2ab.

Find if { R, *} is a semigroup. Is it commutative? (4)
PART C

Answer all questions, 3marks each.

8. Show that the 5९ {1,2,3,4,5} is not a group under addition modulo 6.
9. Prove that every distributive lattice is modular.
10. Show that the set Q+ of all positive rational numbers forms an abelian group under the
operation * defined by a*b= கஸ்‌; a,be 0+
11. Simplify the Boolean expression a’b’c + ab’c + a’b’c’
Page 1 of 2