Chapter 2 • Digital Logic 77

(a) P only (b) Q and S The counter is connected as follows:

(c) R and S (d) S only
A4 A3 A2 A1
(GATE 2007: 2 Marks)
54. 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 Count = 1
Which of the following is TRUE? Clear 4-bit counter Load = 0
(a) Only P and Q are valid.
Clock
(b) Only Q and R are valid.
(c) Only P and R are valid.
(d) All P, Q, R are valid. Inputs
(GATE 2007: 2 Marks)
55. Suppose only one multiplexer and one inverter are
allowed to be used to implement any Boolean function 0 0 1 1
of n variables. What is the minimum size of the multi- Assume that the counter and gate delays are negligible.
plexer needed? If the counter starts at 0, then it cycles through the fol-
(a) 2n line to 1 line (b) 2n + 1 line to 1 line lowing sequence:
(c) 2n − 1 line to 1 line (d) 2n − 2 line to 1 line (a) 0, 3, 4 (b) 0, 3, 4, 5
(GATE 2007: 2 Marks) (c) 0, 1, 2, 3, 4 (d) 0, 1, 2, 3, 4, 5
56. In a look-ahead carry generator, the carry generate func- (GATE 2007: 2 Marks)
tion Gi and the carry propagate function Pi for inputs Ai
and Bi are given by 58. In the Karnaugh map shown below, × denotes a don’t
care term. What is the minimal form of the function rep-
Pi = Ai ⊕ Bi and Gi = AiBi resented by the Karnaugh map?
The expressions for the sum bit Si and the carry bit Ci + 1
of the look-ahead carry adder are given by ab 00 01 11 10
Si = Pi ⊕ Ci and Ci + 1 = Gi + PiCi, where C0 is the input cd
carry. 00 1 1 1
Consider a two-level logic implementation of the look- 01 ×
ahead carry generator. Assume that all Pi and Gi are avail-
able for the carry generator circuit and that the AND and 11 ×
OR gates can have any number of inputs. The number of 10 1 1 ×
AND gates and OR gates needed to implement the look-
ahead carry generator for a 4-bit adder with S3, S2S1, S0, (a) b ⋅d + a ⋅d (b) a ⋅ b + b ⋅ d + ab ⋅ d
and C4 as its outputs are, respectively,
(c) b ⋅d + a ⋅b⋅d (d) a ⋅b + b ⋅d + a ⋅d
(a) 6, 3 (b) 10, 4
(c) 6, 4 (d) 10, 5 (GATE 2008: 1 Mark)
(GATE 2007: 2 Marks) 59. In the IEEE floating-point representation, the hexadeci-
mal value 0x00000000 corresponds to
57. The control signal functions of a 4-bit binary counter are
given below (where × is “don’t care”): (a) The normalized value 2−127
(b) The normalized value 2−126
Clear Clock Load Count Function
(c) The normalized value +0
1 × × × Clear to 0 (d) The special value +0
0 × 0 0 No change (GATE 2008: 1 Mark)
0 1 × Load input 60. Let r denote number system radix. The only value(s) of
0 0 1 Count next r that satisfy the equation 121r = 11r is/are

Ch wise GATE_CSIT_CH02_Digital Logic.indd 77 11/13/2018 9:43:11 AM

 78 GATE CS AND IT Chapter-wise Solved Papers

(a) Decimal 10 (b) Decimal 11 Which one of the following is equivalent to P ∨ Q?

(c) Decimal 10 and 11 (d) Any value > 2 (a) ¬Q ¬P (b) P ¬Q
(GATE 2008: 1 Mark) (c) ¬P Q (d) ¬P ¬Q
61. Given f1, f3 and f in canonical sum of products form (in (GATE 2009: 1 Mark)
decimal) for the circuit 66. How many 32 K × 1 RAM chips are needed to provide a
memory capacity of 256 K-bytes?
f1
(a) 8 (b) 32
f2 f
(c) 64 (d) 128
(GATE 2009: 1 Mark)
f3
f1 = ∑m(4, 5, 6, 7, 8) 67. The minterm expansion of f ( P , Q, R) = PQ + QR + PR
f3 = ∑m(1, 6, 15) is
f = ∑m(1, 6, 8, 15) (a) m2 + m4 + m6 + m7
then f2 is (b) m0 + m1 + m3 + m5
(a) ∑m(4, 6) (b) ∑m(4, 8) (c) m0 + m1 + m6 + m7
(c) ∑m(6, 8) (d) ∑m(4, 6, 8) (d) m2 + m3 + m4 + m5
(GATE 2008: 1 Mark) (GATE 2010: 1 Mark)

62. If P, Q, R are Boolean variables, then 68. P is a 16-bit signed integer. The 2’s complement rep-
resentation of P is (F87B)16. The 2’s complement rep-
( P + Q )( P ⋅ Q + P ⋅ R)( P ⋅ R + Q )
resentation of 8 × P is
simplifies to (a) (C3D8)16 (b) (187B)16
(a) P ⋅Q (b) P⋅R (c) (F878)16 (d) (987B)16
(c) P ⋅Q + R (d) P⋅R +Q (GATE 2010: 1 Mark)
(GATE 2008: 2 Marks) 69. The Boolean expression for the output f of the multi-
plexer shown below is
63. (1217)8 is equivalent to
(a) (1217)16 (b) (028F)16
(c) (2297)10 (d) (0B17)16
R
(GATE 2009: 1 Mark)
R
64. What is the minimum number of gates required to f
implement the Boolean function (AB + C ) if we have to R
use only 2-input NOR gates? R
(a) 2 (b) 3
(c) 4 (d) 5
(GATE 2009: 1 Mark)
P Q
65. The binary operation is defined as follows
(a) P⊕Q⊕R (b) P⊕Q⊕R
P Q P Q
T T T (c) P⊕Q⊕R (d) P + Q + R
T F T (GATE 2010: 1 Mark)
F T F
70. What is the Boolean expression for the output f of the
F F T combinational logic circuit of NOR gates given below?

Ch wise GATE_CSIT_CH02_Digital Logic.indd 78 11/13/2018 9:43:13 AM