## 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*

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

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.

__Answer B__

__Explanation :-__
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 :-__