First Question of compulsory.

Answer any FOUR from the remaining questions.

All questions carry wqual marks.

 Answer All Parts of any questionj at one place.

1. (a) Let A and B be sets. Show that

(i)                  (AB)A

(ii)                A(AB).

(b) Use mathematical induction to prove that n3-n is divisible by 3 whenever nis a positive integer.

(c) What is the coefficient of x’2y’3 in the expansion of (x+y)25?

(d)  Define Non-Homogeneous recurrence relation.

(e)  State Four color theorem.

(f) Prove that is G is a tree, then the sum of degrees equals |v|-2.

(g) Show that a vertex v is a tree T if a cut vertex of T iff deg(v)>1.

2. (a)  Construct the truth table for

[(pvq)^(~r)]-><-(q->r)

(b) Verify that the following argument is valid by translating into symbols and using truth tables to check for tautologies.

If Joe is a mathematician, then he is ambitious.

If Joe is an early riser, the he does not like out meal

If Joe is ambitiors, thenhe is an early riser.

Hence, if Joe is a mathematician, then he does not like out meal.

3.(a)   Prove that the function b(n)=2(3n)-5 is the unique function defined by

(i)                  B(0)=-3, b(1)=1 and

(ii)                B(n)=4b(n-1) -3b(n-2) for n>=2.

(b) Solve the recurrence relation

an-7an-1+10an-2=0 for n>=2.

4.(a) Let R1 and R2 be two equibvalence relations on asset A. Show that R1 R2 is an equivalence relations on a set A but that R1R2 beed not be an equivalence relation.

(b) If Ris a symmetric relation defined on a set A, then prove that RR2 is symmetric.

5.(a)  Let Rbe a relation on A=(a,b,c,d) whose adjacency martix is given              Computes the adjacency matrix of R+ using Warshall’s Algorithm.

(b) Draw a digraph with 5 verteces that has 4 strongly connected components, 2 weekly connected components and 3 unilaterally connected componints oxactly.

6. (a) Prove that a simple non-directed graph Gis a tree iff G is connected and contains no cycles.

(b)  Draw all regular binary trees:

(i) With exactly  7 vertices.

(ii) with exactly 9 vertices.

7.Show that every subsystem of Boolean algebra is a Boolean Algebra.

8.Write short notes on the following:

(a)    Language and grammar.

(b)   Finite State machine.

(c)    Turning machine.

tejus mahiIT 2.1 Previous PapersCSE,CSE Previous Papers,Discrete Mathematical Structures-I Previous Papers,IT,IT Previous Papers
First Question of compulsory. Answer any FOUR from the remaining questions. All questions carry wqual marks.  Answer All Parts of any questionj at one place. 1. (a) Let A and B be sets. Show that (i)                  (AB)A (ii)                A(AB). (b) Use mathematical induction to prove that n3-n is divisible by 3 whenever nis a positive integer. (c)...