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

Download JNTUH (Jawaharlal nehru technological university) MCA (Master of Computer Applications) 1st Sem (First Semester) Regulation-R13 2020 November 811AA Mathematical Foundations Of Computer Science Previous Question Paper


S OCT 2020

R13

Code No: 811AA















JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY HYDERABAD

MCA I Semester Examinations, October/ November - 2020

MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE


Time: 2 Hours













Max.Marks:60

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 ((A )

B C) AC using automatic

theorem proving.

















[6+6]



2.a)

Show that (a )

b (a c )

b (a )

a is not a tautology.

used

b)

Find a CNF for ( p r) (r )

p .











[6+6]









3.a)

Let R be the following equivalence relation on the set A

}

6

,

5

,

4

,

3

,

2

,

1

{

.

R

),

1

,

1

{(

),

5

,

1

(

),

2

,

2

(

),

3

,

2

(

),

6

,

2

(

),

2

,

3

(

),

3

,

3

(

),

6

,

3

(

),

4

,

4

(

),

1

,

5

(

),

5

,

5

(

),

2

,

6

(

),

3

,

6

(

)}

6

,

6

(

.

Find the partition of A induced by R .



b) Define the following properties of binary relations with examples.

i) Reflexive
ii) Symmetric
iii) Anti symmetric
iv) Transitive.

















[6+6]



4.a)

Find all group homomorphisms from Z into Z .

4

10

b)

Define the following terms with examples:
i) Semigroup
ii) Monoid
iii) Group
iv) Abelian group.

















[6+6]









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?



b)

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?
The letters are in alphabetical order?











[6+6]
S OCT 2020






6.a)

Determine the values of

n and

r in the following expressions.

i) nP 56

2

ii) 11C 311C

r

r 1

b) Obtain the coefficient of 99 60 14

x y z in

3

2 100

(2x y z ) using multinomial theorem. [6+6]









7.

Use generating functions to solve the following recurrence relation:

a 5a

6a for n

2 , a 0 and a 3.









[12]

n

n 1

n2

0

1











8.a)

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

used



b) Find the chromatic number of the given graph.









[6+6]











---oo0oo---





This post was last modified on 16 March 2023