31. The dual of a Boolean expression is obtained by interchanging
(A) Boolean sums and Boolean products
(B) Boolean sums and Boolean products or interchanging 0's and 1's
(C) Boolean sums and Boolean products and interchanging 0's & 1's
(D) Interchanging 0's and 1's
32. Given that (292)10 = (1204)x in some number system x. The base x of that number system is
(A) 2 (B) 8
(C) 10 (D) None of the above
So here, x=6
33. The sum of products expansion for the function
F(x, y, z) = (x + y)z’ is given as
(A) x’y’z + xyz’ + x’yz’
(B) xyz + xyz’ + xy’z’
(C) xy’z’ + x’y’z’ + xyz’
(D) xyz’ + xy’z’ + x’yz’
Use Boolean identities to expand the product and simplify.
F(x, y, z)=(x + y)z’
=xz’+yz’ Distributive law
=x1z’+1yz’ Identity law
=x(y+y’)z’+(x+x’)yz’ Unit property
=xyz’+xy’z’+xyz’+x’yz’ Distributive law
=xyz’+xy’z’+x’yz’ Idempotent law
34. Let P(m, n) be the statement
"m divides n" where the universe of discourse for both the variables is the set of positive integers. Determine the truth values of each of the following propositions:
I. ∀m ∀n P(m,n),
II. ∃m ∀n P(m, n)
(A) Both I and II are true
(B) Both I and II are false
(C) I - false & II - true
(D) I - true & II – false
35. Big - O estimate for
f(x) = (x + 1) log(x2 + 1) + 3x2 is given as
(A) O(xlogx) (B) O(x2)
(C) O(x3) (D) O(x2logx)
Big-O notation of f(x)=(x+1) log(x2+1) + 3x2
Note (x+1) is O(x) and x2+1≤2x2 when x>1
So, log x2+1≤log(2x2)=log 2+ log x2=log 2+ 2 log x
≤ 3 log x if x >2
Thus, log x2+1 is O(log x)
The first part of f(x) is O(x log x)
Also, 3x2 is O(x2)
So, f(x) is O(max(x log x, x2))=O(x2) as x log x ≤ x2 for x >1
36. How many edges are there in a forest of t-trees containing a total of n vertices ?
(A) n+t (B) n-t
(C) n*t (D) nt
37. Let f and g be the functions from the set of integers to the set integers defined by
f(x) = 2x + 3 and g(x) = 3x + 2
Then the composition of f and g and g and f is given as
(A) 6x + 7, 6x + 11
(B) 6x + 11, 6x + 7
(C) 5x + 5, 5x + 5
(D) None of the above
38. If n and r are non-negative integers and n≥r, then p(n + 1, r) equals to
(A) P(n,r)(n+1) / (n+1-r)
(B) P(n,r)(n+1) / (n-1+r)
(C) p(n,r)(n-1) / (n+1-r)
(D) p(n,r)(n+1) / (n+1+r)
p(n, r) = n!/(n-r)!
p( n+1, r) = (n+1)!/(n+1-r)!
= (n+1) n! /(n+1-r) (n-r)!
= P(n, r)(n+1)/(n+1-r)
39. A graph is non-planar if and only if it contains a subgraph homeomorphic to
(A) K3,2 or K5 (B) K3,3 and K6
(C) K3,3 or K5 (D) K2,3 and K5
Kuratowski’s Theorem: A graph is non-planar if and only if it contains a subgraph that is homeomorphic to either K5 or K3,3.
40. Which of the following statements are true ?
I. A circuit that adds two bits, producing a sum bit and a carry bit is called half adder.
II. A circuit that adds two bits, producing a sum bit and a carry bit is called full adder.
III. A circuit that adds two bits and a carry bit producing a sum bit and a carry bit is called full adder.
IV. A device that accepts the value of a Boolean variable as input and produces its complement is called an inverter.
(A) I & II (B) II & III
(C) I, II, III (D) I, III & IV