a knowledge trading engine...

Thapar University 2005 M.C.A Discrete Mathematical Structure - Question Paper

Friday, 19 April 2013 02:35Web

Page 1 of 2

Thapar Institute of Engineering & Technology
MCA (1st Year)
Final Term exam
CA003(Discrete Mathematical Structure)

School of Mathematics and Computer Applications, T.I.E.T., Patiala End semester Examination (December, 16, 2005)

Time: 3 Hours Discrete Mathematical Structure (CA-003) Max. Mark: 45

Note :(i) Answer any FIVE questions (ii) Answers of only first five questions will be checked (iii) Evaluated answ er sheet shall be shown on December 10, 2006 at 3.00 P.M. in B-208. _

o. 1(a) (b)

Simplify the following on-off n formula and represent the simplifi

etwork using sta ed form in netwo

ndard logical equivalent

rk.

5

4

T th11

In calculus the definition of thi f(x) L as x - a if and only that for all xe/(0<|x-a|< expression f(x) -> L as x a..

-K-J

s limit of a fii if for every e > 0 e) then |/l

1-h-J \

nction /(x) is given as there exists a S > 0, so x)-L|<f. Negate the

Q. 2(a) (b)

Write the following argument ir verify the validity of the argume all the adults (18 years or abo\ universe of discourse All crec All credit union employees w Excel. Anita works for the ere Mohan knows Excel but doe doesn't write loan applications union.

Define reflexive and symmetr

A = {1, 2,3, 4} and R be a reli [0 1 0 0 10 10

M_r =

* 0 0 0 1

[o 0 0 1_

Obtain transitive closure of R us

i symbolic form using predicate and then nt using predicate calculus by assuming e) who are presently residing in Delhi as it union employees must know COBOL ho write loan applications must know dit union, but she does, not know Excel. > not know COBOL. Therefore, Anita and Mohan doesn't work for the credit

ic closures with suitable example. Let ition such that

mg Warshall Algorithm.

5

4

Q- 3(a) (b)

LetS = {x :xe R andx * 0, x * -1}. Consider G = {f_l,f_2i /_3> A./s, /$} where /j (x) = x, /₂ (x) = 1 - x, /₃(x) = l/x, /₄(*) = 1/(1-*). /₅(x) = 1 -1 /(l-x), /(x)-x/(x-l) are functions from S to S. Prove that (S,o) is a group where o is the composition of function.

Prove that intersection of any subgroups of a group is again a subgroup but their union in general, is not a subgroup.

5

4

Q. 4(a)

Let (tf ,*) be a subgroup of a group (G,*) . Show that the relation

2.5

R = {(*, >):*. y e G. .v¹ *>- e // } is an equivalence relation on II.

Using generating function method, find the explicit formula for Fibonacci sequence.

(c)

Q- 5(a)

(b)

(c)

Solve the following recurrence relation by the method of characteristic roots. a_r ~ 6 a+%a,._₂ =f-4^r where a_Q =8, and a, =22.

For X - {0. l}, let A = X xX . Define relation R on A by (7. A)i?(c. d) if

(i) a<c; or (ii)a = c and b<d . Prove that R is a partial order on/i. Determine all minimal and maximal elements of this partial order.

Let /: R x R > Z be the closed binary operation defined by

f(a,b) = \a + b\. Is / associative? .Is / commutative? .Does / have an identity element? Justify your answer.

Let (L, <) be a lattice in which * and denote the operations of meet and join respectively. Prove that a<b<z>a*b = a o a b = b.__

Let a and b be elements of a Boolean Algebra. Prove that (avb) = a 6\

Q. 6(a) (b)

Express the output Z as a Boolean expression of the logic circuit given below for which a, b, c, are inputs and simplify the Boolean expression algebraically to find DNF.

G *' I .V > 2

Suppose G is a non-directed graph with 12 edges. If G has 6 vertices each of degree 3 and the rest have degree less than 3. What is the minimum number of degree of vertices G can have?

Write down the adjacency matrix of the following graph and find the indegree and out-degree of each vertex using the adjacency matrix.