UGC Net Computer Science Paper II Dec 13 Page 4 Solved
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
Answer C
Explanation :-
Dual of a Boolean expression
The duality principle ensures that "if we exchange every symbol by its dual in a formula, we get the dual result".
(a) 0 . 1 = 0: is a true statement asserting that "false and true evaluates to false"
(b) 1 + 0 = 1: is the dual of (a): it is a true statement asserting that "true or false evaluates true."
(c) 1 . 1 = 1: it is a true statement asserting that "true and true evaluates to true".
(d) 0 + 0 = 0: (d) is the dual of (c): it is a true statement asserting, correctly, that "false or false
More example
F1 = x'yz' + x' y' z
The dual of F1 is : ( x' + y + z' ) ( x' + y' + z )
Complement each literal : F1' = ( x + y' + z ) ( x + y + z' )
F2 = x ( y' z' + yz )
The dual of F2 is x + ( y' + z' ) ( y + z )
Complement each literal: F2' = x' + ( y + z ) ( y' + z' )
Product of Sums (POS)
A boolean expression consisting purely of Maxterms (sum terms) is said to be in canonical product of sums form.
Example
Lets say, we have a boolean function F defined on two variables A and B. So, A and B are the inputs for F and lets say, output of F is true i.e., F = 1 when only one of the input is true or 1.
Lets say, we have a boolean function F defined on two variables A and B. So, A and B are the inputs for F and lets say, output of F is true i.e., F = 1 when only one of the input is true or 1.
now we draw the truth table for F
Now we will create a column for the maxterm using the variables A and B. If input is 1 we take the complement of the variable and if input is 0 we take the variable as is.
To get the desired canonical POS expression we will multiply the maxterms (sum terms) for which the output is 0.
F = (A+B) . (A’+B’)
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
Answer D
33. The sum of products expansion for the function F(x, y, z) = (x + y)–z is given as
(A) –x –yz + xy–z + –x y–z
(B) xyz + xy–z + x–y –z
(C) x–y –z + –x –y –z + xy–z
(D) x y–z + x–y –z + –x y–z
Answer D
Explanation :-
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
Explanation :-
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
Answer C
Explanation :-
∀m ∀n P(m, n) says that every number divides every other number and result should be a postive integer.
Clearly it is a false proposition.
Eg: if m=10 n=3 10 divides 3 does not follow the proposition
a is false
∀n P(1, n) says that any positive integer is divisible by 1 and result will be a +ve integer.
That is correct
b is true
∃m∀nP(m,n) says that there are some +ve integers which divides any other +ve integer.
The proposition is correct
example: 1
c is true
Clearly it is a false proposition.
Eg: if m=10 n=3 10 divides 3 does not follow the proposition
a is false
∀n P(1, n) says that any positive integer is divisible by 1 and result will be a +ve integer.
That is correct
b is true
∃m∀nP(m,n) says that there are some +ve integers which divides any other +ve integer.
The proposition is correct
example: 1
c is true
35. Big – O estimate for f(x) = (x + 1) log(x2 + 1) + 3x2 is given as
(A) O(x log x)
(B) O(x2)
(C) O(x3)
(D) O(x2 log x)
Answer B
Explanation :-
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
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) n^t
Answer B
Explanation :-
In each tree we have k-1 edges for k vertices. So, for t trees with total n vertices (all trees are disconnected in a forest) we would have n-t edges.
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
Answer A
Explanation :-
fog(x)=f(g(x))=f(3x+2)=2(3x+2)+3=6x+7
gof(x)=g(f(x))=g(2x+3)=3(2x+3)+2=6x+11
gof(x)=g(f(x))=g(2x+3)=3(2x+3)+2=6x+11
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)
Answer A
39. A graph is non-planar if and only if it contains a subgraph homomorphic to
(A) K3, 2 or K5
(B) K3, 3 and K6
(C) K3, 3 or K5
(D) K2, 3 and K5
Answer C
Explanation :-
Kuratowski's theorem is a mathematical forbidden graph characterization of planar graphs, named after Kazimierz Kuratowski. It states that a finite graph is planar if and only if it does not contain a subgraph that is a subdivision of K5 (the complete graph on five vertices) or of K3,3 (complete bipartite graph on six vertices, three of which connect to each of the other three, also known as the utility graph).
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
Answer D
Explanation :-
No comments:
Post a Comment