\$\begingroup\$
\$\endgroup\$
1
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.
ocrdu
9,34123 gold badges33 silver badges43 bronze badges
asked Jul 14, 2018 at 5:30
-
\$\begingroup\$ Related to your question, maybe it helps: electronics.stackexchange.com/questions/383660/… \$\endgroup\$Marco Zollinger– Marco Zollinger2018年07月14日 11:07:00 +00:00Commented Jul 14, 2018 at 11:07
1 Answer 1
\$\begingroup\$
\$\endgroup\$
2
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.
answered Jul 14, 2018 at 6:56
-
\$\begingroup\$ what would happen if we are not given with NOT GATE/INVERTER? \$\endgroup\$Geeklovenerds– Geeklovenerds2018年07月15日 11:44:04 +00:00Commented Jul 15, 2018 at 11:44
-
\$\begingroup\$ then you would not have
not nas a choice for mux inputs so you'd only be able to fully handle functions of n-1 bits. \$\endgroup\$Jasen Слава Україні– Jasen Слава Україні2018年07月16日 06:05:03 +00:00Commented Jul 16, 2018 at 6:05