GATE Questions & Answers of Digital Logic Computer Science and Information Technology

In 16-bit 2’s complement representation, the decimal number −28 is:

•  (A)  1111 1111 0001 1100
•  (B)  0000 0000 1110 0100
•  (C)  1111 1111 1110 0100
•  (D)  1000 0000 1110 0100

Which one of the following is NOT a valid identity?

•  (A)  $ (\mathrm x\oplus\mathrm y)\oplus\mathrm z=\mathrm x\oplus(\mathrm y\oplus\mathrm z) $
•  (B)  $ (\mathrm x+\mathrm y)\oplus\mathrm z=\mathrm x\oplus(\mathrm y+\mathrm z) $
•  (C)  $ \mathrm x\oplus\mathrm y=\;\mathrm x+\mathrm y,\;\mathrm{if}\;\mathrm{xy}=0 $
•  (D)  $ \mathrm x\oplus\mathrm y=(\mathrm{xy}+\mathrm x'\mathrm y')' $

Consider Z = X – Y, where X, Y and Z are all in sign-magnitude form. X and Y are each represented in n bits. To avoid overflow, the representation of Z would require a minimum of:

•  (A)  $n$ bits
•  (B)  $n$ - 1 bits
•  (C)  $n$ + 1 bits
•  (D)  $n$ + 2 bits

Consider three 4-variable functions f₁, f₂, and f₃, which are expressed in sum-of-minterms as f₁ = $\sum$ (0, 2, 5, 8, 14),   f₂ = $\sum$ (2, 3, 6, 8, 14, 15),   f₃ = $\sum$ (2, 7, 11, 14) For the following circuit with one AND gate and one XOR gate, the output function f can be expressed as:

•  (A)  $\sum$ (7, 8, 11)
•  (B)  $\sum$ (2, 7, 8, 11, 14)
•  (C)  $\sum$ (2, 14)
•  (D)  $\sum$ (0, 2, 3, 5, 6, 7, 8, 11, 14, 15)

What is the minimum number of 2-input NOR gates required to implement a 4-variable function expressed in sum-of-minterms form as f = $\mathrm\Sigma$ (0, 2, 5, 7, 8, 10, 13, 15)? Assume that all the inputs and their complements are available. Answer: _______________.

Let $\style{font-family:'Times New Roman'}\oplus$ and $\style{font-family:'Times New Roman'}\odot$ denote the Exclusive OR and Exclusive NOR operations, respectively.

•  (A)  $\style{font-family:'Times New Roman'}{\overline{P\oplus Q}=P\odot Q}$
•  (B)  $\style{font-family:'Times New Roman'}{\overline P\oplus Q=P\odot Q}$
•  (C)  $\style{font-family:'Times New Roman'}{\overline P\oplus\overline Q=P\odot Q}$
•  (D)  $\style{font-family:'Times New Roman'}{\begin{array}{l}(P\oplus\overline P)\oplus Q=(P\odot\overline P)\odot\overline Q\\\end{array}}$

The number of states in the state transition diagram of this circuit that have a transition back to the same state on some value of “in” is _____.

•  (A) None of (i), (ii), (iii), (iv) can be exactly represented
•  (B) Only (ii) cannot be exactly represented
•  (C) Only (iii) and (iv) cannot be exactly represented
•  (D) Only (i) and (ii) cannot be exactly represented

Consider the minterm list form of a Boolean function F given below.

$\style{font-family:'Times New Roman'}{F\left(P,Q,R,S\right)=\sum m\left(0,2,5,7,9,11\right)+d\left(3,8,10,12,14\right)}$

The n-bit fixed-point representation of an unsigned real number X uses f bits for the fraction part. Let i = n - f. The range of decimal values for X in this representation is

•  (A)  2^-f to 2ⁱ
•  (B)  2^-f to (2ⁱ - 2^-f)
•  (C)  0 to 2ⁱ
•  (D)  0 to (2ⁱ - 2^-f)

Consider the Karnaugh map given below, where X represents "don't care" and blank represents 0.

Assume for all inputs (a, b, c, d), the respective complements  $\style{font-family:'Times New Roman'}{\left(\overline a,\;\overline b,\;\overline c,\;\overline d\right)}$  are also available. The above logic is implemented using 2-input NOR gets only. The minimum number of gates required is _____________.

