# Discrete Mathematics 2010-11

Note : (I) Attempt all questions.

(2) Each question carries equal marks.

1.    Attempt any four parts of the following:—

(a) If R is an equivalence relation on a set A, then show that R_l is also an equivalence relation on A.

(b) If R = {(a, b), (b, c), (c, a)} and A = {a, b, c}, then find reflexive, symmetric and transitive closure of R by the composition of relation R.

(c) Show that for any two sets A and B

A – (A n B) = A – B, without Venn diagram.

(d) What are the recursively defined functions ? Give the recursive definition of factorial function.

(e) Let f, g, h e R be defined as

f(x) = x + 2, g(x) = x – 2, h(x) = 3x v x e R.

Find g o f, h o f and f o h o g.

(f)  State and prove Pigeon hole principle.

2.  Attempt any four parts of the following:-

(a) Consider the operator * defined on z, the set of integers As a * b = a + b + I for all x, y e z. Show that (z, *) is an abelian group.

(b) Show that every cyclic group is abelian but the converse is not true.

(c) For a Group G prove that G is abelian iff

(ab)2 = a2 b2 v a, b e G

(d) If H and K are any two subgroups of a group G, then show that HuK will be a subgroup iff H c K or K c H.

(e) Define field with one example.

(f)  Consider a ring (R, +, •) defined by a • a = a. Determine whether the ring is commutative or not.

3. Attempt any two parts of the following:—

(a) Construct the truth table :

(i) (P -» Q) v R) v (P -> Q -> R)

(ii) (P Q) a (P -> R).

(b) Is the statement

((P -> Q) a (Q -► R)) -» (P -> R) a tautology ?

(c) Find out whether the following formula are equivalent or not:—

(i)                  (P a (P-*<?))-» Q 00 (P->Q)^(lPvQ).

4.  Attempt any four parts of the following:—

(a) If x and y denote the pair of real numbers for which 0 < x < y, prove by mathematical induction 0 < x” < y” for all natural number n.

(b) Show that: “C + “C = n+lC. r       r-l         r

(c) Solve the recurrence relation : a=a_, +a_2,r>2 with a0 = 1, a, – 1.

(d) Find the solution of recurrence relation by generating function method:

3,-2a, , +a,J = 2‘’rS2a0 = 2a! = L

(e) Use quantifiers to say that V3 is not a rational number.

(f)  (i) How many selections any number at a time may be

made from three white balls, four green balls, one red ball and one black ball if at least one must be chosen.

(ii) In how many ways can a five-card hand be dealt from a deck of 52 cards ?

5. Attempt any two parts of the following:—

(a) (i) Differentiate between Euler graph and Hamiltonian

graph with examples.

(ii) Show that a Hamiltonian path is a spanning tree.

(b) Define the fol lowing with one example:

(i)  Bipartite graph.

(ii) Complete graph.

(iii)   Binary tree.

(iv)   Chromatic number of a graph.

(v) Isomorphic graphs.

(c) (i) Define degree of a vertex. Prove that the sum of degrees of all vertex of a graph is equal to the twice of the number of edges in a graph.

(ii) Define tree. Show that in a tree of n vertex will have n-I edges.

1. bharat

very nice