# UPTU Previous Year Question Papers

# B Tech 3rd Semester

# Discrete Structure 2008-09

Note : Attempt all questions.

** 1. Attempt any four parts of the following :**

(a) Show that 2^{n} <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

x_{l} = jyj and x_{2} = y_{2} then

(_{Xl} + X_{2} ) = (y_{x} + )

(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 = a^{2}b^{2} 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 z_{2}, z_{3}, z_{5} and z_{7}.

(ii) 2x + l = 2 over z_{3} and z_{5}

(iii) 5x +1 = 2 over z_{5}

(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.