•  (A)  Q₁Q₀ after the 3^rd cycle are 11 and after the 4^th cycle are 00 respectively
•  (B)  Q₁Q₀ after the 3^rd cycle are 11 and after the 4^th cycle are 01 respectively
•  (C)  Q₁Q₀ after the 3^rd cycle are 00 and after the 4^th cycle are 11 respectively
•  (D)  Q₁Q₀ after the 3^rd cycle are 01 and after the 4^th cycle are 01 respectively

                                                           SET-2

The representation of the value of a 16-bit unsigned integer X in hexadecimal number system is BCA9. The representation of the value of X in octal number system is

•  (A)  571244
•  (B)  736251
•  (C)  571247
•  (D)  136251

Given the following binary number in 32-bit (single precision) IEEE-754 format:

00111110011011010000000000000000

The decimal value closest to this floating-point number is

•  (A)  $\style{font-family:'Times New Roman'}{1.45\times10^1}$
•  (B)  $\style{font-family:'Times New Roman'}{1.45\times10^{-1}}$
•  (C)  $\style{font-family:'Times New Roman'}{2.27\times10^{-1}}$
•  (D)  $\style{font-family:'Times New Roman'}{2.27\times10^1}$

If w, x, y, z are Boolean variables, then which one of the following is INCORRECT ?

•  (A)  $\style{font-family:'Times New Roman'}{wx+w(x+y)+x(x+y)=x+wy}$
•  (B)  $\style{font-family:'Times New Roman'}{\overline{w\overline x(y+\overline z)}+\overline wx=\overline w+x+\overline yz}$
•  (C)  $\style{font-family:'Times New Roman'}{(w\overline x(y+x\overline z)+\overline w\;\overline x)y=x\overline y}$
•  (D)  $\style{font-family:'Times New Roman'}{(w+y)(wxy+wyz)=wxy+wyz}$

Given $\style{font-family:'Times New Roman'}{f(w,\;x,\;y,\;z)=\sum\nolimits_m(0,\;1,\;2,\;3,\;7,\;8,\;10)+\sum\nolimits_d(5,\;6,\;11,\;15)}$ where d represents the don't-care condition in Karnaugh maps. Which of the following is a minimum product-of-sums (POS) form of $ f\left(w,x,y,z\right) $ ?

•  (A)  $\style{font-family:'Times New Roman'}{f=(\overline w+\overline z)(\overline x+z)}$
•  (B)  $\style{font-family:'Times New Roman'}{f=(\overline w+z)(x+z)}$
•  (C)  $\style{font-family:'Times New Roman'}{f=(w+z)(\overline x+z)}$
•  (D)  $\style{font-family:'Times New Roman'}{f=(w+\overline z)(\overline x+z)}$

Consider a binary code that consists of only four valid codewords as given below:

00000,01011,10101,11110

Let the minimum Hamming distance of the code be p and the maximum number of erroneous bits that can be corrected by the code be q. Then the values  of p and q are

•  (A)  p=3 and q=1
•  (B)  p=3 and q=2
•  (C)  p=4 and q=1
•  (D)  p=4 and q=2

The next state table of a 2-bit saturating up-counter is given below.

The counter is built as a synchronous sequential circuit using T flip-flops. The expression for T₁ and T₀ are

•  (A)  $\style{font-family:'Times New Roman'}{T_1=Q_1Q_0\;\;\;T_0={\overline Q}_1{\overline Q}_0}$
•  (B)  $\style{font-family:'Times New Roman'}{T_1={\overline Q}_1Q_0\;\;\;T_0={\overline Q}_1+{\overline Q}_0}$
•  (C)  $\style{font-family:'Times New Roman'}{T_1=Q_1+Q_0\;\;\;T_0={\overline Q}_1+{\overline Q}_0}$
•  (D)  $\style{font-family:'Times New Roman'}{T_1={\overline Q}_1Q_0\;\;\;T_0=Q_1+Q_0}$

Consider the Boolean operator # with the following properties:

$x\#0\;=\;x,\;x\#1\;=\;\overline x,\;x\#x\;=\;0\;and\;x\#\overline x\;=1.$ Then $ x#y $ is equivalent to 

•  (A)  $x\overset-y+\overset-xy$
•  (B)  $x\overset-y+\overset-x\overset-y$
•  (C)  $ \overline xy+xy $
•  (D)  $xy+\overset-x\overset-y$

