Download JNTUH MCA 1st Sem R13 2020 November 811AA Mathematical Foundations Of Computer Science Question Paper

FirstRanker.com

Firstranker's choice

Code No: 811AA R13

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

JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY HYDERABAD

MCA I Semester Examinations, October/ November - 2020

MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE

Time: 2 Hours Max.Marks:60

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

Answer any five questions

All questions carry equal marks

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. [6+6]
2. a) Show that (av —b) A(—av—cvb)A(av—a)is not a tautology.
   

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

   b) Find a CNF for(p —r) <> (—r —>—p). [6+6]
3. a) Let R be the following equivalence relation on the set A = {1,2,3,4,5,6} .
   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.
   

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

   I) Reflexive
   II) Symmetric
   III) Anti symmetric
   IV) Transitive. [6+6]
4. a) Find all group homomorphisms from Z₆ into Z₄.
   

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

   b) Define the following terms with examples:
   I) Semigroup
   II) Monoid
   III) Group
   IV) Abelian group. [6+6]

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

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?
   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?

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

6. a) How many different arrangements of the word ELLIPSE are possible if
   I) There are no restrictions?
   II) The arrangement starts with S?
   III) Both L’s are together?
   IV) The letters are in alphabetical order? [6+6]

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

7. a) Determine the values of n and r in the following expressions.
   I) ⁿC_r =3xⁿC_r-1
   b) Obtain the coefficient of x⁴y⁴z²in (2x² +y—2z²)⁷ using multinomial theorem. [6+6]
8. 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. [12]
   

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

   b) Determine whether the graphs shown in the following figure are isomorphic.
   
   
   
   
   

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

   
   
   
   
   
   

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

   
   Find the chromatic number of the given graph. [6+6]
   

FirstRanker.com

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