# Discrete Structure 2008-09

Note : Attempt all questions.

1. Attempt any four parts of the following :

(a) Show that 2n <n \ for n > 4

(b) Let D(x) denote “number of divisors of x”.

Show that £>(x) is primitive recursive.

(c) Show that there exists a one-to-one mapping from Ax B to B x A . Is it also onto ?

(d) Define equivalent class generated by an element of a set. Is it partition the set ?

(e) Prove that the relation “Congruence modulo m” given by

= = {(*> y) I x- y is divisible by mover the set of positive integers is an equivalence relation. Show also that if

xl = jyj and x2 = y2 then

(Xl + X2 ) = (yx + )

(f) 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 if R is (i) reflexive

(ii) symmetric, and (iii) transitive ?

2. Attempt any four parts of the following :

(a) If for each a and b in group G, (aby = a2b2 show that G is abelian.

(b) Show that the composition of two congruence relations on a set is not necessarily a congruence relation.

(c) Show that the set N of natural numbers is a semigroup under the operation

x * y = max (# • ;y). Is it a monoid ?

(d) Prove that any infinite cyclic group is isomorphic to the group (z, +} integers.

(e) Determine all values of x from the given field which satisfies the given equation :

(i)  x +1 = —1 over z2, z3, z5 and z7.

(ii) 2x + l = 2 over z3 and z5

(iii) 5x +1 = 2 over z5

(f) Explain Boolean ring with suitable examples.

3. Attempt any two parts of the following :

(a) Show that if  (L, c:, o) is a lattice then

(L, 2, r% is also a lattice. Also show that cartesian product of two lattices is a lattice.

(b) Use K-map to find simplified form of Boolean expression :

(c) Define Tree. Describe different traversal algorithms for a binary tree.

4.  Attempt any two of the following parts

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

(1) 1(PaQ)^(1Pv-1Q)

(2)  ((/* —> Q) v v (P —> Q —> 72)

(ii) Give the recursive definition of well formed formulas. Write in symbolic form the statement.

“The crop will be destroyed if there is a flood.”

(b) Show the following equivalences :

<i) (p c) a(Q -» c) <=> (PvQ) -> c

(ii) ((P a Q a A) —> C) a (^4 —» (P v Q v C))

<=> (A a (P ,*<})) —> c

(c) Show that

(i) (x)(P(x) vQ(x))=>(x)P(x)v(3x)Q(x)

(ii) (x)P(ji:) A (3x)Q(x) (3ac)(P(ac) a Q(x))

5. Attempt any two of the following parts :

(a) (i) Solve the recurrence relation

fn~ fn-1 + fn-2 (ii) Explain the terms – walk, path, circuit.

(b) Show that a connected graph G is an Euler graph if and only if it can be decomposed into circuits.

(c) Write short notes on the following :

(i) Planer graph

(ii)  Euler graph

(iii) Graph coloring.