Download JNTUH MCA 1st Sem R15 2020 November 821AA Mathematical Foundations of Computer Science Question Paper

FirstRanker.com

Firstranker's choice

Code No: 821AA R15

--- Content provided by FirstRanker.com ---

JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY HYDERABAD

--- Content provided by FirstRanker.com ---

MCA I Semester Examinations, October/ November - 2020

MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE

Time: 2 Hours Max.Marks:75

Answer any five questions

All questions carry equal marks

--- Content provided by FirstRanker.com ---

1. a) Give the formal definition of a well-formed formula in predicate calculus with examples of formulae that are well-formed and not-well-formed.
   b) Show that B is tautologically implied by (—(Av B)—>C)A—AA—C using automatic theorem proving. [7+8]
2. a) Show that (av —b) A(—aVv—cvb)A(av—a)is not a tautology.
   b) Find a CNF for(p —»7) <> (—r —>—p). [7+8]
3. a) Let R be the following equivalence relation on the set A = {1,2,3,4,5,6} .
   

   --- Content provided by FirstRanker.com ---

   R={(1,1),(1,5),(2,2),(2,3),(2,6),(3,2),(3,3),(3,6),(4,4),(5,1),(5,5),(6,2),(6,3),(6,6) }
   Find the partition of A induced by R .
   b) Define the following properties of binary relations with examples.
   I) Reflexive
   II) Symmetric
   

   --- Content provided by FirstRanker.com ---

   III) Anti symmetric
   IV) Transitive. [7+8]
4. a) Find all group homomorphisms.from Z,into Z,.
   b) Define the following terms with examples:
   I) Semigroup
   

   --- Content provided by FirstRanker.com ---

   II) Monoid
   III) Group
   IV) Abelian group. [7+8]
5. a) Using the digits 1,2,3 and 5, how many 4 digit numbers can be formed if
   I) The first digit must be 1 and repetition of the digits is allowed?
   

   --- Content provided by FirstRanker.com ---

   II) The first digit must be 1 and repetition of the digits is not allowed?
   III) The number must be divisible by 2 and repetition is allowed?
   IV) The number must be divisible by 2 and repetition is not allowed?
   b) How many different arrangements of the word ELLIPSE are possible if
   I) There are no restrictions?
   

   --- Content provided by FirstRanker.com ---

   II) The arrangement starts with S?
   III) Both L’s are together?
   The letters are in alphabetical order? [7+8]
6. a) Determine the values of n and r in the following expressions.
   I) ⁿC_r =3xⁿC_r-1
   

   --- Content provided by FirstRanker.com ---

   b) Obtain the coefficient of x⁴y⁵z⁶in (2x² +y—2z³)¹⁷ using multinomial theorem. [7+8]
7. a) Use generating functions to solve the following recurrence relation:
   a_n=5a_n-1 —6a_n-2 for n≥2, a₀=0 and a₁ =3. [15]
8. a) Determine whether the graphs shown in the following figure are isomorphic.
   
   

   --- Content provided by FirstRanker.com ---

   
   
   
   
   
   

   --- Content provided by FirstRanker.com ---

   
   
   
   a b 5 1
   € f‘ - X
   

   --- Content provided by FirstRanker.com ---

   d c v u
   Find the chromatic number of the given graph. [7+8]
   b c
   a d
   f e

--- Content provided by FirstRanker.com ---

---00000---