We want to design a synchronous counter that counts the sequence 0-1-0-2-0-3 and then repeats. The minimum number of J-K flip-flops required to implement this counter is .

Consider the two cascaded 2-to-1 multiplexers as shown in the figure.

The minimal sum of products form of the output $X$ is

•  (A)  $\style{font-family:'Times New Roman'}{\overline P\;\overline Q\;+\;PQR}$
•  (B)  $\style{font-family:'Times New Roman'}{\overline PQ\;+\;QR}$
•  (C)  $\style{font-family:'Times New Roman'}{P\;Q\;+\;\overline P\;\overline Q\;R}$
•  (D)  $\overline{Q} \overline{R} +PQR$

Consider an eight-bit ripple-carry adder for computing the sum of A and B, where A and B are integers represented in 2’s complement form. If the decimal value of A is one, the decimal value of B that leads to the longest latency for the sum to stabilize is ___________ .

Let,x₁ ⊕ x₂ ⊕ x₃ ⊕ x₄ =0 where x₁, x₂, x₃, x₄ are Boolean variables, and ⊕is the XOR operator. Which one of the following must always be TRUE?

•  (A)  $x_1{x}_2{x}_3{x}_4 = 0$
•  (B)  $x_1{x}_3+x_2 = 0$
•  (C)  $\style{font-family:'Times New Roman'}{\overset-{x_1}\oplus\overset-{x_3}=\overset-{x_2}\oplus\overset-{x_4}}$
•  (D)  $x_1+x_2+x_3+x_4 = 0$

Let X be the number of distinct 16-bit integers in 2's complement representation. Let Y be the number of distinct 16-bit integers in sign magnitude representation. Then X-Y is ________.

Consider a 4-bit Johnson counter with an initial value of 0000. The counting sequence of this counter is

•  (A)  0, 1, 3, 7, 15, 14, 12, 8, 0
•  (B)  0, 1, 3, 5, 7, 9, 11, 13, 15, 0
•  (C)  0, 2, 4, 6, 8, 10, 12, 14, 0
•  (D)  0, 8, 12, 14, 15, 7, 3, 1, 0

The binary operator $\ne$ is defined by the following truth table.

Which one of the following is true about the binary operator $\ne$?

•  (A)  Both commutative and associative
•  (B)  Commutative but not associative
•  (C)  Not commutative but associative
•  (D)  Neither commutative nor associative

A positive edge-triggered D flip-flop is connected to a positive edge-triggered JK flip-flop as follows. The Q output of the D flip-flop is connected to both the J and K inputs of the JK flip-flop, while the Q output of the JK flip-flop is connected to the input of the D flip-flop. Initially, the output of the D flip-flop is set to logic one and the output of the JK flip-flop is cleared. Which one of the following is the bit sequence(including the initial state) generated at the Q output of the JK flip-flop when the flip-flops are connected to a free-running common clock? Assume that J = K = 1 is the toggle mode and J = K = 0 is the state-holding mode of the JK flip-flop. Both the flip-flops have non-zero propagation delays.

•  (A)  0110110…..
•  (B)  0100100….
•  (C)  011101110….
•  (D)  011001100…

The minimum number of JK flip-flops required to construct a synchronous counter with the count sequence (0, 0, 1, 1, 2, 2, 3, 3, 0, 0,….) is _______.>

