Uttar Pradesh Technical University (UPTU) 2006 B.Tech Computer Science Information Technology GATE - Question Paper

(D) F must have 2 identical rows
24. integers S, and ,r(S) is the set of integers found by applying permutation rto every
element of S?
(A) (n-AUBAHB
(B) (A2 +B2)n2
(C) n!
(D) A fl B2/[A U B
25. Let S = {1,2,3 ,m},m>3. Let X1 X be subsets of S every of size 3.
describe a function ffrom Sto the set of natural numbers as, f(i)is the number of sets Xthat

contain the element I. That is f (I)={jIE x7[.
Then f(i)is:
(A) 3m
(B) 3n
(C) 2m+1
(D) 2n+1
26. Which 1 of the 1st order predicate calculus statements provided beneath correctly expresses
the subsequent English statement?
Tigers and lions attack if they are hungry or threatened.
(A) vx[(tiger(x) A lion(x)) — {(hungry(x) v threatened(x)) — attacks(x))1
(B) Vx [(tiger (x) v lion (x)) — {(hungry (x) v threatened (x)) A attacks (x)j
(C) Vx[(tiger(x) v lion(x)) — {attacks(x) — (hungry(x) v threatened(x)))1
(D) vx[(tiger(x) v lion(x)) — {(hungry(x) v threatened(x)) — attacks(x))1
27. Consider the subsequent propositional statements:
Pl:((AAB)C))((AC)A(BC))
P2:((AvB)C))((A—C)v(B_C))
Which 1 of the subsequent is true?
(A) P1 is a tautology, but not P2
(B) P2 is a tautology, but not P1
(C) P1 and P2 are both tautologies
(D) Both P1 and P2 are not tautologies
28. A logical binary relation a, is described as follows:
Let be the unary negation (NOT) operator, with higher precedence then o. Which 1 of the
subsequent is equivalent to A A B?
(A) (‘-‘.‘AOB)
(B) -‘.‘(AO’-..’B)
(C) “.‘(“.‘Ao”.’B)
(D) AOB)
29. If s is a string over (0 + 1)* then let n0 (s) denote the number of 0’s in
s and n1 (s)the number of l’s in s. Which 1 of the subsequent languages is not
regular?
(A) L = {s (0 + 1)*n0 (s) is a 3-digit prime
(B) L = {s E (0 + 1)* for every prefix s’ of s, fl0 (s’) — n1 (s’) 2}
(C) L={sE(0+1)*n0(s)_n1(s)4}
(D) L = {s E (0 + 1) j n0 (s) mod seven = n1 (s) mod five = 0)
30. For SE (0+1)*let d(s)denote the decimal value of s(e.g.d(101)= 5). Let L = {s E (0 + 1) j

Earning:   Approval pending.