BSc IT Sem III 2016 2017 2017 LDMS =3 Question Paper - Mumbai University | munotes

Questions asked in this paper

1. Q1 Solve the following (any two) 10 marks
   • a) Define Mathematical Induction, Prove by method of induction Use (i)p(k) to show that (ii)Is p(n)truevn
   • b) State and prove Inclusion and Exclusion principle and find how many number are not divisible by 2,3 and 5, If p and q are true and r is false then prove the following truth values. How many number are not divisible by 2,5 and 9,
   • d) If A, B, c are subset of U then prove thatA x (BU C)S(AxB)U(AxC)also give set Solve the following (any two) (10)
   • a) Let R be the relation defined on Z such that xRy iff is divisible by for that R is equivalent relation
   • b) If (A <) and (B <)are poset then (A x B, <) is a poset with partial order < defined by (a, A relation R is defined on Draw diagraph of diagraph of Mp , MZ ,Indegree,Outdegree and draw Let L be the lattice then prove that
2. Q3 Solve the following (any two) 10 marks
   • a) Define i) Bijective function function and find fog and gof if Check given function is bijective or not if f(x) also find inverse of it If function f: A B is an invertible then prove that it is bijective
   • d) State and prove Pigeon hole Principal with suitable example. Also state Extended Pigeon p.T.O hole principal with example
3. Q4 Solve the following (any two) Define i) Graph ii) Minimal Spanning tree and check Eulerian and Hamiltonian path, graph and Circuit. the following digraph Satisfy
   • b) Define graph. Check following graphs are isomorphic,
   • i) ul ii) Construct tree and find value of tree. Also find pre-order, post order, Inorder and Left D Prove that the number of veticese: of an odd degree group is even and draw all possible spanning tree.of given graph. Solve the following (any two)
   • a) Show that G = 3,17 } with respect to multiplication modulo eighteen is group
   • c)i) Prove that G= {1,-1,i,-i} is group under ti) (2, *) is semi group for n=5 also show monoid for
   • d)i) Let Z be a set of all even integers then show that semigroup (z +) and (T +) are
   • ii) Show that isnot group
4. Q6 Solve the (any 10 marks
   • a) Find the solution of Recurrnce Relation by using genratring function if 7@n-1 + 4 solution of Recurrnce Relation = — = 3,41 = Find the of Recurrence Relation if dn = — + = 1,41 = 32
   • d) Define Explicit formula and Implicit formula and Check {an} is solution of Recurrence
5. Q7 Solve the following (any
   • a) Let R be relation on set of real number s.t. xRy iff x & y are real number differ by than one i.e. [x — yl < 1. Show that R is equivalence relation.
   • b) Prove that addition is an abalian group Let C,h:C find (fog)oh)(—2), (fof of 9) if f(a) =x? + 2;-g(b) = 5x,h(c) = 9x +5 and define composite function
   • d) Define L.H.R:R and find term Of RR if = + + = = Apply the prims and Kruskal Algorithm. Find minimum weight of given diagram Aand B are two sets then verify following
   • i) Associative law Distributive with the help of Truth

Read from the scan above, so a character or two may differ. The scan is the original.