# Discrete Mathematics Structures 2011-12

Note (i) Attempt all questions.

(ii) Make suitable assumptions wherever necessary.

1.   Attempt any four parts of the following:

(a) Let A and B be sets. Show that AxB * BxA. Under what condition AxB = BxA ?

(b) Let R be a relation on R, the set of real numbers, such that R = {(x, y) | |x – y| < 1}. Is R an equivalence relation ? Justify.

(c) Let R be a relation on the set of positive real numbers so that its graphical representation consists of points in the first quadrant of the Cartesian plane. What can you expect ifRis(i) reflexive,(ii) symmetric,and(iii) transitive?

(d) Let f (x) = ax2 + b and g(x) = cx2 + d, where a, b, c and d are constants. Determine for which constants a, b, c and d (5×4=20)the following equation holds: f o g = g o f.

(e) Use mathematical induction to show that:

1 + 2 + 22 + . . . +2″ = 2n+I -1 for all nonnegative integers n.

(f)  Differentiate between proof by counter example and proof by cases methods.

2. Attempt any two parts of the following:

(a) Let (G, *) be a group, where* is usual multiplication operation on G. Then show that for any x, y e G following equations holds:

(i) (x’1)-1 = x

(ii) (xy)’1 = jr’ X’1

(b) What do you mean cosets of subgroup ? Consider the group Z of integers under addition and the subgroup H = {…, -10,-5,0,5,10,…} considering of the multiple of 5.

(i) Find the cosets of H in Z

(ii) What is index of H in Z ?

(c) Write out the operation table for [Z2Z, +2, x2]. Is Z22 a ring ? Is an integral domain ? Is a field ? Explain.

3.  Attempt any two parts of the following:

(a) Define a poset. Suppose that (S, < ) and (T, <2) are posets. Show that (S*T, <) is a poset where (s, t) < (u, v) if and only if s <jU and t <2v.

(b) Let [L, v, a] be a lattice and a, b, c e L. Prove :

(i)  a v b > a

(ii) a v b > b

(iii) a > b and a>c=>a>bvc

(c) Define a Boolean function of degree n. Simplify the following Boolean expression using Karnaugh maps

xyz + xy’z+x’y’z + x’yz + x’y’z’.

4. Attempt any two parts of the following:

(a) (i) Construct the truth table for :

[(pvq)A(p->r) A(q-» r)]-> r

(ii) Also show that above statement is a tautology by developing a series of logical equivalences.

(b) What do you mean by valid argument ? Are the following arguments valid ? If valid, construct a formal proof; if not, explain why.

For students to do well in discrete structure course, it is necessary that they     study hard. Students who do well in courses do not skip classes. Student who study hard do

well in courses. Therefore students who do well in discrete structure course do not skip class.

(c) Express the following statements using predicates and quantifiers:

(i)  For every student in this class, that student has studied mathematics.

(ii) Some student in this class has visited United States.

(iii) Every student in this class visited either Canada or United States.

5. Attempt any two parts of the following :

(a) What is a binary search tree ? Form a binary search tree for the words vireo, warbler, egret, grosbeak, nuthatch, and kingfisher. Explain each step.

(b) Solve the following:

yn+2-yn+12yn = n2

(c) Write short notes on any three of the following :

(i) Multi Graphs

(ii) Planar Graphs

(iii) Recursive algorithms

(iv) Pigeon hole principle.