# Discrete Mathematical Structures 2009-10

Note : (i) Answer all questions.

(ii) All questions carry equal marks.

1 Attempt any four parts :

(a)      Let A be a set with 10 distindt elements.

Determine the following :

(i)  Number of different binary relations on A

(ii) Number of different symmetric binary relations on A

(b)      Suppose S and T are two sets and / is a functions from S to T. Let R- be an equivalence relation on T. Let R2 be a binary relation on S such that y) e i?2 if and only if (f(x), f(y)) e Show that Ro is also an equivalence relation.

(c)    Prove that union of two countably infinite set is countably infinite.

(d) Composition of functions is commutative. Prove the statement or give counter example.

(e) Prove that for any integer ri > 1,ill 1 r—Frt‘…………………………. + –7=r> »nVl V2 V3                                      \n

(f)  What do you understand by asymptotic behaviour of a numeric function ? Explain Big-Oh and Big-Omega notation.

2. Attempt any two parts :

(a) (i) Define group. Prove that if every element of a group G is its own inverse then G is abelian group.

(ii) Prove that Xp) is a group where the set is the set of all

non-zero residue classes modulo P,P is a positive prime number and Xp denotes the multiplication of residue classes modulo p

(b) (i) Prove the following or give counter

example : If (Hv *) and (H2, *) are both subgroups of the group (G, *) then <H1 *) is also a subgroup of (G, *).

(ii) State and prove Lagrange theorem.

(c) (i) Define and explain the following with

suitable example :

(a)   Cyclic group

(b)   Zero divisor of a ring

(c)   Order of an element of a group

(d)  Field.

(ii)  If G is a group of order n then order of any element a g G is a factor of n. Prove.

3. Answer any two parts :

(a) (i) Define a relation R on the set Z of all integers by m^n if and only if 9 om ~n . Determine whether R is a partial order or not 0

(ii) Let (A, <) and (B, <) be two posets. Prove that (AxB, <) is a poset, where (a, b) < (c, d) if and only if a <c, b <d

(iii) Draw the Hasse diagram of (A. <) where A = {3, 4, 12, 24, 48, 72} and the relation < be such that a < b if a divides b

(b) (i) Define distributive lattice and complemented lattice. Prove that in a distributive lattice, if an element has a complement then this complement is unique.

(ii) Let E(Xj, X2, 3Cg) =(Xj V X2) v (» AX3) be a boolean expression over the two valued boolean algebra. Write E(xj, x2, .r3) in disjunctive normal form.

(c)    (i) Let a, b, c be elements in a lattice (A, <). Show that if a<b then

a v (b a c) < b a (a vc)

(ii) Simplify boolean function F given by

F(A, B, C, Z)) = 2 (0, 2, 7, 8, 10. 15)

using Karnaugh map.

4. Answer any two parts :

(a) (i) Given that the value of p q is false, determine the value of (p v q) —> q

(ii) Find a formula A that uses the variable p, q and r such that A is a contradiction.

(iii)  Write an equivalent formula for P A (Q <-> r) v (r <-> P) which neither contains biconditional nor conditional connectives.

(iv) The contrapositive of a statement S is given as “If x <2 then x + 4 < 6 ” write the statement S and its converse.

(b) (i) Prove that (p v q) => (p a q) is logically equivalent to p<=>q

(ii) Translate the following sentences in quantified expressions of predicate logic.

(a)     all students need financial aid.

(b)     Some students need financial aid.

(c)     (i) Show that following are not equivalent :

(a) V x (P(x) —» Q(x)) and V x P(x) —» Vx Q(x)

(b) Vx P(x, y) and 3y Vx P(x, y).

(ii) Show thatf ->~ Q* rvs, s q, p-+q<=> ~ p are inconsistent.

5. Answer any two parts :

(a) (i) Find the simple expression for the generating function of following discrete numeric function2 3 4 (r+1) ’ 3’ 9’ 27’

(ii) Solve the recurrence relation ar-6ar_j+8ar_2 = r- 4r given Oq = 8, Oj = 22

(b) (i) Find the number of integer solutions of the equation Xj + x2 + x3 + x4 + x~ = 30 where Xj >2, > 3, Xg > 4, x4 >2, x5 > 0

(ii) Given the in order and post order traversal of a tree T In order : BEHFACDGI Post order : HFEABIGDC Determine the tree T and its pre order.

(c) (i) Prove that for any connected planar graph, V-e + r = 2where v, e, r are the number of vertices, edges and regions of the graph respectively.

(ii) Define and explain the following ;

(a)Bipartite graph

(b)Chromatic number of a graph

(c)Binary search tree

(d) Adjacency matrix of a graph.