Discrete Mathematics Structure Paper 2010-2011

                                                                       B.TECH

                                               (SEM-3) THEORY EXAMINATION 2010-2011  

                                                 DISCRETE MATHEMATICAL STRUCTURES

               TIME : 3 HOURS                                                                         TOTAL MARKS : 100

         NOTE: - Attempt all question.

1.      Attempt any four parts of the following :

(a)   Consider a universal set U={x|x is an integer}.Assume that X={x|x is a positive integer},Z={x|x is an even integer} and Y={x|x is a negative odd integer}. Find the following :

·         X-Y

·         X^c-Y, where X^c is the complement of set X.

(b)   Consider a set S_k={1,2,……..,K}. Find  and .

(c)    Let R be a relation on N, the set of natural numbers such that

R={(x,y)|2x+3y and x,y € N}.

Find: • The domain and co domain of R,

           • R^-1

(d)   Show that the functions f(x)=X³+1 and g(x)=(x-1)^1/3 are converse to each other.

(e)   Prove that if f_n is a Fibonacci number than

F_n= 1/√5[{(1+√5)/2}ⁿ⁺¹  - {(1-√5)/2}ⁿ⁺¹]  for all n € N, the set of natural numbers.

(f)      Let f:X→Y and X=Y=R, the set of real number. Find f^-1 if

• f(x)=X²

• f(x)=(2x-1)/5.

2.      Attempt any two parts of the following :

(a)   Let G={1,-1,-I,i} with the binary operation multiplication be an algebraic structure, where i=√-1.

• Determine whether G is an Abelian.

• If G is a cyclic group, then determine the generator of G.

(b)   Let G=(Z²,+) be a group and let H be a subgroup of G, when H={(x,y)|x=y}. Find the left cosets of H in G. Here Z is the set of integers.

(c)    Prove that (R,+,*) is a ring with zero divisors, where R is 2×2 matrix and + and * are usual addition and multiplication operations.

3.       Attempt any two parts of the following :

(a)   Let (L₁,≤) and (L₂,≤) be lattices as shown below. Then draw the Hasse diagram for the lattice (L,≤), where L=L₁×L₂.

                                                                                                                       L₁

                                 L₁

                                                                              x                                                         y

                                                                      L₂                                       

                                                                                                                     L₂

(b)

i)        Simplify the following Boolean function using K-Map :

f(x,y,z)=∑(0,2,3,7)

ii)       How are sequential circuit different from combinational circuits?

(c)Describe the Boolean duality principle. Write the dual of each Boolean equations :

i)        x+x’y=x+y

ii)      (x.1)(0+x’)=0

    

4.      Attempt any two parts of the following :

(a)   (i) Show that the statements: P→Q and ⁿQ→ⁿP are equivalent.

(ii) State the contraposition and converse statement of the following statement:

       “If the triangle is equilateral, then it is equiangular”.

(b)   Show that premises : P→Q,R→S,ⁿQ→ⁿS,ⁿⁿP

And (TᶺU)→R imply the conclusion ⁿ(TᶺU).

                          © What do the following expressions means?

i)                    (₳x)(x²≥x)

ii)                  (₳x)<0(x²>0)

iii)                (Ǝx)!=0(x²!=0)

Here the domain in each case consists of the real numbers.

5.      Attempt any two parts of the following :

(a)   Determine the value of each of these prefix expressions :

I)                    -*2/993,

II)                  +-*355/↑232.

(b)   For which values of n do these graphs have an Euler cycle :

i)                    K_n, a complete graph of n-vertices.

ii)                  C_x, a cycle of n-vertices.

(c)    Solve the recurrence relation :

T(n)=64(n/4)+n⁶ where n≥4 and a power of 4.

(d)   Solve the recurrence relation: a_n=3a_n-1+4^n-1 for n≥0 and a₀=1.

(e)   Determine the number of bit strings of length 10 that either begin with three0’s or end with two 1’s.

(f)     How many different rooms are needs to assign 500 classes, if there are 45 different time periods during in the university time table that are available?