B B7070

Total Pages: 2
Reg No.: Name:

APJ ABDUL KALAM TECHNOLOGICAL UNIVERSITY
THIRD SEMESTER B.TECH DEGREE EXAMINATION, DECEMBER 2017

Course Code: ೮5201
Course Name: DISCRETE COMPUTATIONAL STRUCTURES (CS, IT)
Max. Marks: 100 Duration: 3 Hours
PART A
Answer all questions, each carries 3 marks. Marks
1 Assume A={1,2,3} and p(A) be its power set. Let ल be the subset relation on (3)

the power ser. Draw the Hasse diagram of (p(A),S)
2 Let R denote a relation on the set of ordered pairs of positive integers such that (3)
(x, y)R(u, v) iffxv = yu. Show that R is an equivalence relation
3 Prove that in any group of six people, at least three must be mutual friends or at least (3)
three must be mutual strangers.
4 Define GLB and LUB for a partially ordered set. Give an example (3)
PART B
Answer any two full questions, each carries 9 marks.
5 2) Suppose f(x)=x+2,g(x)= ೫-2 and h(x)=3x for x € R,where R is the set of real (4)
numbers. Find gof,fo 8, 101, 2 ०0 8, 101, 1 0 2.1 01 810 (101) ० ९
b) Prove that every equivalence relation on a set generates a unique partition of the (5)
set with the blocks as R-equivalence classes
6 9) Show that the set N of natural numbers 15 a semigroup under the operation (3)
x*y=max(x,y). Is ita monoid?
b) Solve the recurrence relation a, + 5281-1 + 6೩.2 = 31 2 ort (6)
7 a) Show that for any commutative monoid , the set of idempotent elements (5)

of M forms a submonoid.

b) Define subsemigroups and submonoids. (4)
PART C
Answer all questions, each carries 3 marks.
8 Show that, for an abelian group, (a * 0) । = ந்தி பறி 3)
9 Show that every chain is a distributive lattice. (3)
10 Simplify the Boolean expression a’b’ctab’c+a’b’c’ (3)

11 Let © = (६1, a, 92, a°} (൪ = 1) be a group and त = (1, 22} 15 ೩ subgroup of Gunder (3)

multiplication. Find all cosets of H.

Page 1௦11