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?


2^n line to 1 line


2^(n+1) line to 1 line


2^(n-1) line to 1 line


2^(n-2) line to 1 line

Answer: (c).2^(n-1) line to 1 line

Engage with the Community - Add Your Comment

Confused About the Answer? Ask for Details Here.

Know the Explanation? Add it Here.

Q. 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?

Similar Questions

Discover Related MCQs

Q. In a look-ahead carry generator, the carry generate function Gi and the carry propagate function Pi for inputs Ai and Bi are given by:

Pi = Ai ⨁ Bi and Gi = AiBi

The expressions for the sum bit Si and the carry bit Ci+1 of the look-ahead carry adder are given by:

Si = Pi ⨁ Ci and Ci+1 = Gi + PiCi , where C0 is the input carry.

Consider a two-level logic implementation of the look-ahead carry generator. Assume that all Pi and Gi 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:

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

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

Q. 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?

Q. Let X 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(P, Q) = ( ( 1 X P) X (P X Q) ) X ( (P X Q) X (Q X 0) )

The equivalent expression for F is

Q. Consider a Boolean function f (w, x, y, z). suppose that exactly one of its inputs is allowed to change at a time. If the function happens to be true for two input vectors i1 = (w1, x1, y1, z1) and i2 = (w2, x2, y2, z2) we would like the function to remain true as the input changes from i1 to i2 (i1 and i2 differ in exactly one bit position), without becoming false momentarily. Let f (w, x, y, z) = ∑(5,7,11,12,13,15). Which of the following cube covers of f will ensure that the required property is satisfied?

Q. The hexadecimal representation of 6578 is

Q. The switching expression corresponding to f(A, B, C, D) = Σ (1, 4, 5, 9, 11, 12) is

Q. The Boolean function x'y' + xy + x'y is equivalent to

Q. In an SR latch made by cross-coupling two NAND gates, if both S and R inputs are set to 0, then it will result in

Q. A circuit outputs a digit in the form of 4 bits. 0 is represented by 0000, 1 by 0001, ..., 9 by 1001. A combinational circuit is to be designed which takes these 4 bits as input and outputs 1 if the digit ≥ 5, and 0 otherwise. If only AND, OR and NOT gates may be used, what is the minimum number of gates required?

Q. Which are the essential prime implicants of the following Boolean function? f(a, b, c) = a'c + ac' + b'c

Q. Consider a multiplexer with X and Y as data inputs and Z as control input. Z = 0 selects input X, and Z = 1 selects input Y. What are the connections required to realize the 2-variable Boolean function f = T + R, without using any additional hardware ?

Q. A 4-bit carry lookahead adder, which adds two 4-bit numbers, is designed using AND, OR, NOT, NAND, NOR gates only. Assuming that all the inputs are available in both complemented and uncomplemented forms and the delay of each gate is one time unit, what is the overall propagation delay of the adder? Assume that the carry network has been implemented using two-level AND-OR logic.

Q. Consider an array multiplier for multiplying two n bit numbers. If each gate in the circuit has a unit delay, the total delay of the multiplier is

Q. A 1-input, 2-output synchronous sequential circuit behaves as follows : Let zk, nk denote the number of 0's and 1's respectively in initial k bits of the input (zk + nk = k). The circuit outputs 00 until one of the following conditions holds.

zk - nk = 2. In this case, the output at the k-th and
all subsequent clock ticks is 10.
nk - zk = 2. In this case, the output at the k-th and
all subsequent clock ticks is 01.

What is the minimum number of states required in the state transition graph of the above circuit?

Q. Let f(A, B) = A' + B. Simplified expression for function f(f(x + y, y)z) is :

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

Q. A positive edge-triggered D flip-flop is connected to a positive edge-triggered JK flipflop 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.

Q. Consider the operations f(X, Y, Z) = X'YZ + XY' + Y'Z'  and  g(X′, Y, Z) = X′YZ + X′YZ′ + XY. Which one of the following is correct?