1
\$\begingroup\$

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?

Answer is: 2n−1 to 1

Any help provided to understand this question is appreciated.

\$\endgroup\$
1

1 Answer 1

0
\$\begingroup\$

circuit input n goes to the inverter circuit inputs 1 to n-1 go the multiplexer address lines

mux data inputs are wired to 1,0,n or not(n) as required to produce your function on the output.

\$\endgroup\$
2
  • \$\begingroup\$ what would happen if we are not given with NOT GATE/INVERTER? \$\endgroup\$ Commented Jul 15, 2018 at 11:44
  • \$\begingroup\$ then you would not have not n as a choice for mux inputs so you'd only be able to fully handle functions of n-1 bits. \$\endgroup\$ Commented Jul 16, 2018 at 6:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.