**DLD |Gate-2007| Digital Logic Design**

- What is the maximum number of different Boolean functions involving n Boolean variables?
**[GATE – 2007]**

a. n^{2}

b. 2^{n}

c. 2^{2n}

d. 2^{n2}

*Answer : c)*

- How many 3-to-8 line decoders with an enable input are needed to construct a 6-to-64 line decoder without using any other logic gates?
**[GATE – 2007]**

a. 7

b. 8

c. 9

d. 10

*Answer : c)*

- Consider the following Boolean function of four variables: f(w,x,y,z) = ∑(1,3,4,6,9,11,12,14) The function is:
**[GATE – 2007]**

a. independent of one variable.

b. independent of two variables.

c. independent of three variables.

d. dependent on all the variables.

*Answer : b)*

- Let f(w, x, y, z) = ∑(0, 4, 5, 7, 8, 9, 13, 15). Which of the following expressions are NOT equivalent to f?
**[GATE – 2007]**

P. x’y’z’ + w’xy’ + wy’z + xz

Q. w’y’z’ + wx’y’ + xz

R. w’y’z’ + wx’y’ + xyz + xy’z

S. x’y’z’ + wx’y’ + w’y

a. P only

b. Q and S

c. R and S

d. S only

*Answer : d)*

5. Define the connective * for the Boolean variables X and Y as: X * Y = XY + X’ Y’. Let Z = X * Y.

Consider the following expressions P, Q and R.

P: X = Y⋆Z

Q: Y = X⋆Z

R: X⋆Y⋆Z=1

Which of the following is TRUE? **[GATE – 2007]**

a. Only P and Q are valid.

b. Only Q and R are valid.

c. All P, Q, R are valid.

d. Only P and R are valid.

*Answer : c)*

6. Suppose only one multiplexer and one inverter are allowed to be used to implement any Boolean function of n variables. What is the minimum size of the multiplexer needed? **[GATE – 2007]**

a. 2^{n} line to 1 line

b. 2^{n-1} line to 1 line

c. 2^{n+1} line to 1 line

d. 2^{n-2} line to 1 line

*Answer : b)*

7. In a look-ahead carry generator, the carry generate function G_{i} and the carry propagate function P_{i} for inputs A_{i} and B_{i} are given by:

P_{i} = A_{i} ⨁ B_{i} and G_{i} = A_{i}B_{i}

The expressions for the sum bit S_{i} and the carry bit C_{i+1} of the look-ahead carry adder are given by:

S_{i} = P_{i} ⨁ C_{i} and C_{i+1} = G_{i} + P_{i}C_{i} , where C_{0} is the input carry.

Consider a two-level logic implementation of the look-ahead carry generator. Assume that all P_{i} and G_{i} are available for the carry generator circuit and that the AND and OR gates can have any number of inputs. The number of AND gates and OR gates needed to implement the look-ahead carry generator for a 4-bit adder with S3, S2, S1, S0 and C4 as its outputs are respectively: **[GATE – 2007]**

a. 6, 3

b. 10, 4

c. 6, 4

d. 10, 5

*Answer : b)*

8. Which of the following is TRUE about formulae in Conjunctive Normal Form? **[GATE – 2007]**

a. For any formula, there is a truth assignment for which at least half the clauses evaluate to true.

b. For any formula, there is a truth assignment for which all the clauses evaluate to true.

c. There is a formula such that for each truth assignment, at most one-fourth of the clauses evaluate to true

d. None of the above

*Answer : a)*

9. Which of the following input sequences for a cross-coupled R-S flip-flop realized with two NAND gates may lead to an oscillation? **[GATE – 2007]**

a. 11, 00

b. 01, 10

c. 10, 01

d. 00, 11

*Answer : d)*

10. The following expression was to be realized using 2-input AND and OR gates. However, during the fabrication all 2-input AND gates were mistakenly substituted by 2-input NAND gates. (a.b).c + (a’.c).d + (b.c).d + a. d What is the function finally realized ? **[GATE – 2007]**

a. 1

b. a’ + b’ + c’ + d’

c. a’ + b + c’ + d’

d. a’ + b’ + c + d’

*Answer : c)*

11. (C012.25)_{H} – (10111001110.101)_{B} = :** [GATE – 2007]**

a. (135103.412)_{O}

b. (564411.412)_{O}

c. (564411.205)_{O}

d. (135103.205)_{O}

*Answer :a)*

12. The line T in the following figure is permanently connected to the ground.

Which of the following inputs (X1 X2 X3 X4) will detect the fault ?

(The line T in the following figure is permanently connected to the ground) **[GATE – 2007]**

a. 0000

b. 0111

c. 1111

d. None of the above

*Answer : d)*

DLD |Gate-2007|

13. Consider the following expression ad’ + (ac)’ + bc’d Which of the following expressions does not correspond to the Karnaugh Map obtained for the above expression?? **[GATE – 2007]**

a. c’d’+ ad’ + abc’ + (ac)’d

b. (ac)’ + c’d’ + ad’ + abc’d

c. (ac)’ + ad’ + abc’ + c’d

d. b’c’d’ + acd’ + (ac)’ + abc’

*Answer : a)*

DLD |Gate-2007|