The number of min-term after minimizing the following Boolean expression is _____.

                                                       $ \left[D'\;+\;AB'+A'C+AC'D\;+\;A'C'D'\right] $

A half adder is implemented with XOR and AND gates. A full adder is implemented with two half adders and one OR gate. The propagation delay of an XOR gate is twice that of and AND/OR gate. The propagation delay of an AND/OR gate is 1.2 microseconds. A 4-bit ripple-carry binary adder is implemented by using four full adders. The total propagation time of this 4- bit binary adder in microseconds is _____.

Let # be a binary operator defined as

                 X # Y = X' +Y' where X and Y are Boolean variables.

Consider the following two statements

                S1  (P # Q) # R = P # (Q # R)
                S2   Q # R = R # Q

Which of the following is/are true for hte Boolean variables P, Q and R?

•  (A)  Only S1 is true
•  (B)  Only S2 is true
•  (C)  Both S1 and S2 are true
•  (D)  Neither S1 nor S2 are true

Given the function F = P' + QR, where F is a function in three Boolean variables P, Q and R and P' = !P, consider the following statements.

(S1) F = ${\sum }_{}$ (4, 5, 6)
(S2) F = ${\sum }_{}$ (0, 1, 2, 3, 7)
(S3) F = $\prod$ (4, 5, 6)
(S4) F = $\prod$ (0, 1, 2, 3, 7)

Which of the following is true?

•  (A)  (S1) – False, (S2) – True, (S3) – True, (S4) – False
•  (B)  (S1) –True, (S2) – False, (S3)- False, (S4) – True
•  (C)  (S1) – False, (S2)-False (S3)-True, (S4)-True
•  (D)  (S1)–True, (S2)-True, (S3)-False, (S4)-False

Consider the following Boolean expression for F:

$F\left(P,Q,R,S\right)=PQ+\overline{P}QR+\overline{P}Q\overline{R}S$

The minimal sum-of-products form of F is

•  (A) $PQ+QR+QS$
•  (B) $P+Q+R+S$
•  (C) $\overline{P}+\overline{Q}+\overline{R}+\overline{S}$
•  (D) $\overline{P}R+\overline{P}\overline{R}S+P$

The base (or radix) of the number system such that the following equation holds is____________.

$\frac{312}{20}=13.1$

Consider the 4-to-1 multiplexer with two select lines S₁ and S₀ given below.

The minimal sum-of-products form of the Boolean expression for the output F of the multiplexer is

•  (A) $\overline{P}Q+Q\overline{R}+P\overline{Q}R$
•  (B) $\overline{P}Q+\overline{P}Q\overline{R}+PQ\overline{R}+P\overline{Q}R$
•  (C) $\overline{P}QR+\overline{P}Q\overline{R}+Q\overline{R}+P\overline{Q}R$
•  (D) $PQ\overline{R}$

The dual of a Boolean function F(x₁, x₂, … , x_n, +, · , ′ ), written as F^D, is the same expression as that of F with + and ⋅ swapped. F is said to be self-dual if F = F^D. The number of self-dual functions with n Boolean variables is

•  (A) $2^n$
•  (B) $2^{n-1}$
•  (C) $2^{2^n}$
•  (D) $2^{2^{n-1}}$

Let k= 2ⁿ. A circuit is built by giving the output of an n-bit binary counter as input to an n-to-2ⁿ bit decoder. This circuit is equivalent to a

•  (A) k-bit binary up counter.
•  (B) k-bit binary down counter.
•  (C) k-bit ring counter.
•  (D) k-bit Johnson counter.

Consider the equation (123)₅ = (x8)_y with x and y as unknown. The number of possible solutions is _____ .

Consider the following minterm expression for F:

$F\left(P,Q,R,S\right)=\sum 0,2,5,7,8,10,13,15$

The minterms 2, 7, 8 and 13 are ‘do not care’ terms. The minimal sum-of-products form for F is

•  (A) $Q\overline{S}+\overline{Q}S$
•  (B) $\overline{Q}\overline{S}+QS$
•  (C) $\overline{Q}\overline{S}\overline{R}+\overline{Q}R\overline{S}+Q\overline{R}S+QRS$
•  (D) $\overline{P} \overline{Q } \overline{S}+\overline{P}QS+PQS+P\overline{Q}\overline{S}$

Consider the following combinational function block involving four Boolean variables x, y, a, b where x, a, b are inputs and y is the output.

f (x, y, a, b)
{
     if (x is 1) y = a;
     else y = b;
}

Which one of the following digital logic blocks is the most suitable for implementing this function?

•  (A) Full adder
•  (B) Priority encoder
•  (C) Multiplexor
•  (D) Flip-flop

The above synchronous sequential circuit built using JK flip flop is initialized with Q₂Q₁Q₀=000.THe state sequence for these circuit for next 3 clock cycle is

•  (A) 001,010,011
•  (B) 111,110,101
•  (C) 100,110,111
•  (D) 100,011,001

Let ⊕ denote the Exclusive OR (XOR) operation. Let ‘1’ and ‘0’ denote the binary constants. Consider the following Boolean expression for F over two variables P and Q:

$F\left(P,Q\right)=\left(\left(1\oplus P\right)\oplus \left(P\oplus Q\right)\right)\oplus \left(\left(P\oplus Q\right)\oplus \left(Q\oplus 0\right)\right)$

The equivalent expression for F is

•  (A) $P+Q$
•  (B) $\overline{P+Q}$
•  (C) $P\oplus Q$
•  (D) $\overline{P\oplus Q}$

The smallest integer that can be represented by an 8-bit number in 2’s complement form is

•  (A) -256
•  (B) -128
•  (C) -127
•  (D) 0

In the following truth table, V = 1 if and only if the input is valid.

What function does the truth table represent?

•  (A) Priority encoder
•  (B) Decoder
•  (C) Multiplexer
•  (D) Demultiplexer

Which one of the following expressions does NOT represent exclusive NOR of x and y?

•  (A)  $xy+x^{{}^{\prime }}{y}^{{}^{\prime }}$
•  (B)  $x\oplus <!--\; ?\; -->y^{{}^{\prime }}$
•  (C) $x^{\text{'}}\oplus y$
•  (D)  $x^{{}^{\prime }}\oplus <!--\; ?\; -->y^{{}^{\prime }}$

The truth table

represents the Boolean function

•  (A) X
•  (B) X + Y
•  (C) X $\oplus$ Y
•  (D) Y

The decimal value 0.5 in IEEE single precision floating point representation has

•  (A) fraction bits of 000…000 and exponent value of 0
•  (B) fraction bits of 000…000 and exponent value of −1
•  (C) fraction bits of 100…000 and exponent value of 0
•  (D) no exact representation

What is the minimal form of the Karnaugh map shown below? Assume that X denotes a don’t care term.

•  (A) $\overline{b}\overline{d}$
•  (B) $\overline{b}\overline{d}+\overline{b}\overline{c}$
•  (C) $\overline{b}\overline{d}+a\overline{b}\overline{c}d$
•  (D) $\overline{b}\overline{d}+\overline{b}\overline{c}+\overline{c}\overline{d}$

Which one of the following circuits is NOT equivalent to a 2-input XNOR (exclusive NOR) gate?

•  (A) 
•  (B) 
•  (C) 
•  (D) 

The simplified SOP (Sum of Product) form of the Boolean expression

$\left(P+\overline{Q}+\overline{R}\right).\left(P+\overline{Q}+R\right).\left(P+Q+\overline{R}\right)$ is

•  (A) $\left(\overline{P}.Q+\overline{R}\right)$
•  (B) $\left(P+\overline{Q}.\overline{R}\right)$
•  (C) $\left(\overline{P}.Q+R\right)$
•  (D) $\left(P.Q+R\right)$

Consider the following circuit involving three D-type flip-flop used ina certain type of  counter configuration.

if at some instance prior to the occurance of the clock edge  P ,Q,and R have value 0, 1 and 0 respectively, what shall be the val ue of PQR after the clock edge?

•  (A) 000
•  (B) 001
•  (C) 010
•  (D) 011

Consider the following circuit involving three D-type flip-flop used ina certain type of  counter configuration.

If all the flip-flop were reset to 0 at power on ,what is the total number of distinct outputs (states) represented by PQR generated by the counter?

•  (A) 3
•  (B) 4
•  (C) 5
•  (D) 6

The minterm expansion of $f\left(P,Q,R\right)=PQ+Q\overline{R}+P\overline{R}$ is

•  (A) m₂ + m₄ + m₆ + m₇
•  (B) m₀ +m₁ + m₃ + m₅
•  (C) m₀ +m₁ + m₆ + m₇
•  (D) m₂ + m₃ + m₄ + m₅

P is a 16-bit signed integer. The 2’s complement representation of P is (F87B)₁₆. The 2’s complement representation of 8*P is

•  (A) (C3D8)₁₆
•  (B) (187B)₁₆
•  (C) (F878)₁₆
•  (D) (987B)₁₆

The Boolean expression for the output f of the multiplexer shown below is

•  (A) $\overline{P\oplus Q\oplus R}$
•  (B) $P\oplus Q\oplus R$
•  (C) $P+Q+R$
•  (D) $\overline{P+Q+R}$

What is the Boolean expression for the output f of the combinational logic circuit of NOR gates given below?

•  (A) $\overline{Q+R}$
•  (B) $\overline{P+Q}$
•  (C) $\overline{P+R}$
•  (D) $\overline{P+Q+R}$

In the sequential circuit shown below, if the initial value of the output Q₁Q₀ is 00, what are the next four values of Q₁Q₀?

•  (A) 11,10,01,00
•  (B) 10,11,01,00
•  (C) 10,00,01,11
•  (D) 11,10,00,01

(1217)₈ is equivalent to

•  (A) (1217)₁₆
•  (B) (028F)₁₆
•  (C) (2297)₁₀
•  (D) (0B17)₁₆

What is the minimum number of gates required to implement the Boolean function (AB+C) if we have to use only 2-input NOR gates?

•  (A) 2
•  (B) 3
•  (C) 4
•  (D) 5

In the IEEE floating point representation the hexadecimal value 0x00000000 corresponds to

•  (A) The normalized value 2^-127
•  (B) The normalized value 2^-126
•  (C) The normalized value +0
•  (D) The special value +0

In the Karnaugh map shown below, X denotes a don’t care term. What is the minimal form of the function represented by the Karnaugh map?

•  (A) $\overline{b}.\overline{d}+\overline{a}.\overline{d}$
•  (B) $\overline{a}.\overline{b}+\overline{b}.\overline{d} +\overline{a}.b.\overline{d}$
•  (C) $\overline{b}.\overline{d} +\overline{a}.b.\overline{d}$
•  (D) $\overline{a}.\overline{b}+\overline{b}.\overline{d} +\overline{a}.\overline{d}$

Let r denote number system radix. The only value(s) of r that satisfy the equation $\sqrt{{121}_r}={11}_r$ is / are

•  (A) decimal 10
•  (B) decimal 11
•  (C) decimal 10 and 11
•  (D) any value >2

Given f₁, f₃ and f in canonical sum of products form (in decimal) for the circuit

f₁ = ${\sum }_{}$m (4, 5, 6, 7, 8)
f₃ = ${\sum }_{}$m (1, 6, 15)
f = ${\sum }_{}$m (1, 6, 8, 15)
then f₂ is

•  (A) ${\sum }_{}$ m (4, 6)
•  (B) ${\sum }_{}$m (4, 8)
•  (C) ${\sum }_{}$m (6, 8)
•  (D) ${\sum }_{}$m (4, 6, 8)

If P, Q, R are Boolean variables, then

$\left(P+\overline{Q}\right)\left(P.\overline{Q}+P.R\right)\left(\overline{P}.\overline{R}+\overline{Q}\right)$

Simplifies to

•  (A) $P.\overline{Q}$
•  (B) $P.\overline{R}$
•  (C) $P.\overline{Q}+R$
•  (D) $P.\overline{R}+Q$

What is the maximum number of different Boolean functions involving n Boolean variables?

•  (A) n²
•  (B) 2ⁿ
•  (C) 2²ⁿ
•  (D) 2ⁿ²

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?

•  (A) 7
•  (B) 8
•  (C) 9
•  (D) 10

Consider the following Boolean function of four variables:

$f\left(w,x,y,z\right)=\sum \left(1,3,4,6,9,11,12,14\right)$

The function is

•  (A) independent of one variables.
•  (B) independent of two variables.
•  (C) independent of three variables.
•  (D) dependent on all the variables.

Let $f\left(w,x,y,z\right)=\sum \left(0,4,5,7,8,9,13,15\right)$. Which of the following expressions are NOT equivalent to f ?

(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

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?

•  (A) Only P and Q are valid.
•  (B) Only Q and R are valid.
•  (C) Only P and R are valid.
•  (D) All P, Q, R are valid.

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?

•  (A) 2ⁿ line to 1 line
•  (B) 2ⁿ⁺¹ line to 1 line
•  (C) 2^n-1 line to 1 line
•  (D) 2^n-2 line to 1 line

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\oplus 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\oplus C_i$ and $C_{i+1}=G_i+P_i{C}_i$ ,where C₀ 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 S₃, S₂, S₁, S₀, and C₄ as its outputs are respectively:

•  (A)   6, 3
•  (B)   10, 4
•  (C)   6, 4
•  (D)   10, 5

The control signal functions of a 4-bit binary counter are given below (where X is “don’t care”):

The counter is connected as follows:

Assume that the counter and gate delays are negligible. If the counter starts at 0, then it cycles through the following sequence:

•  (A)   0, 3, 4
•  (B)   0, 3, 4, 5
•  (C)   0, 1, 2, 3, 4
•  (D)   0, 1, 2, 3, 4, 5