Andhra University 2006 B.E Information Technology COMPUTER SCIENCE

(c) P(x) = False for all X Î S such that b £ x and x ¹ c

(d) P(x) = False for all X Î S such that a £ and b £ x



32. Which of the subsequent is a valid 1st order formula? (Here a and b are 1st order formulae with x as their only free variable)

(a) (( " x) [ a ] Þ ( " x)[ b ]) Þ ( " x) [ a Þ b ]

(b) ( " x) [ a ] Þ ( $ x) [ a Ù b ]

(c) (( " x) [ a v b ] Þ ( $ x)[ a ]) Þ ( " x) [ a ]

(d) ( " x) [ a Þ b ] Þ (( " x)[ a ] Þ ( " x) [ b ])



33. Consider the subsequent formula a and its 2 interpretations I one and I two

a: ( " x) [P x Û ( " y) [Q xy Û Ø Q yy]] ==> ( " x) [ Ø P x]

I 1: Domain: the set of natural numbers

P x == 'x is a prime number

Q xy == 'y divides x'

I 2: identical as I two other than that Px = 'x is a composite number'.

Which of the subsequent statements is true?

(a) I one satisfies a , I two does not

(b) I two satisfies a , I one does not

(c) Neither I one nor I2 satisfies a

(d) Both I one and I two satisfy a



34. m identical balls are to be placed in n distinct bags. You are provided that m ³ kn, where k is a natural number ³ 1. In how many ways can the balls be placed in the bags if every bag must contain at lowest k balls?

(a)

(b)

(c)

(d)



35. Consider the subsequent recurrence relation

T(1) = one

T(n + 1) = T(n) + for all n ³ one

The value of T(m 2) for m ³ one is

(a)

(b)

(c)

(d)



36. How many perfect matchings are there in a complete graph of six vertices?
15
24
30
60



37. Let f: A ® B be an injective (one-to-one) function. describe g: two A ® two B as:

g(C) = (f(x) \x Î C}, for all subsets C of A.

describe h: two B ® two A as: h(D) = { x\x Î A, f(x) Î D}, for all subsets D of B.

Which of the subsequent statements is always true?

Earning:   Approval pending.